Design The Knight’s tour problem in Python

Here we are going to discuss backtracking to solve The Knight’s tour problem in Python. At first, before we move on to the problem let’s see what is backtracking. Backtracking is an algorithm paradigm that helps you solve many competitive programs.
So, this algorithm works in a way that tries to figure out all possible solutions following the conditions of the problem. If the next point has a solution it keeps it or else it deletes it. Then it jumps back to the previous step and tries to figure out one more. If there is no solution it moves further back up and so on until the last node is deleted. Then it prints no solution.

Now, let’s understand the program question. The Knight’s tour problem states that: IF A KNIGHT IS PLACED ON THE FIRST BLOCK ON AN EMPTY BOARD THEN FIND A WAY THAT THE KNIGHT VISITS ALL THE SQUARES EXACTLY ONCE FOLLOWING THE RULES OF THE CHESS.

Let’s move forward to the solution to the question.

Python Code: The Knight’s tour problem

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(board): 
  
  for i in range(n): 
    for j in range(n): 
      print(board[i][j],end =' ') 
    print() 


def solveKT(): 
  
  
  
  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(board, 0, 0, move_x, move_y, pos)): 
    print("Solution does not exist") 
  else: 
    printSolution(board) 

def solveKTUtil(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(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()

Let’s understand the code:

At first, I am taking a standard square chessboard of n=8.

Next, I am defining the following functions:

  1. isSafe- It checks whether the move is within the board or not.
  2. solveKT-  It refers to as solve Knight Tour. It provides a move to solveKTUil which says whether it’s true or false. Hence, it solves the problem by backtracking.
  3. printSolution- It prints the solution of the program.

Next, I create a matrix that resembles the chessboard. So actually this matrix contains all the numbers from 0 to 63 as in a 64 square chessboard in that same order.

Finally, solveKTUil a function which receives a value from solveKT and check wethers it is valid or not.

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

Leave a Reply