Not getting any output to my code for Knight's Tour Problem

Question

Problem:

Given a N*N board with the Knight placed on the first block of an empty board. Moving according to the rules of chess knight must visit each square exactly once. Print the order of each cell in which they are visited.

I used backtracking, but not getting any output

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

bool valid(int a, int b)
{
    //check validity
    if (a < 0 || a > 7 || b < 0 || b > 7)
        return false;

    return true;
}

bool backtrack(vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j)
{
    //ans found
    if (chess[i][j] == 63)
        return true;
        
    else
    {
        bool flag = false;

        for (int k = 0; k < moves.size(); k++)
        {
            int a = i + moves[k].first, b = j + moves[k].second;
            //if valid.. and not already visited
            if (valid(a, b) && chess[a][b] == -1)
            {
                chess[a][b] = chess[i][j] + 1;

                //recurse for next moves
                flag = backtrack(chess, moves, a, b);

                //if solution not found..backtrack
                if (!flag)
                    chess[a][b] = -1;
                
                //break..return ans
                else
                    break;
            }
        }
        return flag;
    }
}

int main()
{
    vector<vector<int>> chess(8, vector<int>(8, -1));

    vector<pair<int, int>> moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};
    
    chess[0][0] = 0;

    backtrack(chess, moves, 0, 0);

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            cout << chess[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Answer 1

Change the ordering of your moves to (the less tangled)

    vector<pair<int, int>> moves = { {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

and it will work. Quite quickly.

There are multiple possible solutions. There are also other strategies for choosing the search order which may improve things.

Here is an alternative version, allowing you to play with the size of the board:

#include <iostream>
#include <iomanip>
#include <utility>
using namespace std;

const int N = 8;
int A[N][N]{};
pair<int,int> jump[] = { {1,2}, {2,1} ,{2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

//==========================================================

void display()
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) cout << setw( 3 ) << A[i][j];
      cout << '\n';
   }
}

//==========================================================

bool check( int mv, int i, int j )
{
   if ( i < 0 || i >= N || j < 0 || j >= N || A[i][j] ) return false;
   A[i][j] = mv;
   return true;
}

//==========================================================

bool solve( int mv, int i0, int j0 )                       // main backtracking routine
{
   if ( mv == N * N )                                      // *** COMPLETION
   {
      display();
      return true;
   }

   for ( int jp = 0; jp < 8; jp++ )
   {
      int i = i0 + jump[jp].first ;
      int j = j0 + jump[jp].second;
      if ( check( mv, i, j ) && solve( mv + 1, i, j ) ) return true;      // *** MAIN RECURSIVE CALL ***
   }
   A[i0][j0] = 0;
   return false;
}

//==========================================================

int main()
{
   int i = 0, j = 0, mv = 0;
   A[i][j] = mv;
   solve( mv + 1, i, j );
}