Knight's Tour Brute Force

Question

I'm lost with how the knight backtracks using recursion. I've tried multiple ways as you can see it's commented out some of the attempts, but how does it know how far to backtrack back to start moving forward again? My understanding of recursion is the function calls itself each time with new arguments building up the stack frame, and when it gets to the base case it goes back down the stack frame, in this case moving back moves. Can someone point me in the right direction? Thanks.

#include "stdafx.h"
#include <iostream>
#include <iomanip>

using namespace std;


int GAMEBOARD[8][8] = { 0 };
int TOTAL_MOVES = 0, BAD_MOVES = 0;

bool moveKnight(int row, int col, int movNum);
void print();

int main()
{
    int startRow = 3, startCol = 3;
    int moveNum = 1;

    GAMEBOARD[startRow][startCol] = moveNum;
    TOTAL_MOVES++;

    moveKnight(startRow, startCol, moveNum);

    if (moveKnight(startRow, startCol, moveNum) == true) {
        cout << "Knight's Tour Solved! It took " << TOTAL_MOVES <<
            " total moves and " << BAD_MOVES << " bad moves." << endl;
    }

    system("pause");
    return 0;
}

bool moveKnight(int row, int col, int moveNum)
{
    GAMEBOARD[row][col] = moveNum;
    TOTAL_MOVES++;


    if (moveNum == 64) {
        return true;
    }

    if (GAMEBOARD[row][col] != 0) {
        GAMEBOARD[row][col] = 0;
        print();
        system("pause");
        return moveKnight(row, col, moveNum);
    }

// commented out
    /*if (GAMEBOARD[row - 2][col + 1] != 0) {
        print();
        system("pause");
        return moveKnight(row - 2, col + 1, moveNum + 1);
    }
    else if (GAMEBOARD[row - 1][col + 2] != 0) {
        print();
        system("pause");
        return moveKnight(row - 1, col + 2, moveNum + 1);
    }
    else if (GAMEBOARD[row + 1][col + 2] != 0) {
        print();
        system("pause");
        return moveKnight(row + 1, col + 2, moveNum + 1);
    }
    else if (GAMEBOARD[row + 2][col + 1] != 0) {
        print();
        system("pause");
        return moveKnight(row + 2, col + 1, moveNum + 1);
    }
    else if (GAMEBOARD[row + 2][col - 1] != 0) {
        print();
        system("pause");
        return moveKnight(row + 2, col - 1, moveNum + 1);
    }
    else if (GAMEBOARD[row + 1][col - 2] != 0) {
        print();
        system("pause");
        return moveKnight(row + 1, col - 2, moveNum + 1);
    }
    else if (GAMEBOARD[row - 1][col - 2] != 0) {
        print();
        system("pause");
        return moveKnight(row - 1, col - 2, moveNum + 1);
    }
    else if (GAMEBOARD[row - 2][col - 1] != 0) {
        print();
        system("pause");
        return moveKnight(row - 2, col - 1, moveNum + 1);
    }

    return false;*/






    else if (row - 2 >= 0 && row - 2 <= 7 && col + 1 >= 0
        && col + 1 <= 7 && GAMEBOARD[row - 2][col + 1] == 0) {
        GAMEBOARD[row - 2][col + 1] = moveNum;
        print();
        system("pause");
        return moveKnight(row - 2, col + 1, moveNum + 1);
    }
    else if (row - 1 >= 0 && row - 1 <= 7 && col + 2 >= 0
        && col + 2 <= 7 && GAMEBOARD[row - 1][col + 2] == 0) {
        GAMEBOARD[row - 1][col + 2] = moveNum;
        print();
        system("pause");
        return moveKnight(row - 1, col + 2, moveNum + 1);
    }
    else if (row + 1 >= 0 && row + 1 <= 7 && col + 2 >= 0
        && col + 2 <= 7 && GAMEBOARD[row + 1][col + 2] == 0) {
        GAMEBOARD[row + 1][col + 2] = moveNum;
        print();
        system("pause");
        return moveKnight(row + 1, col + 2, moveNum + 1);
    }
    else if (row + 2 >= 0 && row + 2 <= 7 && col + 1 >= 0
        && col + 1 <= 7 && GAMEBOARD[row + 2][col + 1] == 0) {
        GAMEBOARD[row + 2][col + 1] = moveNum;
        print();
        system("pause");
        return moveKnight(row + 2, col + 1, moveNum + 1);
    }
    else if (row + 2 >= 0 && row + 2 <= 7 && col - 1 >= 0
        && col - 1 <= 7 && GAMEBOARD[row + 2][col - 1] == 0) {
        GAMEBOARD[row + 2][col - 1] = moveNum;
        print();
        system("pause");
        return moveKnight(row + 2, col - 1, moveNum + 1);
    }
    else if (row + 1 >= 0 && row + 1 <= 7 && col - 2 >= 0
        && col - 2 <= 7 && GAMEBOARD[row + 1][col - 2] == 0) {
        GAMEBOARD[row + 1][col - 2] = moveNum;
        print();
        system("pause");
        return moveKnight(row + 1, col - 2, moveNum + 1);
    }
    else if (row - 1 >= 0 && row - 1 <= 7 && col - 2 >= 0
        && col - 2 <= 7 && GAMEBOARD[row - 1][col - 2] == 0) {
        GAMEBOARD[row - 1][col - 2] = moveNum;
        print();
        system("pause");
        return moveKnight(row - 1, col - 2, moveNum + 1);
    }
    else if (row - 2 >= 0 && row - 2 <= 7 && col - 1 >= 0
        && col - 1 <= 7 && GAMEBOARD[row - 2][col - 1] == 0) {
        GAMEBOARD[row - 2][col - 1] = moveNum;
        print();
        system("pause");
        return moveKnight(row - 2, col - 1, moveNum + 1);
    }




// commented out
    /*if (row - 2 < 0 || row - 2 > 7 || col + 1 < 0
        || col + 1 > 7 || GAMEBOARD[row - 2][col + 1] != 0) {
        GAMEBOARD[row - 2][col + 1] = 0;
        return moveKnight(row - 2, col + 1, moveNum + 1);
    }
    else if (row - 1 < 0 || row - 1 > 7 || col + 2 < 0
        || col + 2 > 7 || GAMEBOARD[row - 1][col + 2] != 0) {
        GAMEBOARD[row - 1][col + 2] = 0;
        return moveKnight(row - 1, col + 2, moveNum + 1);
    }
    else if (row + 1 < 0 || row + 1 > 7 || col + 2 < 0
        || col + 2 > 7 || GAMEBOARD[row + 1][col + 2] != 0) {
        GAMEBOARD[row + 1][col + 2] = 0;
        moveKnight(row + 1, col + 2, moveNum + 1);
        return false;
    }
    else if (row + 2 < 0 || row + 2 > 7 || col + 1 < 0
        || col + 1 > 7 || GAMEBOARD[row + 2][col + 1] != 0) {
        GAMEBOARD[row + 2][col + 1] = 0;
        moveKnight(row + 2, col + 1, moveNum + 1);
        return false;
    }
    else if (row + 2 < 0 || row + 2 > 7 || col - 1 < 0
        || col - 1 > 7 || GAMEBOARD[row + 2][col - 1] != 0) {
        GAMEBOARD[row + 2][col - 1] = 0;
        moveKnight(row + 2, col - 1, moveNum + 1);
        return false;
    }
    else if (row + 1 < 0 || row + 1 > 7 || col - 2 < 0
        || col - 2 > 7 || GAMEBOARD[row + 1][col - 2] != 0) {
        GAMEBOARD[row + 1][col - 2] = 0;
        moveKnight(row + 1, col - 2, moveNum + 1);
        return false;
    }
    else if (row - 1 < 0 || row - 1 > 7 || col - 2 < 0
        || col - 2 > 7 || GAMEBOARD[row - 1][col - 2] != 0) {
        GAMEBOARD[row - 1][col - 2] = 0;
        moveKnight(row - 1, col - 2, moveNum + 1);
        return false;
    }
    else if (row - 2 < 0 || row - 2 > 7 || col - 1 < 0
        || col - 1 > 7 || GAMEBOARD[row - 2][col - 1] != 0) {
        GAMEBOARD[row - 2][col - 1] = 0;
        moveKnight(row - 2, col - 1, moveNum + 1);
        return false;
    }
        */


    cout << endl << endl;

    return false;
}

void print()
{
    for (int row = 0; row <= 7; row++) {
        for (int col = 0; col <= 7; col++) {
            cout << setw(5) << GAMEBOARD[row][col];
        }
        cout << endl;
    }
}

Answer 1

Recursion can be tricky to get the hang of! I would highly recommend trying to think through how your algorithm is going to work before you try to start writing code.

Start out by clearly defining your base case. You did this well. Here we have:

if (moveNum == 64) {
    return true;
}

Now, we need to handle think about how to handle the 8 possible moves for the knight from each position. I'm going to simplify your code for this using some sudo code:

moves = [[2, 1], [2, 1], [-2, -1], etc...]; // 8 moves total
for (move : moves) {
    newRow = row + move[0];
    newCol = col + move[1];

    if (InBounds(newRow, newCol) && GAMEBOARD[newRow][newCol] == 0) {
        // Backtracking logic goes here
    }
}

This code essentially does the same thing as your if statements, but is a bit easier to work with and conceptualize.

Recursive backtracking essentially has 2 steps. First, we check if we have reached a base case. Second, we handle the recusive cases. With recursive backtracking, this consists of a few steps:

1. Do something (in this case, move the knight)
2. Make a recursive call to check if this results in a solution
3. If this results in a solution, tell the caller of this function that we found a solution. Additionally, you might want to do something with the solution you found.
4. This didn't result in a solution. Undo what we did in step one, and see if the other recursive cases result in a solution
5. If no recursive case resulting in finding a solution, tell the caller that no solution could be found from the current position.

Applying this format to knights tour:

1. Make a move on the board: GAMEBOARD[newRow][newCol] = moveNum
2. Test if this move results in a solution: result = moveKnight(newRow, newCol, moveNum + 1)
3. If we found a solution, just return true for now. if (result) {return true;}
4. If this move didn't work, undo the move we did: GAMEBOARD[newRow][newCol] = 0. Then, we should see if the other recursive cases result in a solution. My code handles this by looping through each of the moves. You handled it by doing a series of if/else statements.
5. There is no moves from this statement that result in a solution. We should return false to indicate this.

Putting this all together, we get:

bool moveKnight(int row, int col, int moveNum) {

  if (moveNum == 64) {
      return true;
  }
  moves = [[2, 1], [2, 1], [-2, -1], etc...]; // 8 moves total
  for (move : moves) {
    int newRow = row + move[0];
    int newCol = col + move[1];

    if (InBounds(newRow, newCol) && GAMEBOARD[newRow][newCol] == 0) {
      GAMEBOARD[newRow][newCol] = moveNum;
      bool result = moveKnight(newRow, newCol, moveNum + 1);
      if (result) {
        return true;
      } else {
        // Undo this move
        GAMEBOARD[newRow][newCol] = 0;
      }
    }
  }
  return false;
}

Because we don't undo moves when we've found a correct a solution, GAMEBOARD will contain a solution when moveKnight returns true.