Knights tour

The following program solves the knights tour problem.

function main () {
  array25<array2<int4>> knightsTour;

  knightsTour.eachCons(2, function (move) {
    from, to = move.first, move.last;
    invariant validMove?(from, to);
  });

  invariant knightsTour.all?(*inBounds?);
  invariant knightsTour.uniq?;

  isClosed = validMove?(knightsTour.last, knightsTour.first);

  expose knightsTour, isClosed;
};

function validMove? (from, to) {
  xDelta = (from.x - to.x).abs;
  yDelta = (from.y - to.y).abs;

  return xDelta == 1 && yDelta == 2
      || xDelta == 2 && yDelta == 1;
};

function inBounds? (coordinate) {
  return coordinate.x.between?(1, 5)
      && coordinate.y.between?(1, 5);
};

function x (coordinate) {
  return coordinate.first;
};

function y (coordinate) {
  return coordinate.last;
};

main();

You can touch the chessboard on the right to try a different tour.

How does it work?

We declare an array of 25 elements to hold the coordinates of the tour. We iterate through eachConsecutive pair of coordinates and specify that it must be valid to go between them. The ‘validMove?’ function checks if the knight moved in an L-shape.

We specify that all coordinates must be in bounds and unique, otherwise it wouldn’t be a valid tour. Finally, we check to see if the tour is ‘closed’, which is defined to be whether the last coordinate loops back round to the start again.

This program assigns multiple expressions at once. It makes use of function pointers and the method syntax to call ‘x’ and ‘y’ on coordinates. It also wraps the high-level code in a ‘main’ function so that it can be placed at the top of the file.

CLI example

Here is an example of running this program with the command-line interface:

sentient --run knights-tour.json --number 3

# standard output:
{"isClosed":false,"knightsTour":[[1,3],[2,5],[4,4], ...]}
{"isClosed":false,"knightsTour":[[2,2],[1,4],[3,5], ...]}
{"isClosed":false,"knightsTour":[[2,4],[1,2],[3,1], ...]}

You can specify that only ‘closed’ tours should be returned like so:

sentient --run knights-tour.json --assign '{ isClosed: true }'

# standard output:
{}

The output above means that Sentient has concluded there are no solutions to the problem. For a 5x5 chessboard, this is correct. Sentient arrives at this conclusion in about four seconds.