{"id":507,"date":"2007-09-10T09:00:00","date_gmt":"2007-09-10T09:00:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/09\/10\/puzzling-graphs-problem-modeling-with-graphs\/"},"modified":"2007-09-10T09:00:00","modified_gmt":"2007-09-10T09:00:00","slug":"puzzling-graphs-problem-modeling-with-graphs","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/09\/10\/puzzling-graphs-problem-modeling-with-graphs\/","title":{"rendered":"Puzzling Graphs: Problem Modeling with Graphs"},"content":{"rendered":"

As I’ve mentioned before, the real use of graphs is as models<\/em>. Many real problems can be
\ndescribed 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
\nsolution is extremely common, and can come up in some unexpected places.<\/p>\n

For example, there’s a classic chess puzzle called the Knight’s tour.<\/a>
\nIn the Knight’s tour, you have a chessboard, completely empty except for a knight on one square. You can
\nmove the knight the way you normally can in chess, and you want to find a sequence of moves in which is
\nvisits every square on the chessboard exactly once. There are variations of the puzzle for non-standard
\nchessboards – 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
\n(1) figure out if it’s possible to do a knights tour, and (2) find the sequence of moves in a tour
\nif one exists?<\/p>\n

<\/p>\n

As a reminder, t\"knights-moves.png\"
\nhe basic knight’s move on a chessboard is illustrated in the diagram to the side. \tThe way it works is, a knight can move one two squares in one direction, and one square\tperpendicular to that direction. From a given spot far from the edges of the board, a knight can move to 8 different destination squares. <\/p>\n

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
\nisn’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
\nof the kind of place where people make off-by-one errors. And the tangling of finding possible
\nmoves with the logic of searching the possible solution space makes it extremely messy – increasing the
\nodds of an error creeping in. And even if you get it right, most programs search for a solution even
\nin cases where it should be obvious that there is no solution. For example, on a 3×3, there’s definitely
\nno possible solution.<\/p>\n

For example, here’s a basic Knight’s tour in Haskell:<\/p>\n

\nmodule Knights where\nimport Data.List\ntype Square = (Int, Int)\n-- Possible knight moves from a given square on an nxn board\nknightMoves :: Int -> Square -> [Square]\nknightMoves n (x, y) = filter (onBoard n)\n[(x+2, y+1), (x+2, y-1), (x+1, y+2), (x+1, y-2),\n(x-1, y+2), (x-1, y-2), (x-2, y+1), (x-2, y-1)]\n-- Is the square within an nxn board?\nonBoard :: Int -> Square -> Bool\nonBoard n (x, y) = 1 <= x && x <= n && 1 <= y && y <= n\n-- Knight's tours on an nxn board ending at the given square\nknightsTo :: Int -> Square -> [[Square]]\nknightsTo n finish = [pos:path | (pos, path) <- tour (n*n)]\nwhere tour 1 = [(finish, [])]\ntour k = [(pos', pos:path) |\n(pos, path) <- tour (k-1),\npos' <- sortImage (entrances path)\n(filter (`notElem` path) (knightMoves n pos))]\nentrances path pos =\nlength (filter (`notElem` path) (knightMoves n pos))\n-- Closed knight's tours on an nxn board\nclosedKnights :: Int -> [[Square]]\nclosedKnights n = [pos:path | (pos, path) <- tour (n*n), pos == start]\nwhere tour 1 = [(finish, [])]\ntour k = [(pos', pos:path) |\n(pos, path) <- tour (k-1),\npos' <- sortImage (entrances path)\n(filter (`notElem` path) (knightMoves n pos))]\nentrances path pos\n| pos == start = 100  -- don't visit start until there are no others\n| otherwise = length (filter (`notElem` path) (knightMoves n pos))\nstart = (1,1)\nfinish = (2,3)\n-- Sort by comparing the image of list elements under a function f.\n-- These images are saved to avoid recomputation.\nsortImage :: Ord b => (a -> b) -> [a] -> [a]\nsortImage f xs = map snd (sortBy cmpFst [(f x, x) | x <- xs])\nwhere cmpFst x y = compare (fst x) (fst y)\n<\/pre>\n
 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.<\/p>\n
\"knights-graph.png\"<\/p>\n
 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
\nis 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
\ncomparison.)<\/p>\n
\nHamiltonianPath[g_Graph] := HamiltonianPath[g, One]\nHamiltonianPath[g_Graph, One] :=\nModule[{c = HamiltonianCycle[g], nonEdges, p, q},\nIf[c != {},\nDrop[c, -1],\nnonEdges = Complement[Flatten[Table[{i, j}, {i, V[g]-1}, {j, i+1, V[g]}],1], Edges[g]];\nDo[h = AddEdges[g, nonEdges[[i]]];\nIf[((BiconnectedQ[h]) && ((c = HamiltonianCycle[h]) != {})),\np = Position[c = Drop[c,-1], nonEdges[[i, 1]]][[1, 1]];\nc = RotateLeft[c, p-1];\nIf[nonEdges[[i, 2]] == c[[2]], c = RotateLeft[c, 1]];\nBreak[]\n],\n{i, Length[nonEdges]}\n];\nc\n]\n]\n<\/pre>\n
 The problem has basically become easier, because you’ve separated
\nthe problem into two disjoint pieces, each of which is easy to solve, and you’ve made the logic of
\nthe 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-507","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-8b","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/507","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=507"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/507\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=507"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=507"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=507"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}