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

Does your code produce the right answer? https://codereview.stackexchange.com/ might be more appropriate — Alan Birtles, Dec 25 '20 at 06:50
The only way to know if your code behaves as desired is to test the code. That's your job. We may be able to help you establish the parameters of your tests, but a flat out "Does my code work?" is a tough sell. — user4581301, Dec 25 '20 at 06:54
But in your case I can safely say, no. For a great many compilers this code doesn't work at all. For example, here's what happens with Visual Studio: https://godbolt.org/z/eqvd6v — user4581301, Dec 25 '20 at 06:56
Yes my code works, the output is posted below of my code. I have tried on sublime text — Aditya Sarin, Dec 25 '20 at 06:59
Well, I tried it with a different compiler and it failed to compile. Read into that whatever you want. But also read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — user4581301, Dec 25 '20 at 07:13

score 1 · Accepted Answer · answered Dec 25 '20 at 07:14

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:

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.
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.
Avoid static int counter. That is a bad practice for many reasons. Better allocate a variable in the main and pass it by reference.
The final state (that indicates that you have found a solution) is when your counter is equal to the size of the board.

Knight's Algorithm using Backtracking

Output

1 Answers1