Knight's tour in C++

Question

I have this knight's tour problem that I have to solve. I have to input a NxN matrix and the coordinates of the knight, where (1 , 1) is the bottom left element. Now the program works correctly, however my problem is that the task states that there can be many inputs. That's why I've added a while loop in the main function (to continuously take inputs and solve them, however after the first input the program doesn't let me write anymore in the console (as if it blocks out), and the only thing I can do is stop the console. Can you please help me with my problem? Thanks in advance.

#include <iostream>

using namespace std;

const int MAXN = 10;
const int MAXD = 10;

const int maxDiff = 8;

const int diffX[MAXD] = { 1, 1, -1, -1, 2, -2, 2, -2 };
const int diffY[MAXD] = { 2, -2, 2, -2, 1, 1, -1, -1 };

unsigned board[MAXN][MAXN];
unsigned newX, newY;

void printBoard(int n)
{
int i, j;
for (i = n; i > 0; i--) {
    for (j = 0; j < n; j++)
    {
        if (j == 0)
        {
            cout << board[i - 1][j];
        }
        else
        {
            cout << " " << board[i - 1][j];
        }
    }
    cout << endl;
}
}

void nextMove(int X, int Y, int i, int n)
{
int k;
board[X][Y] = i;
if (i == n * n) 
{ 
    printBoard(n); 
    return; 
}

for (k = 0; k < maxDiff; k++)
{
    newX = X + diffX[k]; newY = Y + diffY[k];
    if ((newX >= 0 && newX < n && newY >= 0 && newY < n) && (0 ==             board[newX][newY]))
    {
        nextMove(newX, newY, i + 1, n);
    }
}
board[X][Y] = 0;
}

int main()
{
int n;
int startX;
int startY;
int br = 0;
while (cin >> n >> startX >> startY)
{
    if (n < 4 || n > 10)
    {
        break;
    }
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            board[i][j] = 0;
        }
    }
    nextMove(startX - 1, startY - 1, 1, n);
}
return 0;
}

Edit: Apparently I mistook the conditions. The matrix should be 2 < n < 10. However when I change the condition the program doesn't work for matrix lower than 5. Any idea what's wrong with it?

Answer 1

1. The knight's tour is a special case of Hamiltonian path problem is NP-hard in general.Heuristic is able to successfully locate a solution in linear time.
2. for m × n board with m ≤ n, a closed knight's tour is always possible unless one or more of these three conditions are met.
   • m and n are both odd
   • m = 1, 2, or 4
   • m = 3 and n = 4, 6, or 8.wiki

You are using bruit-force approach. Hence it stuck in cases where it will not find the solution.

after the first input the program doesn't let me write anymore

because nextMove() continues to execute after finding the solution . You should place flag

if (i == n * n) 
{ 
    printBoard(n); 
    global_flag=true;
    return; 
}

and check this flag in

if ((newX >= 0 && newX < n && newY >= 0 && newY < n) && (0 == board[newX]newY]))
{
    nextMove(newX, newY, i + 1, n);
    if(global_flag) return;
}

initialize global_flag=false in while loop