// 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, int path[N*N],int);

bool isValid(int i, int j);

void printPath(int path[]);

/* A utility function to check if i,j are valid indexes
   for N*N chessboard */



int main(){
    int sol[N][N]={{1,2,3},{4,5,6},{7,8,9}};
    int path[N*2-1] = {0};
    int count =0;
    printSolution(sol,0,0,&count, path, 0);
    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, int path[N*N], int currentPath)
{

    if((i==N-1)&&(j==N-1)){
            (*count)++;
            path[currentPath] =  sol[i][j];
            printPath(path);
            return;
    }

    path[currentPath] =  sol[i][j];


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

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

}


void printPath(int path[N*2-1]){

    int i=0;
    for(i =0; i<N*2-2; i++){

            printf("(%d) ->  ",path[i]);


    }

    printf("(%d)\n", path[i]);






}