Performing the Knights Tour in Linear Time

mgcadmin 12-07-2024

The knights tour is a classic chess puzzle, which involves finding a path on a chess board where starting from some place on the board, the knight occupies every space once without using the same space twice. Like the N queens problem, finding a knights tour has become a common puzzle for computer science students studying algorithms. And, like the N queens problem, the knights tour is often used as an example of using the backtracking technique.

Backtracking is an adaptation of a preorder depth first search which incorporates a promising function. A promising function determines if the branch being explored is worth continuing or not, and depending on the quality of this promising function has the potential to greatly reduce the number of nodes which need to be explored to find a solution. This is called pruning the search space tree, and can lead to significant speed ups in search times compared to a true exhaustive search. For a problem such a the 8-queens problem, this leads to an efficient solution which returns our answer with ease. The knights tour on the other hand, while being played on the same sized board as the N queens problem is noticeably slower to arrive at an answer.

Solving the Knights Tour with Backtracking

Our "chess board" will be a 2d integer array, with each position initialized to -1, to symbolize that it has not been occupied yet. Depending on where on the board the knight has the potential to move to one of up to 8 places. We store offsets as arrays, so that we can quickly compute possible next moves, though we must be careful to check that a computed next position is in-bounds.

#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;

int coloffset[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int rowoffset[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

typedef vector<vector<int>> ChessBoard; 

void init(ChessBoard& board, int n) {
    board = vector<vector<int>>(n, vector<int>(n, -1));
} 

 
bool inBounds(ChessBoard& cb, int col, int row) {
   return (row >= 0 && row < cb.size() && col >= 0 && col < cb.size());
} 

Backtracking algorithms all follow the same general pattern, which as mentioned above is based on a preorder depth first search of our search space. Since our goal is to occupy every square, once we have made 64 successful moves we are done, so that is our base case. Until reaching our goal, each recursive call will place the knight in one square - or none of backtracking.

 bool promising(ChessBoard& cb, int col, int row) {
    return inBounds(cb, col, row) && (cb[row][col] == -1);
} 
 
bool solveBackTracking(ChessBoard cb, int c, int r, int placed) {
    tries++;
    if (placed == cb.size() * cb.size()) {
        printBoard(cb);
        return true;
    } else {
        for (int i = 0; i < 8; i++) {
            int nc = c + coloffset[i];
            int nr = r + rowoffset[i];
            if (promising(cb, nc, nr)) {
                cb[nr][nc] = placed;
                if (solveBackTracking(cb, nc, nr, placed+1))
                    return true;
                cb[nr][nc] = -1; 
            }
        }
    }
    return false;
} 

Our promising function is exceptionally simple: we simply check that the move keeps us on the board, and that it has not been occupied yet. Unfortunately, because of the constraints we're working with there isn't much more information for us to build a better promising function from. This plays significantly into why backtracking is particularly slow for this problem. The other major part is how big our search tree is: 8 possible next steps, and we need to find 64 of them. It's still better than a true blind brute force search though, and it does lead to a correct answer so this is what you see as the way to solve the knights tour.

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

Yup you read that right. Eight and one quarter million nodes explored before finding a valid solution with backtracking. That's roughly 130k nodes per move. While it certainly isn't good, it's not... catastrophic. But man, wouldn't it be so cool to if we could find it on the first try?

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

Hah, yeah that would be cool.

What? Why are you looking at me like that?

Warnsdorf's Heuristic

Warnsdorf's heuristic is a method for choosing nodes during a knights tour. At each step, instead of simply trying all of the possible next moves sequentially, select the move which brings you to a square from which you have the least possible next moves from. In this way we assign a score to each possible next move, and try them in the order of best possible next move. We will still use backtracking, but we will transform our search from depth first search to best first search. To perform a best first search we will use a min priority queue to pick the next move once we have scored them.

typedef pair<int,int> ScoredMove; 
typedef priority_queue<ScoredMove, vector<ScoredMove>, greater<ScoredMove>> _priorityQueue;

class PriorityQueue {
    private:
        _priorityQueue _pq;
    public:
        PriorityQueue() { }
        bool empty() { 
            return _pq.empty(); 
        }
        void push(int score, int move) {
            _pq.push(make_pair(score, move));
        }
        int pop() {
            int move = _pq.top().second;
            _pq.pop();
            return move;
        }
}; 

To score our moves according to Wanrsdorf's rule, we'll still use our old promising function, because we still need to know the information it provides, by "looking ahead" from a promising node we augment the available information giving our initially weak promising function a significant boost in "guessing" power.

int countMovesFrom(ChessBoard& cb, int c, int r) {
    int valid_moves = 0;
    for (int i = 0; i < 8; i++) {
        int nc = c + coloffset[i];
        int nr = r + rowoffset[i];
        if (promising(cb, nc, nr))
            valid_moves++;
    }
    return valid_moves;
} 
 
void scoreNextMoves(ChessBoard& cb, int c, int r, int paced, PriorityQueue& pq) {
    for (int i = 0; i < 8; i++) {
        int nc = c + coloffset[i];
        int nr = r + rowoffset[i];
        if (promising(cb, nc, nr)) {
            int cm = countMovesFrom(cb, nc, nr);
            if (cm > 0 || placed == 63)
                pq.push(cm, i);
        }
    }
} 

bool tryMove(ChessBoard& cb, int c, int r, int move, int placed) {
    int nc = c + coloffset[move];
    int nr = r + rowoffset[move];
    cb[nr][nc] = placed;
    if (solveBestFirst(cb, nc, nr, placed+1))
        return true;
    cb[nr][nc] = -1;
    return false; 
}

bool solveBestFirst(ChessBoard cb, int c, int r, int placed) {
    tries++;
    if (placed == cb.size() * cb.size()) {
            printBoard(cb);
            return true;
    } else {
        PriorityQueue pq;
        scoreNextMoves(cb, c, r, placed, pq);
        while (!pq.empty()) {
            int next = pq.pop();
            if (tryMove(cb, c, r, next, placed))
                return true;
        }
    }
    return false;
}   

Using the above Warndorfs heuristic to perform a best first search resulted in finding 64 solutions faster than the back tracking solution could find one.

All in a day's work. Until next time, Happy Hacking!

 

---