A Naive Knight's Tour

Last week I heard of the Knight's Tour Problem, and thought "hey, that sounds fun!" And I was right. Mostly. This is the tale of that journey.

The problem is simple: given an 8x8 chessboard and a Knight placed at an arbitrary location on the board, move the Knight such that it travels to every square only once.

My initial idea turned out to be pretty close to my eventually working solution. However the struggles that I had to get from that initial idea to an actual solution proved revealing.

Here's the initial plan:

• Define an 8x8 chessboard of 8 nested arrays, each with 8 values, each set to false.
• Define a function which accepts the x and y position of the Knight and the current state of the board
  • Mark that coordinate on the board as visited
  • Determine which moves are possible from that location
  • If there are no more possible moves
    • Check if the board has been visited completely
      • If it has, return the path visited to get there
      • If it hasn't, discard that branch and move on to the next one
  • For each possible move, call the function again

Rather than writing the entire algorithm as one block of code, I broke it into a number of parts. This allows me to test each part individually, and to refer to them using declarative names describing my intent rather than details of implementation.

Let's start by defining our recursive function:

function knightsTour(x, y) {}

That was a Bad Idea

I would soon learn that the problem that I had chosen to solve was actually huge. As in, there are ~26.5 billion closed tours (where the Knight returns to its starting location) and ~19.6 quadrillion open tours. While that makes it seem almost as if it is hard for the Knight not to stumble across the right path, for every one of those solutions, there are even more possible wrong answers.

// Possible Move Combinations
4,000,000,000,000,000,000,000,000,000,000,000,000,000

The Knight can easily skip over a square and not be able to reach it later, or just paint itself into a corner where there are no further possible moves within reach.

Is it Recursing Infinitely, or Just Taking Forever?

It's actually really hard to tell the difference between endless recursion and an algorithm which just takes a long time to solve, if you're just sitting there...waiting.

In order to avoid this dilemma, instead of hard coding in the scale of the problem that you want to solve, make your problem scalable, so you can test it for issues before trying to arrive at the entire solution. Aim to have your algorithm run in a matter of seconds or less, and only scale up once you are confident with its validity at that problem size.

Let's re-write that simple function declaration to be scalable:

function knightsTour(x, y, boardSize) {}

Next we'll establish a set of nested arrays to represent the board:

function initializeBoard(boardSize) {
   return [...Array(boardSize)].map(v => 
              [...Array(boardSize)].map(v => false));
}

Now that we have a board, let's make a function to see if every square has been visited:

function entireBoardVisited(board) {
    return board.every(column => column.every(square => square));
}

The Array.prototype.every() function will return true only if every element in the array evaluates to true. So if every square in every column is true, then the entire board has been visited and will return true.

Recursion and Immutability

Something which is important to consider is how we ensure that each step of our branching algorithm isn't polluted by side effects from other branches. If each branch shares the same root chess board, then every time that branch visits a new cell it will mark the cell true. Now that cell has been visited for all branches. That simply won't do.

Instead we need to ensure that for every step along the way we have a chess board that records only the moves made to travel that specific path. That's going to introduce some space complexity which we would want to consider if we were talking about more than an 8x8 board. However for this case the cost is at most 64 8x8 arrays, and the solution is simple:

• give each recursive step a deep copy of the board
• discard any failed branch's board via garbage collection

Since we know the array is only nested once, our deep copy isn't that deep:

function copyBoard(board) {
  return board.map(column => column.slice());
}

Next we need to determine what moves are possible given any coordinate on a board of arbitrary size:

function possibleMoves(x, y, board, size) {
  const moves = []

  const possibilities = [[1, 2], [1, -2], [-1, 2], [-1, -2],
                         [2, 1], [2, -1], [-2, 1], [-2, -1]]
  for (let [offsetX, offsetY] of possibilities) {
    const newX = x + offsetX;
    const newY = y + offsetY;

    if ( newY < size && newY >= 0 
      && newX < size && newX >= 0 
      && !board[newX][newY]) {
        moves.push([newX, newY]);
    }
  }
  return moves;
}

I'd love to know a cleaner way to write that if statement. Please drop a comment if you have an idea!

Basically, if the possible move is in bounds and unvisited, we add it to our list of possible moves at the given coordinate.

My biggest mistake here was assuming that because the logic seemed correct, that it was. It wasn't. I had made several tiny but important errors in my first draft. I went on to write the actual recursive algorithm and struggle through a series of errors because of that assumption.

Don't Make Assumptions, Prove your Expectations

One of the most challenging aspects of programming is simply our own human fallibility. People are imprecise, in our thoughts, in our language. Our minds seamlessly fill in the gaps between fact and assumptions and we need to train ourselves to recognize the difference.

Each time we build out a function, give it limited test data and make sure that it works in isolation. Test Driven Development is great for this. But even if you aren't following that methodology, demonstrate to yourself that your code actually works.

In this case, I had to shrink the board down to a 3x3, then 4x4, then 6x6 size, and prove to myself that I could place the knight at any position and receive a valid result back based upon the border of the board and the contents of the cells.

We're almost ready to recurse! Let's write the most important part of any recursion function first.

The Base Case

Just like you start any while or for loop by defining the condition where it stops, we start our recursive function with the condition where it should stop recursing:

function visitNextPosition(x, y, board, boardSize) {
    // if there are no more moves, check board for completion
        // if the board is complete unwind the successful path
        // if the board is not complete, move on to the next branch
}

With actual code that will look something like this:

function visitNextPosition(x, y, board, boardSize) {
    const copiedBoard = copyBoard(board);
    copiedBoard[x][y] = true;

    const moves = possibleMoves(x, y, copiedBoard, boardSize);
    if (moves.length === 0) {
        if (entireBoardVisited(copiedBoard)) return [[x, y]];
        else return false;
    } else {
        // recursively call function for each possible move
    }
}

So now we've established two possible outcomes to a path:

• return the [x, y] coordinates of the final cell inside of an array
• return false for a failed branch.

Because our return values are different for the two outcomes, we can test for them and respond accordingly. Once we reach our first solution, we want to unwind our call stack, at each stage, adding the [x, y] coordinate of the step that led to our successful tour. But if we don't find a successful path, we want to unwind only until there are more alternative paths to explore.

function visitNextPosition(x, y, board, boardSize) {
  // base case ...
  } else {
    for (let [nextX, nextY] of moves) {
      let path = visitNextPosition(nextX, nextY, copiedBoard, boardSize);
      if (!!path) {
        path.push([x, y]);
        return path;
      }
    }
  return false;
}

If path evaluates to false, it will fall through the if (!!path) statement and the loop will continue on to the next possible move. If all possible moves are exhausted with no solutions reached, then loop will exit, and the function returns false.

However if the path has reached a successful solution, then it has returned something like [[6, 5]] or [[6, 5], [5, 2], [4, 4]] and all we need to do is add our current coordinates to the tail of our Knight's Tour path.

Let's fire it up!

function knightsTour(x, y, boardSize) {
  const board = initializeBoard(boardSize);

  return visitNextPosition(x, y, board, boardSize);
}

var gogoKnight = "gogoKnight " + Date.now();
console.time(gogoKnight);
console.log(knightsTour(0, 1, 8));
console.timeEnd(gogoKnight);
// 60712.694ms 
// 24105743 cells visited

That's not...bad. But can we do better?

Heuristics

Turns out we can! There's some smart people out there, and many different approaches to this problem. One such approach was proposed by H. C. von Warnsdorff back in 1823 who employed a simple heuristic (a practical method of approaching a problem which significantly reduces the steps needed to solve it):

When looking at the next possible moves, prefer the next move with the fewest possible options

This simple rule has three effects.

• It leads us down the shortest paths first. If those paths do not reach a successful outcome, they'll reach their end quicker, and waste less of our time.
• It leads us towards the edges of the board. Squares near the border will naturally have fewer options, and thus will be preferred by the heuristic. This has the consequence of filling in the outside first, which moves us away from the center of the board where our Knight can easily waste a lot of time on tours which are doomed to fail.
• It prefers isolated squares, and is less likely to leave an orphaned, inaccessible square.

Since we've already written a function which returns an array of possible moves from a given coordinate, all we need to do is apply that function to each possible move from the coordinate that we're currently at and then compare the number of potential moves. If we then resort our array according to the fewest possible subsequent moves, then we've got our heuristic!

function warnsdorff(moves, board, size) {
  const weightedMoves = [];
  for (const [x, y] of moves) {
    const weight = possibleMoves(x, y, board, size).length;
    weightedMoves.push({move: [x, y], weight});
  }
  return weightedMoves
          .sort((a, b) => b.weight - a.weight)
          .map(weighted => weighted.move);
}

Now, we just need to call our Warnsdorff heuristic after we've checked for our base case:

function visitNextPosition(x, y, board, boardSize) {
  cellVisits++;

  const copiedBoard = copyNestedArray(board);
  copiedBoard[x][y] = true;

  let moves = possibleMoves(x, y, copiedBoard, boardSize);
  if (moves.length === 0 ) {
    if (entireBoardVisited(copiedBoard)) return [[x, y]];
    else return false;
  }

  // Resort according to Heuristic:  
  moves = warnsdorff(moves, copiedBoard, boardSize);

  for (let [nextX, nextY] of moves) {
    let path = visitNextPosition(nextX, nextY, copiedBoard, boardSize);
    if (!!path) {
      path.push([x, y]);
      return path;
    }
  }
  return false;
}

And oh man, what a difference!

console.time(gogoKnight);
console.log(knightsTour(0, 1, 8));
console.timeEnd(gogoKnight);
// 7.121ms
// 64 cells visited
// Versus:
// 60712.694ms 
// 24105743 cells visited

Even though we've added a function which adds a significant amount of processing to each move, the resulting savings are massive.

That is absolutely brilliant! These heuristics deserve some more looking into.