Print all Knight 's tour possible from a starting point on NxN chessboard | C ++ program of the above approach ; Stores the 8 possible combinations of moves that the knight can follow ; Function to find if ( i , j ) is a valid cell for the knight to move and it exists within the chessboard ; Stores whether there exist any valid path ; Recursive function to iterate through all the paths that the knight can follow ; Mark the current square of the chessboard ; If the number of visited squares are equal to the total number of sqares ; Print the current state of ChessBoard ; Backtrack to the previous move ; Iterate through all the eight possible moves for a knight ; Stores the new position of the knight after a move ; If the new position is a valid position recursively call for the next move ; Backtrack to the previous move ; Driver Code ; If no valid sequence of moves exist
#include <bits/stdc++.h> NEW_LINE using namespace std ; int DirX [ ] = { 2 , 1 , -1 , -2 , -2 , -1 , 1 , 2 } ; int DirY [ ] = { 1 , 2 , 2 , 1 , -1 , -2 , -2 , -1 } ; bool isSafe ( int i , int j , int n , vector < vector < int > > & Board ) { return ( i >= 0 and j >= 0 and i < n and j < n and Board [ i ] [ j ] == 0 ) ; } bool isPossible = false ; void knightTour ( vector < vector < int > > & ChessBoard , int N , int x , int y , int visited = 1 ) { ChessBoard [ x ] [ y ] = visited ; if ( visited == N * N ) { isPossible = true ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { cout << ChessBoard [ i ] [ j ] << " ▁ " ; } cout << endl ; } cout << endl ; ChessBoard [ x ] [ y ] = 0 ; return ; } for ( int i = 0 ; i < 8 ; i ++ ) { int newX = x + DirX [ i ] ; int newY = y + DirY [ i ] ; if ( isSafe ( newX , newY , N , ChessBoard ) && ! ChessBoard [ newX ] [ newY ] ) { knightTour ( ChessBoard , N , newX , newY , visited + 1 ) ; } } ChessBoard [ x ] [ y ] = 0 ; } int main ( ) { vector < vector < int > > ChessBoard ( 5 , vector < int > ( 5 , 0 ) ) ; int N = ChessBoard . size ( ) ; int X = 1 ; int Y = 1 ; knightTour ( ChessBoard , N , X - 1 , Y - 1 ) ; if ( ! isPossible ) { cout << -1 ; } return 0 ; }