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, tknights-moves.png
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 square perpendicular 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 3×3, 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.

knights-graph.png

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.

0 thoughts on “Puzzling Graphs: Problem Modeling with Graphs

  1. JR

    Is there a way from looking at the graph that there is or isn’t a solution besides the 3×3 case of disconnection? I don’t believe the 4×4 shown has a solution either, does it?

    Reply
  2. Eric Lund

    Is there a way from looking at the graph that there is or isn’t a solution…?

    Yes. Look at the cycle A-G-P-J on the left-hand side of the graph, and D-F-M-K on the right. You see that A and P are connected only to G and J. Therefore any tour which includes both A and P must visit either G twice or J twice. Similarly, any tour which includes both D and M must visit either F twice or K twice. These paths violate the assumption that each node must be visited exactly once, and therefore no tour is possible on a 4×4 board.

    Reply
  3. Eric

    @Eric Lund,
    Well, your argument is salient, but not quite sufficient. If the tour were to start at A, you could then go to G to P to J and cover the left-hand side. The tour mustthen end with the diamond on the right of the graph, say going from K to D to F and finally ending up at M.
    Then the question is whether you can bridge that gap b/w the starting sequence and the ending sequence, and I don’t think you can. There’s a cycle from H to I to O to B. And there’s another cycle from N to L to C to E. But you can’t seem to move b/w those two cycles without going through G, J, F, or K, and once you hit one of those, you’d have to go through the ending sequence.

    Reply
  4. Jonathan Vos Post

    This is a particularly rich area of classical Recreational mathematics.
    At the Online Encyclopedia of Integer Sequences, see:
    A068608 Path of a knight’s tour on an infinite chess board.
    A098498 Number of squares on infinite half chessboard at

    Reply
  5. Paul

    Jonathan,
    I’m not familiar with the way to mention academic papers (I’ve read a grand total of two in my lifetime), were those 11 different papers you mentioned, or just 11 different chapters?
    I don’t suppose that what you mentioned is freely available over the Internet?
    It all sounds fascinating, but I’m at a loss as how to learn more.

    Reply
  6. Jonathan Vos Post

    Paul: “were those 11 different papers you mentioned”
    Sorry. My point was poorly made. The Online Encyclopedia of Integer Sequences (Google that, or google “OEIS”) is entrely on-line, and has far over 100,000 web pages. Wikipedia has an article about it, as the Googling reveals.
    If a listing at OEIS constitutes a paper, then I’d have 1687 papers at OEIS, which would give me over 2,500 publications presentations, and broadcasts. So an OEIS page is much less than a paper, but how much less is hard to say.
    The hotlink for the first one I listed is:
    http://www.research.att.com/~njas/sequences/A068608
    The condition of the early 21st century is that there are now MANY ways to learn Math, of which blogs, wikis, on-line encyclopedias, and the like are relative newcomers (to books and academic papers and classrooms) but clearly of vast importance.

    Reply
  7. Tiago S.

    Mark,
    I’d like to hear an opinion from you and your readers.. I’ve to implement a Bloxorz puzzles creator/solver in three different programming paradigms: logical and functional and OO. The first one I already did in Prolog, using A*.
    Here is my question: What would you use to model the solver using using other idea than A*?
    Why not A*? Because I think that it’ll be trivial to re-implement A* in lisp, so I’d like to use something else I can learn much more.
    Any ideas?
    Thanks in advance,
    Tiago S.

    Reply

Leave a Reply to Jonathan Vos Post Cancel reply