The Knights tour problem:

Backtracking is an algorithmic paradigm that tries different solutions until finds a solution that . Problems which are typically solved using backtracking technique have the following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once. A Naive solution for these problems is to try all configurations and output a configuration that follows given problem constraints. Backtracking works in an incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.

Problem :

Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each the cell in which they are visited.

Time Complexity : 
There are N2 Cells and for each, we have a maximum of 8 possible moves to choose from, so the worst running time is O(8N^2).

Naive Algorithm for Knights tour 
The Naive Algorithm is to generate all tours one by one and check if the generated tour satisfies the constraints. 

while there are untried tours
{ 
   generate the next tour 
   if this tour covers all squares 
   { 
      print this path;
   }
}

knightTour(x, y, move, sol, xMove, yMove)

Input       (x, y) place, number of moves, solution matrix, and possible x and y movement lists.

Output   The updated solution matrix if it exists.

Backtracking Algorithm for Knights tour 

Following is the Backtracking algorithm for Knights tour problem. 

If all squares are visited 
    print the solution
Else
   a) Add one of the next moves to solution vector and recursively 
   check if this move leads to a solution. (A Knight can make maximum 
   eight moves. We choose one of the 8 moves in this step).
   b) If the move chosen in the above step doesn't lead to a solution
   then remove this move from the solution vector and try other 
   alternative moves.
   c) If none of the alternatives work then return false (Returning false 
   will remove the previously added item in recursion and if false is 
   returned by the initial call of recursion then "no solution exists" )

Source code:

n = 8

def isSafe(x, y, board):

    if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1):

        return True

    return False

def printSolution(n, board):

    for i in range(n):

        for j in range(n):

            print(board[i][j], end=' ')

        print()

        

def solveKT(n):

    board = [[-1 for i in range(n)]for i in range(n)]

    move_x = [2, 1, -1, -2, -2, -1, 1, 2]

    move_y = [1, 2, 2, 1, -1, -2, -2, -1]

    board[0][0] = 0

    pos = 1

    if(not solveKTUtil(n, board, 0, 0, move_x, move_y, pos)):

        print("Solution does not exist")

    else:

        printSolution(n, board)

def solveKTUtil(n, board, curr_x, curr_y, move_x, move_y, pos):

    if(pos == n**2):

        return True

    for i in range(8):

        new_x = curr_x + move_x[i]

        new_y = curr_y + move_y[i]

        if(isSafe(new_x, new_y, board)):

            board[new_x][new_y] = pos

            if(solveKTUtil(n, board, new_x, new_y, move_x, move_y, pos+1)):

                return True

            board[new_x][new_y] = -1

    return False

if __name__ == "__main__":

    solveKT(n)

Output:

 0  59  38  33  30  17   8  63
37  34  31  60   9  62  29  16
58   1  36  39  32  27  18   7
35  48  41  26  61  10  15  28
42  57   2  49  40  23   6  19
47  50  45  54  25  20  11  14
56  43  52   3  22  13  24   5
51  46  55  44  53   4  21  12