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.
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
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
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" )
n = 8
def isSafe(x, y, board):
if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1):
def printSolution(n, board):
for i in range(n):
for j in range(n):
print(board[i][j], end=' ')
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
pos = 1
if(not solveKTUtil(n, board, 0, 0, move_x, move_y, pos)):
print("Solution does not exist")
def solveKTUtil(n, board, curr_x, curr_y, move_x, move_y, pos):
if(pos == n**2):
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)):
board[new_x][new_y] = -1
if __name__ == "__main__":
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