Computing a knight's Tour with C++


The knight's tour is a famous puzzle where you move a knight on a chessboard to each square exactly once. The knight's tour dates back to about the 9th Century, and has been has been a popular topic for mathematicians including Leonhard Euler, who was one of the first to explore the problem in length.

Since then, with the popularization of computers and programming, the puzzle has moved from the hobbyists and mathematicians, to the computer scientists.

During this time, it was proven that for any m × n board with mn, a closed knight's tour is always possible unless one or more of these three conditions are met: [Reference]

  1. m and n are both odd
  2. m = 1, 2, or 4
  3. m = 3 and n = 4, 6, or 8.
What A Knight's Voyage Is

There are many ways in which to compute a knight's voyage. The method that I will demonstrate here is a recursive brute force search-tree algorithm. This means the the function will take in the boards parameters (width, height, start position), and search each move from the current position, and "cutting" off any paths that prove invalid.

The following program relies on the grid class, which models the structure of the board, and is mainly unimportant to the understanding of the algorithm. To See the source for the class, hover here.

The program itself goes as follows:


bool voyagingKnight(Grid& visited, int x, int y, int m){
    
    //Ensure that the cell is in bounds.
    if (x>=visited.getWidth() || x<0 || y>=visited.getHeight() || y<0){
        return false;
    }
    
    //Ensure that the cell is untouched.
    if(visited[x][y] != -1 && m != 0){
        return false;
    }
    
    //If the iteration has made it this far then it is a valid move.
    visited[x][y] = m;
    
    //If all cells have been touched, output the board and exit the function.
    if(m == visited.getWidth() * visited.getHeight() - 1){
        
        //Loop through each row.
        for (int i = 0; i < visited.getHeight(); i++){
            //Loop through each column
            for (int j = 0; j < visited.getWidth(); j++){
                //Output each cell.
                std::cout << visited[j][i];
                
                //If the value is 1 didget, use 4 spaces, else use only 3.
                if (visited[j][i] < 10) std::cout << "    ";
                else std::cout << "   ";
               
            }
            //Add a space at the end of every row.
            std::cout << "\n";
        }
        
        return true;
        
    //Else, the move was valid, but the voyage is not yet complete.
    }else{
        bool result = false;
        
        //Recursively call each move to check for validity.
        result = (result || voyagingKnight(visited, x+2, y+1, m+1));
        result = (result || voyagingKnight(visited, x+2, y-1, m+1));
        result = (result || voyagingKnight(visited, x-2, y+1, m+1));
        result = (result || voyagingKnight(visited, x-2, y-1, m+1));
        result = (result || voyagingKnight(visited, x+1, y+2, m+1));
        result = (result || voyagingKnight(visited, x+1, y-2, m+1));
        result = (result || voyagingKnight(visited, x-1, y+2, m+1));
        result = (result || voyagingKnight(visited, x-1, y-2, m+1));
        
        //This position resulted in a voyage.
        if( result == true ){
            return true;
        //Else, not of the moves were sucessfull, so we must backtrack.
        }else{
            //Unviset the current location.
            visited[x][y] = -1; 
            return false;
        }
    }
}

Although this code may look intimidating at first, what it is actually doing is quite simple. Between lines 4 and 15, it is checking if it is a valid move. Between lines 17 and 39, it is checking if it covered every square, and if if did, then it outputs the solution to the console. After that, it is finding every move that can be made from your current position, and recursively calling voyagingKnight on each move. In the end, you should end up with a chess board printed in your console representing the steps required for a knights tour.

We hope that you have found this useful, and have fun finding all 26,534,728,821,064 variations!