Solving The Knight’s Tour

I really enjoy solving computer programming puzzles. They are great for exercising the brain and learning new programming languages. One of my all time favorites is The Knight’s Tour, which was given to me as an assignment in college back in ‘93.

The basic idea is this: Place a knight on a standard chessboard in a random starting position. Move the knight using normal L-shaped knight moves to every position on the board without moving to any position twice. There is more than one solution for a given starting point. The smallest solvable board size is 6×6. If you are solving this by hand then it is best to mark the traveled positions with a number. For example, here’s a solved puzzle:

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

Back in college I wrote two solutions: a brute force solution and what I call the “look ahead” solution. On an 8×8 chessboard the brute force solution, written in C++, took 14 days to solve on a 486 DX2. The “look ahead” method can solve it in microseconds. The brute force method travels to every possible position until it finds a solution while the look-ahead method chooses the best move from the next possible moves. The best move is determined by “looking ahead” at the next 2 moves and choosing the move with the least number possible moves. Don’t ask me why it works, it just does!

I’ve written Knight’s Tour solutions in just about every language I’ve learned since ‘93 including Java, Python, Ruby and Common Lisp. The Common Lisp solution I wrote is by far the most elegant, not necessarily because its written in Common Lisp. It is mostly because I’m now more experienced as a developer and at solving this particular problem

My CL solution is 63 lines of code with comments. If you find a bug you win a free one year subscription to my blog!

#|
The Knight's Tour
Author: Anthony Fairchild
|#

(defun make-chessboard (size-xy)
  "creates a two dimensional array representing a chessboard"
  (make-array (list size-xy size-xy)))

(defun is-valid-move (board pos-x pos-y)
  "Returns true if the given move is valid.  A move is valid if it is
   within the board dimensions and it is not taken by another position."
  (and (< pos-x (array-dimension board 0))
       (< pos-y (array-dimension board 1))
       (>= pos-x 0)(>= pos-y 0)
       (zerop (aref board pos-x pos-y))))

(defun next-valid-moves (board curx cury)
  "returns next 8 possible valid moves"
  (loop for pair in '((-1 2)(-2 1)(1 -2)(2 -1)(-1 -2)(-2 -1)(1 2)(2 1))
        for newx = (+ (first pair) curx)
        for newy = (+ (second pair) cury)
        when (is-valid-move board newx newy)
        collect (list newx newy)))

(defun next-optimized-moves (board curx cury)
  "Sorts the next valid moves with the best moves first.  The best move is
   determined by looking ahead at the next 2 moves and choosing the move
   with the least number of possible moves"
  (sort (next-valid-moves board curx cury)
        #'(lambda (move-a move-b)
            (< (length (next-valid-moves board (first move-a) (second move-a)))
               (length (next-valid-moves board (first move-b) (second move-b)))))))

(defun solve-knights-tour (board posx posy move-num next-moves-fun)
  "Solves the knight's tour recursively. Uses next-move-fun function
to determine next move. Both brute force and optimized methods use
this function as a base."
  (setf (aref board posx posy) move-num)
  (cond ((= move-num (* (array-dimension board 0)
                        (array-dimension board 1))) board)
        ((loop for move in (funcall next-moves-fun board posx posy)
               when (solve-knights-tour board (first move)
                                        (second move) (1+ move-num)
                                        next-moves-fun)
               return t) board)
        (t (setf (aref board posx posy) 0) nil)))

(defun solve-optimized (board posx posy move-num)
  "Solves the knight's tour intelligently by finding the most likely
good position to move to."
  (solve-knights-tour board posx posy move-num #'next-optimized-moves))  

(defun solve-brute-force (board posx posy move-num)
  "Solves the knight's tour using brute force.  This means travel to every
possible position."
  (solve-knights-tour board posx posy move-num #'next-valid-moves))

(defun knights-tour (&key (optimized t)(size-xy 8)(start-x (random size-xy))(start-y (random size-xy)))
  "Return a solution for the knight's tour or nil if no solution could be found"
  (if optimized
      (solve-optimized (make-chessboard size-xy) start-x start-y 1)
      (solve-brute-force (make-chessboard size-xy) start-x start-y 1)))

CL-USER> (time (print-table (knights-tour)))
9 |6 |11|44|27|4 |29|34
--+--+--+--+--+--+--+--
12|43|8 |5 |46|33|26|3
--+--+--+--+--+--+--+--
7 |10|45|48|55|28|35|30
--+--+--+--+--+--+--+--
42|13|54|63|32|47|2 |25
--+--+--+--+--+--+--+--
53|64|49|56|1 |58|31|36
--+--+--+--+--+--+--+--
14|41|62|59|50|19|24|21
--+--+--+--+--+--+--+--
61|52|39|16|57|22|37|18
--+--+--+--+--+--+--+--
40|15|60|51|38|17|20|23

Evaluation took:
  0.006 seconds of real time
  0.004001 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  1,043,200 bytes consed.