Knight's Algorithm using Backtracking

Question

I have written this Knight's problem algorithm using Backtracking and got the following output, however wherever I have looked up people code it differently and I don't know if this way is correct or wrong and what optimizations are needed? Could anyone guide me here as I am fairly new with backtracking algorithms.

#include<bits/stdc++.h>
using namespace std;


bool isValid(int arr[][5], int i, int j)
{
    return (i>=0 && j>=0 && i<5 && j<5 && arr[i][j]==0);
}

void knightProblem(int arr[][5], int i, int j)
{
    static int count = 0;

    if(!isValid(arr,i,j))
        return;

    count++;

    arr[i][j]=count;

    knightProblem(arr,i+2,j+1);
    knightProblem(arr,i+2,j-1);
    knightProblem(arr,i-2,j+1);
    knightProblem(arr,i-2,j-1);
    knightProblem(arr,i+1,j+2);
    knightProblem(arr,i+1,j-2);
    knightProblem(arr,i-1,j+2);
    knightProblem(arr,i-1,j-2);
}

int main()
{
        int maze[5][5]  =  {
       {0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0}
    };

    knightProblem(maze,0,0);

    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            cout<<maze[i][j]<<" ";
        }

        cout<<"\n";
    }
}

Output

1 23 18 12 24

19 13 15 7 17

22 2 9 4 11

14 20 6 16 8

25 21 3 10 5

Answer 1

Your code is incorrect. You never return to try another branch, as you always increment the counter. You are just traversing all the cells in a DFS order, and there is no guarantee that it would produce a valid solution (where a valid solition means a path, not a DFS order).

The ideas how you can correct the algorithm:

1. The correct solution needs to traverse all cells using just one path. Whenever you find that you cannot continue, and you still have not visited all cells, you need to step back freeing the currect position.
2. The function knightProblem has to return a value indicating whether you found a solution in that direction or not. If none of the paths from current state allow you to find a solution, you need to free the cell and return back.
3. Avoid static int counter. That is a bad practice for many reasons. Better allocate a variable in the main and pass it by reference.
4. The final state (that indicates that you have found a solution) is when your counter is equal to the size of the board.