// C Program to Solve Knight’s Tour using Backtracking

#include <stdio.h>

#define N 8

// Function to check if (x, y) is a valid move for the
// knight
int isSafe(int x, int y, int sol[N][N])
{
  return (x >= 0 && x < N && y >= 0 && y < N
	  && sol[x][y] == -1);
}

// Function to print the solution matrix
void printSolution(int sol[N][N])
{
  for (int x = 0; x < N; x++) {
    for (int y = 0; y < N; y++)
      printf(" %2d ", sol[x][y]);
    printf("\n");
  }
}

// Utility function to solve the Knight's Tour problem
int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[N], int yMove[N])
{
  int k, next_x, next_y;
  if (movei == N * N)
    return 1;

  // Try all next moves from the current coordinate x, y
  for (k = 0; k < 8; k++) {
    next_x = x + xMove[k];
    next_y = y + yMove[k];
    if (isSafe(next_x, next_y, sol)) {
      sol[next_x][next_y] = movei;
      if (solveKTUtil(next_x, next_y, movei + 1, sol,
		      xMove, yMove)
	  == 1)
	return 1;
      else
	// Backtracking
	sol[next_x][next_y] = -1;
    }
  }
  return 0;
}

// This function solves the Knight's Tour problem using
// Backtracking
int solveKT()
{
  int sol[N][N];

  // Initialization of solution matrix
  for (int x = 0; x < N; x++)
    for (int y = 0; y < N; y++)
      sol[x][y] = -1;

  // xMove[] and yMove[] define the next move of the
  // knight xMove[] is for the next value of x coordinate
  // yMove[] is for the next value of y coordinate
  int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
  int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

  // Starting position of knight
  sol[0][0] = 0;

  // Start from (0, 0) and explore all tours using
  // solveKTUtil()
  if (solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0) {
    printf("Solution does not exist");
    return 0;
  }
  else
    printSolution(sol);

  return 1;
}

int main()
{
  solveKT();
  return 0;
}