// C program for Knight Tour problem
#include<stdio.h>
#include<stdbool.h>
#define N 3
void printSolution(int sol[N][N],int i,int j,int *count);

bool isValid(int i, int j);

/* A utility function to check if i,j are valid indexes
   for N*N chessboard */
int main(){
    int sol[N][N]={{1,2,3},{3,4,3},{3,4,3}};
    int count =0;
    printSolution(sol,0,0,&count);
    printf("%d",count);
}

bool isValid(int i, int j){

    return !((i>=N)||(i<0)||(j>=N)||(j<0));

}


/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N],int i,int j,int *count)
{

    if((i==N-1)&&(j==N-1)){
            (*count)++;
            return;
    }
    if(isValid(i, j+1))
        printSolution(sol, i, j+1, count);

    if(isValid(i+1, j))
        printSolution(sol, i+1, j, count);


}