Knights Tour using Backtracking

Let's discuss Knight's Tour

Motive of the problem is to print the various paths that the knight can take in a N*N board covering all the boxes given that we place the knight at a specific row and column.

Constraints if we look at a chess board that is of 3*3 size it and place the knight at position (1R-1C) the knight cannot move in the "L" shaped manner in this board .

So ideally we want the board to be 5*5 that is the minimum we should expect for our problem to work.
(Note: There are other Algorithms which handle N*M size of pattern but we are sticking to N*N for our problem)

If we place the Knight at the center (2R-2C) we can say the movements will be as follows:

Our basic requirement is to initiate and put '1' from the first row column that user gives us.
which represents the first step taken by the knight and keep incrementing it till covers all the rows*columns.

Let's create a function to take the row column with our first step by setting 'move' variable to '1'

Once we place the knight at a given place we have a choice of placing our knight at the 8 open positions that are valid according to it's movement.

And this is when Recursion enters !!✨
Why recursion?
we want to give the 2nd step the same 8 possible valid
options we gave the 1st step to place the next step of
the knight.

Code:

public static void knightsTour(int[][] chess, int r, int c, int move) 
{
        chess[r][c]=move;
        knightsTour(chess,r-2,c+1,move+1);
        knightsTour(chess,r-1,c+2,move+1);
        knightsTour(chess,r+1,c+2,move+1);
        knightsTour(chess,r+2,c+1,move+1);
        knightsTour(chess,r+2,c-1,move+1);
        knightsTour(chess,r+1,c-2,move+1);
        knightsTour(chess,r-1,c-2,move+1);
        knightsTour(chess,r-2,c-1,move+1);


    }

knightsTour(chess,row,col,1);  //function call

In order to keep the moves valid and inside the N*N board

limits also be careful to not overwrite a previous step we add our conditions.

public static void knightsTour(int[][] chess, int r, int c, int move) 
{
  if(r<0 || c<0 || r>=chess.length || c >=chess.length || chess[r][c]>0)
        {
         return;   
        }
  ....[code]
 }  

As the Recursion call proceeds it is sure to hit a case where the border is less than 0 ,equal/greater to chess length or the path is already set in the box.

Once it does that particular Recursion Stack Path will return to its the Parent Recursion call.

So Ideally we went down a given path as far as we could but could not cover all the boxes. So we backtrack to our previous decision (basically time travel 😅) to the last mistake that we did and erase it .
to do that we Simply remove the previous step that was added in the parent recursion call and go to the parent parent call (bear with me😂) and look for other steps from our 8-1 options and make a new Recursion call to that step...

public static void knightsTour(int[][] chess, int r, int c, int move) {

 ...[code]
        knightsTour(chess,r-1,c-2,move+1);
        knightsTour(chess,r-2,c-1,move+1);
        chess[r][c]=0;   <-- this erases our mistakes

    }

Now we are nearing the end... I can see the light👩‍🚀
We just Print the chessboard as soon as the N*N move is set in the board.
But There is one little tiny thing which is still left..
At the end of the Recursion when our move is 25 for the case (5*5) we have reached our limit and there is no need to run a Recursion call for this case as this will return no possible new steps... and not handling this will
reset the value of that given box to '0' as chess[r][c]=0; runs after RC call.

Also Be sure to remove the 25th element after printing the chessboard as we want the chessboard to be reset with empty values for the next possible paths...

public static void knightsTour(int[][] chess, int r, int c, int move) {

        if(r<0 || c<0 || r>=chess.length || c >=chess.length || chess[r][c]>0)
        {
         return;   
        }
      else if(move==chess.length*chess.length){      
            chess[r][c]=move;
            displayBoard(chess);   
/*displayBoard can be a function to iterate over the i*j values of chessboard and print them */
            chess[r][c]=0;
            return;
            }

THe eND!!