Puzzling Graphs: Problem Modeling with Graphs

As I've mentioned before, the real use of graphs is as models. Many real problems can be
described using graphs as models - that is, to translate the problem into a graph, solve some problem on the graph, and then translate the result back from the graph to the original problem. This kind of
solution is extremely common, and can come up in some unexpected places.

For example, there's a classic chess puzzle called the Knight's tour.
In the Knight's tour, you have a chessboard, completely empty except for a knight on one square. You can
move the knight the way you normally can in chess, and you want to find a sequence of moves in which is
visits every square on the chessboard exactly once. There are variations of the puzzle for non-standard
chessboards - boards larger or smaller than normal, toroidal boards (where you can wrap around the left edge to the right, or the top to the botton), etc. So - given a particular board, how can you
(1) figure out if it's possible to do a knights tour, and (2) find the sequence of moves in a tour
if one exists?

As a reminder, t
he basic knight's move on a chessboard is illustrated in the diagram to the side. The way it works is, a knight can move one two squares in one direction, and one squareperpendicular to that direction. From a given spot far from the edges of the board, a knight can move to 8 different destination squares.

Trying to solve the moves for a knight's tour is frustrating - as it often is for puzzles with so many possible solutions. You need to figure out what the real underlying constraints of the puzzle are - trial and error isn't going to get you very far unless you're awfully lucky. Writing a program to solve it
isn't too hard - but it's very error prone, unless you're playing on a toroidal board. The edge cases - the places where some of the 8 possible moves are cut off by the edge of the board - are classic examples
of the kind of place where people make off-by-one errors. And the tangling of finding possible
moves with the logic of searching the possible solution space makes it extremely messy - increasing the
odds of an error creeping in. And even if you get it right, most programs search for a solution even
in cases where it should be obvious that there is no solution. For example, on a 3x3, there's definitely
no possible solution.

For example, here's a basic Knight's tour in Haskell:

module Knights where

import Data.List

type Square = (Int, Int)

-- Possible knight moves from a given square on an nxn board
knightMoves :: Int -> Square -> [Square]
knightMoves n (x, y) = filter (onBoard n)
        [(x+2, y+1), (x+2, y-1), (x+1, y+2), (x+1, y-2),
         (x-1, y+2), (x-1, y-2), (x-2, y+1), (x-2, y-1)]

-- Is the square within an nxn board?
onBoard :: Int -> Square -> Bool
onBoard n (x, y) = 1 <= x && x <= n && 1 <= y && y <= n

-- Knight's tours on an nxn board ending at the given square
knightsTo :: Int -> Square -> [[Square]]
knightsTo n finish = [pos:path | (pos, path) <- tour (n*n)]
  where tour 1 = [(finish, [])]
        tour k = [(pos', pos:path) |
                (pos, path) <- tour (k-1),
                pos' <- sortImage (entrances path)
                        (filter (`notElem` path) (knightMoves n pos))]
        entrances path pos =
                length (filter (`notElem` path) (knightMoves n pos))

-- Closed knight's tours on an nxn board
closedKnights :: Int -> [[Square]]
closedKnights n = [pos:path | (pos, path) <- tour (n*n), pos == start]
  where tour 1 = [(finish, [])]
        tour k = [(pos', pos:path) |
                (pos, path) <- tour (k-1),
                pos' <- sortImage (entrances path)
                        (filter (`notElem` path) (knightMoves n pos))]
        entrances path pos
          | pos == start = 100  -- don't visit start until there are no others
          | otherwise = length (filter (`notElem` path) (knightMoves n pos))
        start = (1,1)
        finish = (2,3)

-- Sort by comparing the image of list elements under a function f.
-- These images are saved to avoid recomputation.
sortImage :: Ord b => (a -> b) -> [a] -> [a]
sortImage f xs = map snd (sortBy cmpFst [(f x, x) | x <- xs])
  where cmpFst x y = compare (fst x) (fst y)

The better solution is to use a graph to solve the problem. This separates the problem of understanding the structure of the search space from actually searching that space. What we do is take the chessboard, and name each square. We create a graph where there is a one-to-one mapping between vertices of the graph, and squares on the chessboard. Then we put edges between two vertices A and B if and only if there is a knight's move between the squares A and B on the chessboard. For example, see the picture below for an example of doing this on a 4×4 chessboard.

Once you've got the graph, then finding a Knight's tour is just finding a Hamiltonian path through the graph. That's not quite trivial - but generating the graph from the chessboard is easy, and Hamiltonian searches are common - you can find Hamilton path code in almost any standard graph library. Even if you need to write it yourself - there's no worry about off-by-one errors in the search. The search
is much easier to write. For contrast, the following is a mathematica program for Hamiltonian paths. (I couldn't find a Haskell example, but the Mathematica is close in style, so it's a reasonable
comparison.)

HamiltonianPath[g_Graph] := HamiltonianPath[g, One]
HamiltonianPath[g_Graph, One] := 
        Module[{c = HamiltonianCycle[g], nonEdges, p, q},
               If[c != {}, 
                  Drop[c, -1],
                  nonEdges = Complement[Flatten[Table[{i, j}, {i, V[g]-1}, {j, i+1, V[g]}],1], Edges[g]];
                  Do[h = AddEdges[g, nonEdges[[i]]]; 
                     If[((BiconnectedQ[h]) && ((c = HamiltonianCycle[h]) != {})),
                        p = Position[c = Drop[c,-1], nonEdges[[i, 1]]][[1, 1]];
                        c = RotateLeft[c, p-1];
                        If[nonEdges[[i, 2]] == c[[2]], c = RotateLeft[c, 1]];
                        Break[]
                     ],
                     {i, Length[nonEdges]}
                  ];
                  c
               ]
        ]

The problem has basically become easier, because you've separated
the problem into two disjoint pieces, each of which is easy to solve, and you've made the logic of
the search much clearer. And if you look at the graphical form, you can see the structure much more clearly - which means you can more easily search it to see if there's anything making a path impossible. It's much easire to understand in graph form. For example, go back to the 3×3 grid. If you try to turn that into a graph, you'll find that it's not connected. The middle square is isolated. You can't have a Hamiltonian path over a disconnected graph.