The Knight 's tour problem | Backtracking | Python3 program to solve Knight Tour problem using Backtracking Chessboard Size ; A utility function to check if i , j are valid indexes for N * N chessboard ; A utility function to print Chessboard matrix ; This function solves the Knight Tour problem using Backtracking . This function mainly uses solveKTUtil ( ) to solve the problem . It returns false if no complete tour is possible , otherwise return true and prints the tour . Please note that there may be more than one solutions , this function prints one of the feasible solutions . ; Initialization of Board matrix ; move_x and move_y define next move of Knight . move_x is for next value of x coordinate move_y is for next value of y coordinate ; Since the Knight is initially at the first block ; Checking if solution exists or not ; A recursive utility function to solve Knight Tour problem ; Try all next moves from the current coordinate x , y ; Backtracking ; Driver Code ; Function Call
n = 8 NEW_LINE def isSafe ( x , y , board ) : NEW_LINE INDENT if ( x >= 0 and y >= 0 and x < n and y < n and board [ x ] [ y ] == - 1 ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def printSolution ( n , board ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT print ( board [ i ] [ j ] , end = ' ▁ ' ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT def solveKT ( n ) : NEW_LINE INDENT board = [ [ - 1 for i in range ( n ) ] for i in range ( n ) ] NEW_LINE move_x = [ 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 ] NEW_LINE move_y = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ] NEW_LINE board [ 0 ] [ 0 ] = 0 NEW_LINE pos = 1 NEW_LINE if ( not solveKTUtil ( n , board , 0 , 0 , move_x , move_y , pos ) ) : NEW_LINE INDENT print ( " Solution ▁ does ▁ not ▁ exist " ) NEW_LINE DEDENT else : NEW_LINE INDENT printSolution ( n , board ) NEW_LINE DEDENT DEDENT def solveKTUtil ( n , board , curr_x , curr_y , move_x , move_y , pos ) : NEW_LINE INDENT if ( pos == n ** 2 ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( 8 ) : NEW_LINE INDENT new_x = curr_x + move_x [ i ] NEW_LINE new_y = curr_y + move_y [ i ] NEW_LINE if ( isSafe ( new_x , new_y , board ) ) : NEW_LINE INDENT board [ new_x ] [ new_y ] = pos NEW_LINE if ( solveKTUtil ( n , board , new_x , new_y , move_x , move_y , pos + 1 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT board [ new_x ] [ new_y ] = - 1 NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT solveKT ( n ) NEW_LINE DEDENT