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 );
}

Answer 2

I did not find any infinite loop. But your code never reaches the printing lines, because you are using a brute-force searching algorithm, and the board size you are using is so large that it can't feasibly be computed with brute force in a reasonable amount of time.

Wikipedia says that there are "26,534,728,821,064 closed tours" on an 8x8 board, and basically this means the number of solutions that you can find for that particular board. However:

A brute-force search for a knight's tour is impractical on all but the smallest boards. For example, there are approximately 4×1051 possible move sequences on an 8 × 8 board, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However, the size of this number is not indicative of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty." - Wikipedia (Knight's tour - Brute force algorithms)

It means that the probability of finding one of those solutions in that large of a space is extremely low.

You need to use another algorithm with faster runtime, such as divide and conquer, or others that are listed on that page.

Answer 3

There is not bug in your code. Simply, the algorithm must be slightly improved to be faster.

One trick in to first select cells that do not have much future neighbours.
In the following code,

• I set a list of possible positions.
• For each position, I calculate the number of future possible positions
• I sort the possible first positions according to these numbers

With this modification, I got the result about instantaneously, even for N=20.

Result

 0 59 14 31 48 27 12 29
15 32 53 60 13 30 49 26
58  1 56 45 54 47 28 11
33 16 61 52 63 44 25 50
 2 57 42 55 46 51 10 39
17 34 19 62 43 40  7 24
20  3 36 41 22  5 38  9
35 18 21  4 37  8 23  6

#include <vector>
#include <utility>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <numeric>
#include <algorithm>

#define N 8                 // 8
#define two_n_m1 (N*N-1)    // 63 = N*N - 1

using namespace std;

bool valid(int a, int b) {
    //check validity
    return (a >= 0 && a < N && b >= 0 && b < N);
}

int count_neighbors (vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j) {
    int count = 0;
    for (auto& mov: moves) {
        int a = i + mov.first, b = j + mov.second;
        if (valid(a, b) && (chess[a][b] == -1)) {
            count ++;
        }
    }
    return count;
}

bool backtrack(vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j) {
    //ans found
    if (chess[i][j] == two_n_m1) return true;
    vector<pair<int, int>> neighbors;
    
    for (auto& mov: moves) {
        int a = i + mov.first, b = j + mov.second;
        if (valid(a, b) && (chess[a][b] == -1)) {
            neighbors.push_back ({a, b});
        }
    }
    int n = neighbors.size();
    if (n == 0) return false;
    if (n == 1) {
        int a = neighbors[0].first, b = neighbors[0].second;
        chess[a][b] = chess[i][j] + 1;
        return backtrack(chess, moves, a, b);
    }
    vector<int> future;
    for (auto& candidate: neighbors)  {
        int count = count_neighbors (chess, moves, candidate.first, candidate.second);
        future.push_back (count);                                                                
    }
    vector<int> index(n);
    std::iota (index.begin(), index.end(), 0);
    auto comp = [&] (int i, int j) {return future[i] < future[j];};
    std::sort (index.begin(), index.end(), comp);

    for (int k = 0; k < n; k++) {
        int kp = index[k];
        int a = neighbors[kp].first, b = neighbors[kp].second;
            chess[a][b] = chess[i][j] + 1;
            auto flag = backtrack(chess, moves, a, b);
            if (flag) return true;
            chess[a][b] = -1;
    }
    return false;
}

int main()
{
    vector<vector<int>> chess(N, vector<int>(N, -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;

    auto check = backtrack(chess, moves, 0, 0);
    
    if (!check) {
        cout << "No solution found\n";
        std::exit (1);
    }

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