# 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]];
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.

Tags

### More like this

##### Ropes: Twining Together Strings for Editors
It's been a while since I've written about any data structures. But it just so happens that I'm actually really working on implementing a really interesting and broadly useful data structure now, called a Rope. A bit of background, to lead in. I've got this love-hate relationship with some of the…
##### Games and Graphs: Searching for Victory
Last time, I showed a way of using a graph to model a particular kind of puzzle via a search graph. Games and puzzles provide a lot of examples of how we can use graphs to model problems. Another example of this is the most basic state-space search that we do in computer science problems. In…
##### Graph Decomposition and Turning Cycles
One thing that we often want to do is break a graph into pieces in a way that preserves the structural relations between the vertices in any part. Doing that is called *decomposing* the graph. Decomposition is a useful technique because many ways of studying the structure of a graph, and many…
##### Haskell: the Basics of Type Classes
One thing that we've seen already in Haskell programs is type classes. Today, we're going to try to take our first look real look at them in detail - both how to use them, and how to define them. This still isn't the entire picture around type-classes; we'll come back for another look at them…

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

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 4x4 board.

By Eric Lund (not verified) on 10 Sep 2007 #permalink

@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.

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 <=n knight moves from a fixed point on the edge.

A006075 Minimal number of knights needed to cover an n X n board.

A006076 Sequence A006075 gives minimal number of knights needed to cover an n X n board. This sequence gives number of inequivalent solutions using A006075(n) knights.

A035008 Total number of possible knight moves on an n+2 X n+2 chessboard, if the knight is placed anywhere.

A079137 Number of knights tour diagrams on a 4 X k chessboard.

A098499 Number of squares on infinite half chessboard at <=n knight moves from a fixed point on the diagonal.

A098500 Number of squares on infinite quarter chessboard at <=n knight moves from the corner.

A098501 Number of squares on infinite octant of chessboard at <=n knight moves from the corner. The octant includes the diagonal.

A110214 Minimal number of knights to cover a cubic board.

A001230 Number of knight's tours on a 2n X 2n chessboard.

Oh, this one above has the useful comment:

"No closed tour exists on an m X m board if m is odd."

REFERENCES

N. D. Elkies and R. P. Stanley, The mathematical knight, Math. Intelligencer, 25 (No. 1, 2003), 22-34.

Brendan McKay (bdm(AT)cs.anu.edu.au), personal communication, Feb 03, 1997.

W. W. Rouse Ball, Mathematical Recreations and Essays (various editions), Chap. 6.

I. Wegener, Branching Programs and Binary Decision Diagrams, SIAM, Philadelphia, 2000; see p. 369.

M. Loebbing and I. Wegener, "The Number of Knight's Tours Equals 33,439,123,484,294 - Counting with Binary Decision Diagrams", Electronic Journal of Combinatorics, Vol. 3, Paper R5 [ Note the comments at the end ].

Eric Weisstein's World of Mathematics, Knight's Tour

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.

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.

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?