The Knight 's tour problem | Backtracking | Javascript program for Knight Tour problem ; A utility function to check if i , j are valid indexes for N * N chessboard ; A utility function to prlet solution matrix sol [ N ] [ N ] ; 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 prlets the tour . Please note that there may be more than one solutions , this function prlets one of the feasible solutions . ; Initialization of solution matrix ; xMove [ ] and yMove [ ] define next move of Knight . xMove [ ] is for next value of x coordinate yMove [ ] is for next value of y coordinate ; Since the Knight is initially at the first block ; Start from 0 , 0 and explore all tours using solveKTUtil ( ) ; A recursive utility function to solve Knight Tour problem ; Try all next moves from the current coordinate x , y ; backtracking ; Function Call
let N = 8 ; function isSafe ( x , y , sol ) { return ( x >= 0 && x < N && y >= 0 && y < N && sol [ x ] [ y ] == - 1 ) ; } function printSolution ( sol ) { for ( let x = 0 ; x < N ; x ++ ) { for ( let y = 0 ; y < N ; y ++ ) document . write ( sol [ x ] [ y ] + " " ) ; document . write ( " " ) ; } } function solveKT ( ) { let sol = new Array ( 8 ) ; for ( var i = 0 ; i < sol . length ; i ++ ) { sol [ i ] = new Array ( 2 ) ; } for ( let x = 0 ; x < N ; x ++ ) for ( let y = 0 ; y < N ; y ++ ) sol [ x ] [ y ] = - 1 ; let xMove = [ 2 , 1 , - 1 , - 2 , - 2 , - 1 , 1 , 2 ] ; let yMove = [ 1 , 2 , 2 , 1 , - 1 , - 2 , - 2 , - 1 ] ; sol [ 0 ] [ 0 ] = 0 ; if ( ! solveKTUtil ( 0 , 0 , 1 , sol , xMove , yMove ) ) { document . write ( " " ) ; return false ; } else printSolution ( sol ) ; return true ; } function solveKTUtil ( x , y , movei , sol , xMove , yMove ) { let k , next_x , next_y ; if ( movei == N * N ) return true ; 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 ) ) return true ; else sol [ next_x ] [ next_y ] = - 1 ; } } return false ; } solveKT ( ) ;