Trying additional moves in the Knight's Tour problem

[tuesday0]

Hey! I am teaching myself how to program from the Deitel 10th edition "How to Program" text, and I'm currently working on a brute force solution approach to the Knight's Tour chess problem. Basically, the puzzle is to try and make a single knight piece navigate the board such that it visits each square once and only once.

I'm at a juncture where I believe I need to make my program try additional move options if the first randomly chosen move isn't valid (i.e., it goes off the board or tries to visit an already-visited square). I know I need to implement this in my while loop in function solveKnight, but I'm not sure how to do it.

The program currently places the knight at a random spot on the board, an 8x8 array filled with zeros. Then it randomly selects another move for the knight. The possible moves are stored in two one-dimensional arrays horizontal and vertical. If validMove says it's a good move, then everything is fine. But if it doesn't allow the move, I need a way for the program to choose new moves from horizontal and vertical:

#include <iostream>
#include <iomanip>
#include <array>
#include <random>

#define N 8    // number of squares in a row/column of the board

bool solveKnight();
void printBoard(std::array<std::array<int, N>, N>&);
bool validMove(std::array<std::array<int, N>, N>&, int, int);

int main() {
    if ( solveKnight() )
        std::cout << "Full tour!" << std::endl;
    else
        std::cout << "Not a full tour." << std::endl;
}

bool solveKnight() {
    std::array<std::array<int, N>, N> board{};
    std::array<int, N> horizontal = {2, 1, -1, -2, -2, -1, 1, 2};
    std::array<int, N> vertical = {-1, -2, -2, -1, 1, 2, 2, 1};
    
    std::default_random_engine engine{static_cast<unsigned long int>(time(0))};
    std::uniform_int_distribution<int> randomRow{0, 7};
    std::uniform_int_distribution<int> randomColumn{0, 7};
    std::uniform_int_distribution<int> randomMove{0, 7};
    
    int moveType, moveNumber{0}, currentRow, currentColumn, testRow, testColumn;
    bool complete{false}, goodMove;
    
    // place the knight at a random spot on the board
    currentRow = randomRow(engine);
    currentColumn = randomColumn(engine); 
    board[currentRow][currentColumn] = ++moveNumber;

    while ( !complete ) {
        int move = randomMove(engine);
        
        testRow = currentRow + horizontal[move];
        testColumn = currentColumn + vertical[move];
        goodMove = validMove(board, testRow, testColumn);
        
        if ( goodMove ) {
            currentRow = testRow;
            currentColumn = testColumn;
            board[currentRow][currentColumn] = ++moveNumber;
        }
    }
    
    if ( moveNumber == 64 ) {
        printBoard(board);
        return true;
    }
    
    printBoard(board);
    return false;
}

void printBoard(std::array<std::array<int, N>, N>& board) {
    for ( int i{0}; i < N; i++ ) {
        for ( int j{0}; j < N; j++ ) {
            std::cout << std::setw(3) << board[i][j];
        }
        
        std::cout << std::endl;
    }
}

bool validMove(std::array<std::array<int, N>, N>& board, int row, int column) {
    return ( row >= 0 && row < N && column >= 0 && column < N && board[row][column] == 0 );
}

I figure I could use something like

testRow = currentRow + horizontal[++move]; and testColumn = currentColumn + vertical[++move]; in some kind of loop that loops through the moves, but what about when move gets incremented to a value larger than 8, the number of moves available in horizontal and vertical? Is there a way to make move wrap back to 0 after it hits 8?

I know this won't produce any full tours unless left to run for quite a while, which is fine for now; that's part of the exercise.

[Ganado]

Is there a way to make move wrap back to 0 after it hits 8

if (move == N) // or N - 1 depending of it's before or after the array dereference
    move = 0;

Or, if you want to be fancy:
move = (move + 1) % N; // keeps move in range [0, N - 1]

PS: Prefer const int or constexpr int over #define of a macro.
const int N = 8;

[tuesday0]

O right, why didn't I think of that if statement... guess I was over-complicating things. I haven't seen % used other than as the modulo operator, so that's new to me. Thanks for that! I might just use the fancy version because why not!?

Will get rid of the #define as well. Thanks a bunch!

[TheIdeasMan]

int moveType, moveNumber{0}, currentRow, currentColumn, testRow, testColumn;
    bool complete{false}, goodMove;

It is usually a good idea to declare and initialise variable in one line of code, once you have a sensible value to initalise with:

int currentRow = randomRow(engine);
int   currentColumn = randomColumn(engine);

Otherwise declare the variable near to where it is used, making sure it is initialised with something. Note that zero may not be a good value for all situations, but an obviously invalid value is better. Unitialised variables are a trap for young and old, it's a golden rule to make sure everything is initialised. This makes it so much easier to debug programs.

This one is aesthetic: Prefer not to use variable names that look similar, like i and j or m and n and the ones in this example.

socpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rl-misread

The core guidelines are a really good resource - try to learn them as you go along :+)

[tuesday0]

@TheIdeasMan
Thank you for the tips and the resource! They will save me lots of headaches in the future, I can already tell.

[lastchance]

#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 = 1;
   A[i][j] = mv;
   solve( mv + 1, i, j );
}

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

[tuesday0]

@lastchance
Thanks for another recursive back-tracking routine that I can study! :)

[doug4]

move = (move + 1) % N; // keeps move in range [0, N - 1]

I haven't seen % used other than as the modulo operator, so that's new to me.

You'll note that this IS the modulo operator. It is not a different use of "%".

Maybe you see it as being used in a kind of preemptive way, but it is a quite common usage of the modulo operator.