Introduction

Before I start I would like to make a small announcement. If you are interested in the Julia language you are welcome to participate in a 4-day “Introduction to Julia for Data Science” short course that is organized at MIT on Jan 17-20, 2023. Everyone is invited. You can find a PDF with the schedule here.

Now we can get back to the usual blogging business.

After my recent post about knight covering puzzle I was asked for another puzzle-solving content. Therefore today I want to present you how the Knight’s tour problem can be cracked using Julia.

The code in this post was tested under Julia 1.8.2 and Plots.jl 1.35.0.

The puzzle

Consider a rectangle grid. We place a chess knight in one of the squares on this grid. A chess knight can move two squares vertically and one square horizontally, or two squares horizontally and one square vertically.

We want to find a sequence of moves of a knight so that it visits each square on a grid exactly once and goes back to a starting position.

I will show you how to find a solution to this problem (or learn that the task is impossible) for arbitrary grid sizes. Next, we will see the solution for a standard chessboard that has 8 rows and 8 columns.

The code

In the solution the key object that we will track is a grid. It will be a matrix storing consecutive moves of a knight. In this matrix a 0 entry means that the square has not visited yet it and positive entry indicates move number when the square was visited. So number 1 is a starting position of the knight.

To track location of the knight on a grid we will use a 2-tuple holding current row and column location of the knight. It is called p in the code.

We first create the listoptions helper function. It takes grid and p as arguments and returns a vector of possible moves of the knight from p to squares that have not been visited yet. Here is its implementation:

listoptions(grid, p) =
    [p .+ d for d in ((1, 2), (-1, 2), (1, -2), (-1, -2),
                      (2, 1), (-2, 1), (2, -1), (-2, -1))
     if get(grid, p .+ d, -1) == 0]

Notice how nicely the get function works in this case. We use it to get a -1 value in case p .+ d is not within bounds of grid (so such invalid moves are discarded).

It is time to present a key function that will handle the traversal of the grid by the knight:

function knight_jump!(grid=fill(0, 8, 8), p=(1, 1), i=1)
    grid[p...] = i
    if i == length(grid)
        p1 = Tuple(findfirst(==(1), grid))
        return extrema(abs, p .- p1) == (1, 2) ? grid : nothing
    end
    v = listoptions(grid, p)
    sort!(v, by=np -> length(listoptions(grid, np)))
    for np in v
        knight_jump!(grid, np, i + 1) !== nothing && return grid
    end
    grid[p...] = 0
    return nothing
end

Let me explain how it works. The grid and p arguments were already discussed. The extra i argument stores the move number. The function returns grid in case it found a feasible solution and nothing if no feasible solution is found. This invariant is crucial, as we will use it to perform depth first search for a valid knight tour.

First we set the grid at location p to i to record the current placement of the knight.

Next in i == length(grid) check we verify that we have hit the last free spot on a grid. If this is the case we check if the current position p is knight-jump away from the initial position of the knight (denoted by p1 in the code). If this is the case we return grid. Otherwise the tour is invalid and we return nothing.

If our tour is not finished yet we store in the v vector the possible moves we can do next. Now a crucial part of the algorithm is applied. We sort v using Warnsdorff’s rule, that is, we put the squares with fewest onward moves in the front of the verctor. We then recursively visit them and try to solve the puzzle. If we succeed, i.e. when the recursive call to knight_jump! does not return nothing, we are done and return the result. If we fail for all values in v, this means that an attempt to visit p was an incorrect choice. In this case we need to reset grid so that in position p it has 0 and return nothing (to signal a problem).

The result

Let us check how the solution looks on a 8x8 grid (which is the default in our code):

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

First we see that indeed the solution was found (as we did not get nothing from the call). Second, a visual inspection of the solution shows that indeed the solution is correct.

Let us additionally visualize it to make the analysis easier. We first convert the res matrix into the moves vector of consecutive knight locations stored as tuples. Next we add first location to the end of this vector (as we have a cycle). Finally we plot a chessboard with consecutive knight moves presented by lines.

julia> using Plots

julia> moves = Tuple.(CartesianIndices(res)[sortperm(vec(res))])
64-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 3)
 (1, 5)
 ⋮
 (6, 3)
 (4, 4)
 (3, 2)

julia> push!(moves, first(moves))
65-element Vector{Tuple{Int64, Int64}}:
 (1, 1)
 (2, 3)
 (1, 5)
 ⋮
 (4, 4)
 (3, 2)
 (1, 1)

julia> plot(getindex.(moves, 1), getindex.(moves, 2);
            legend=false, size=(400, 400), color=:blue,
            marker=:o, markerstrokecolor=:blue,
            xlim=(0.5, 8.5), ylim=(0.5, 8.5),
            minorticks=2, minorgrid=true, grid=false,
            xticks=(0:9, [""; 'A':'H'; ""]), yticks=0:9,
            minorgridalpha=1.0, showaxis=false)

The resulting plot looks as follows:

Knight's tour

Homework

Since I have started the post with an announcement of a short course, let me switch to lecturing mode for a moment. For this puzzle I have the following exercises for you to train your Julia muscle:

  • Check if we ever need to backtrack in the algorithm as maybe we solve the problem on the first attempt thanks to Warnsdorff’s rule?
  • Measure the performance of the code.
  • Do you have ideas how its speed could be improved (hint: think how you can reduce the number of allocations and avoid sorting)
  • Check what would happen if we did not use Warnsdorff’s rule. Two natural candidate rules are: visiting squares in random order and visiting squares in the order produced by the listoptions function.
  • The proposed solution uses recursion. Since Julia has a recursion depth limit the code will not work as expected for large grids. First, find this limit. Second, think how you could rewrite the program so that it avoids using recursion.

Conclusions

I hope you enjoyed the puzzle and the presented solution. If you get stuck on any parts of the homework we can discuss them in January, 2023 at MIT during the short course or just contact me on Julia Discourse or Julia Slack and I will gladly answer your questions.