{"id":211,"date":"2006-02-26T12:36:08","date_gmt":"2006-02-26T20:36:08","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=211"},"modified":"2006-03-10T21:32:43","modified_gmt":"2006-03-11T05:32:43","slug":"graph-traversal-puzzle","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/graph-traversal-puzzle\/","title":{"rendered":"Graph Traversal Puzzle"},"content":{"rendered":"

Pickover<\/a> came through with a slightly more involved brute force challenge. As usual I’ll spare you the flowery setup (though I did find it curious that it involved a character named Ben trying to reach one named Jennifer) and distill the essential details. Given this graph of values:<\/p>\n

<\/p>\n
\r\n 1  2  3  4  5\r\n 6  7  8  9 10\r\n11 12 13 14 15\r\n16 17 18 19 20\r\n21 22 23 24 25\r\n<\/pre>\n
<\/center><\/p>\n
find a path from any square in column 1 to any square in column 5, moving up, down, left, or right, such that the sum of all squares traversed tallies 90.<\/p>\n
I liked writing this program because it is the most algorithmically interesting thing I have done in a long time, even though I originally solved the wrong problem. The way I originally read the problem, the task was to move from node 1 -> node 5, traversing up, down, left, or right, and find a path where the values sum to 90.<\/p>\n
<\/p>\n
I came up with a recursive solution to try (I think) every possible path starting from node 1. I was amazed, and somewhat suspicious, that it finished nearly immediately. My program found 5 solutions which are all easily verified:<\/p>\n
\r\n   1   6  11  16  17  12   7   8   3   4   5: sum = 90\r\n   1   6  11  12   7   8  13  14   9   4   5: sum = 90\r\n   1   2   7  12  17  18  13   8   3   4   5: sum = 90\r\n   1   2   7   6  11  12  13  14   9  10   5: sum = 90\r\n   1   2   3   8   7  12  13  14  15  10   5: sum = 90\r\n<\/pre>\n
Hey Cliff! You could use this puzzle in next year’s calendar by just altering the setup a little (“Stan, the obsessive-compulsive pothead on square 1, needs to get to his dealer’s house at square 5 but must traverse a path that tallies 90. Help Stan get his fix.”).<\/p>\n
Fortunately, all 5 of those solutions are valid in the context of the problem (square 1 is in column 1 and square 5 is in column 5). I modified the program a little bit to find all valid paths within the parameters of the problem. Actually, the problem never specified that squares cannot be crossed twice. That could make the solution even more complicated. Within my interpretation of the problem, my program found 39 solutions:<\/p>\n
\r\n   1   6  11  16  17  12   7   8   3   4   5: sum = 90\r\n   1   6  11  12   7   8   3   4   9  14  15: sum = 90\r\n   1   6  11  12   7   8  13  14   9   4   5: sum = 90\r\n   1   6   7   2   3   8   9   4   5  10  15  20: sum = 90\r\n   1   6   7  12  13   8   9   4   5  10  15: sum = 90\r\n   1   2   7  12  17  18  13   8   3   4   5: sum = 90\r\n   1   2   7   6  11  12  13  14   9  10   5: sum = 90\r\n   1   2   3   8   7  12  13  14  15  10   5: sum = 90\r\n   6   1   2   7  12  13   8   3   4   9  10  15: sum = 90\r\n   6   1   2   7  12  13  14  15  20: sum = 90\r\n   6   1   2   7   8  13  14  19  20: sum = 90\r\n   6   1   2   3   8  13  18  19  20: sum = 90\r\n   6   1   2   3   8  13  14   9   4   5  10  15: sum = 90\r\n   6   1   2   3   8  13  14  15  10   9   4   5: sum = 90\r\n   6   1   2   3   8   7  12  13  14   9  10   5: sum = 90\r\n   6   1   2   3   4   9   8  13  14  15  10   5: sum = 90\r\n   6   1   2   3   4   5  10   9   8  13  14  15: sum = 90\r\n   6  11  12   7   8  13  14   9  10: sum = 90\r\n   6  11  12  13   8   7   2   3   4   9  10   5: sum = 90\r\n   6  11  12  13  14   9  10  15: sum = 90\r\n   6   7   8   3   4   9  14  19  20: sum = 90\r\n  11   6   1   2   7  12  13  14   9  10   5: sum = 90\r\n  11   6   1   2   7   8   3   4   9  14  15  10: sum = 90\r\n  11   6   1   2   7   8  13  14   9   4   5  10: sum = 90\r\n  11   6   7   2   3   8   9  14  15  10   5: sum = 90\r\n  11   6   7   8   9  14  15  20: sum = 90\r\n  11  16  17  12   7   8   9  10: sum = 90\r\n  11  12   7   8  13  14  15  10: sum = 90\r\n  11  12  13   8   7   2   3   4   5  10  15: sum = 90\r\n  16  11   6   1   2   3   8   9   4   5  10  15: sum = 90\r\n  16  11   6   7   8  13  14  15: sum = 90\r\n  16  11  12   7   6   1   2   3   8   9  10   5: sum = 90\r\n  16  11  12  13  14   9  10   5: sum = 90\r\n  16  17  12   7   6   1   2   3   8   9   4   5: sum = 90\r\n  16  17  12  13   8   9  10   5: sum = 90\r\n  16  17  12  13  14   9   4   5: sum = 90\r\n  16  17  18  13   8   9   4   5: sum = 90\r\n  16  17  18  19  20: sum = 90\r\n  21  16  11   6   1   2   7   8   9   4   5: sum = 90\r\n<\/pre>\n
Pickover’s solution is in there which was just a straight shot across row 4 (16 -> 17 -> 18 -> 19 -> 20). which makes me suspect that he came up with the matrix situation, tallied the numbers across row 4, came up with 90, added again just to be sure, and then crafted the puzzle around the pre-ordained answer.<\/p>\n
Here is my solution program:<\/p>\n
\r\n\/*\r\n * Program to brute force the solution to Cliff Pickover's\r\n * 2006\/02\/11 puzzle.\r\n *\/<\/i><\/font>\r\n\r\n#include <<\/font>stdio.<\/b><\/font>h><\/font>\r\n\r\n#define DIMENSION 5<\/font>\r\n#define TARGET 90<\/font>\r\n\r\ntypedef struct {<\/b><\/font>\r\n    int<\/b><\/font> up;<\/b><\/font>\r\n    int<\/b><\/font> down;<\/b><\/font>\r\n    int<\/b><\/font> left;<\/b><\/font>\r\n    int<\/b><\/font> right;<\/b><\/font>\r\n    int<\/b><\/font> value;<\/b><\/font>\r\n    int<\/b><\/font> marked;<\/b><\/font>\r\n}<\/b><\/font> node;<\/b><\/font>\r\n\r\nstatic<\/b><\/font> node graph[<\/b><\/font>DIMENSION *<\/font> DIMENSION]<\/b><\/font>;<\/b><\/font>\r\nstatic<\/b><\/font> int<\/b><\/font> path[<\/b><\/font>DIMENSION *<\/font> DIMENSION]<\/b><\/font>;<\/b><\/font>\r\nstatic<\/b><\/font> int<\/b><\/font> path_index =<\/font> 0<\/font>;<\/b><\/font>\r\nstatic<\/b><\/font> int<\/b><\/font> sum =<\/font> 0<\/font>;<\/b><\/font>\r\n\r\nstatic<\/b><\/font> void<\/b><\/font> move_to_node(<\/b><\/font>int<\/b><\/font> index)<\/b><\/font>\r\n{<\/b><\/font>\r\n    int<\/b><\/font> i;<\/b><\/font>\r\n\r\n    graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>marked =<\/font> 1<\/font>;<\/b><\/font>\r\n    path[<\/b><\/font>path_index<\/font>+<\/font>+<\/font>]<\/b><\/font> =<\/font> graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>value;<\/b><\/font>\r\n    sum +<\/font>=<\/font> graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>value;<\/b><\/font>\r\n\r\n    if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>up !<\/font>=<\/font> -<\/font>1<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> (<\/b><\/font>!<\/font>graph[<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>up]<\/b><\/font>.<\/b><\/font>marked)<\/b><\/font>)<\/b><\/font> {<\/b><\/font>\r\n        move_to_node(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>up)<\/b><\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n    if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>down !<\/font>=<\/font> -<\/font>1<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> (<\/b><\/font>!<\/font>graph[<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>down]<\/b><\/font>.<\/b><\/font>marked)<\/b><\/font>)<\/b><\/font> {<\/b><\/font>\r\n        move_to_node(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>down)<\/b><\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n    if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>left !<\/font>=<\/font> -<\/font>1<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> (<\/b><\/font>!<\/font>graph[<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>left]<\/b><\/font>.<\/b><\/font>marked)<\/b><\/font>)<\/b><\/font> {<\/b><\/font>\r\n        move_to_node(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>left)<\/b><\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n    if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>right !<\/font>=<\/font> -<\/font>1<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> (<\/b><\/font>!<\/font>graph[<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>right]<\/b><\/font>.<\/b><\/font>marked)<\/b><\/font>)<\/b><\/font> {<\/b><\/font>\r\n        move_to_node(<\/b><\/font>graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>right)<\/b><\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n\r\n    \/* check the path *\/<\/i><\/font>\r\n    if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>sum =<\/font>=<\/font> TARGET)<\/b><\/font> <\/font>&<\/font>&<\/font>\r\n       (<\/b><\/font>(<\/b><\/font>path[<\/b><\/font>path_index -<\/font> 1<\/font>]<\/b><\/font> =<\/font>=<\/font>  5<\/font>)<\/b><\/font> <\/font>|<\/font>|<\/font>\r\n        (<\/b><\/font>path[<\/b><\/font>path_index -<\/font> 1<\/font>]<\/b><\/font> =<\/font>=<\/font> 10<\/font>)<\/b><\/font> <\/font>|<\/font>|<\/font>\r\n        (<\/b><\/font>path[<\/b><\/font>path_index -<\/font> 1<\/font>]<\/b><\/font> =<\/font>=<\/font> 15<\/font>)<\/b><\/font> <\/font>|<\/font>|<\/font>\r\n        (<\/b><\/font>path[<\/b><\/font>path_index -<\/font> 1<\/font>]<\/b><\/font> =<\/font>=<\/font> 20<\/font>)<\/b><\/font> <\/font>|<\/font>|<\/font>\r\n        (<\/b><\/font>path[<\/b><\/font>path_index -<\/font> 1<\/font>]<\/b><\/font> =<\/font>=<\/font> 25<\/font>)<\/b><\/font>)<\/b><\/font>)<\/b><\/font> {<\/b><\/font>\r\n        \/* valid path found; print the path *\/<\/i><\/font>\r\n        for<\/b><\/font> (<\/b><\/font>i =<\/font> 0<\/font>;<\/b><\/font> i <<\/font> path_index;<\/b><\/font> i<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n            printf(<\/b><\/font>\" %3d\"<\/font>,<\/b><\/font> path[<\/b><\/font>i]<\/b><\/font>)<\/b><\/font>;<\/b><\/font>\r\n        printf(<\/b><\/font>\": sum = %d\\n\"<\/font>,<\/b><\/font> sum)<\/b><\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n\r\n    \/* erase the tracks *\/<\/i><\/font>\r\n    graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>marked =<\/font> 0<\/font>;<\/b><\/font>\r\n    path_index<\/font>-<\/font>-<\/font>;<\/b><\/font>\r\n    sum -<\/font>=<\/font> graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>value;<\/b><\/font>\r\n}<\/b><\/font>\r\n\r\nint<\/b><\/font> main(<\/b><\/font>int<\/b><\/font> argc,<\/b><\/font> char<\/b><\/font> *<\/font>argv[<\/b><\/font>]<\/b><\/font>)<\/b><\/font>\r\n{<\/b><\/font>\r\n    int<\/b><\/font> column,<\/b><\/font> row;<\/b><\/font>\r\n    int<\/b><\/font> index =<\/font> 0<\/font>;<\/b><\/font>\r\n\r\n    \/* set up the graph *\/<\/i><\/font>\r\n    for<\/b><\/font> (<\/b><\/font>row =<\/font> 0<\/font>;<\/b><\/font> row <<\/font> DIMENSION;<\/b><\/font> row<\/font>+<\/font>+<\/font>)<\/b><\/font> {<\/b><\/font>\r\n        for<\/b><\/font> (<\/b><\/font>column =<\/font> 0<\/font>;<\/b><\/font> column <<\/font> DIMENSION;<\/b><\/font> column<\/font>+<\/font>+<\/font>)<\/b><\/font> {<\/b><\/font>\r\n            if<\/b><\/font> (<\/b><\/font>row ><\/font> 0<\/font>)<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>up =<\/font> index -<\/font> DIMENSION;<\/b><\/font>\r\n            else<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>up =<\/font> -<\/font>1<\/font>;<\/b><\/font>\r\n\r\n            if<\/b><\/font> (<\/b><\/font>row <<\/font> DIMENSION -<\/font> 1<\/font>)<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>down =<\/font> index +<\/font> DIMENSION;<\/b><\/font>\r\n            else<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>down =<\/font> -<\/font>1<\/font>;<\/b><\/font>\r\n\r\n            if<\/b><\/font> (<\/b><\/font>column ><\/font> 0<\/font>)<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>left =<\/font> index -<\/font> 1<\/font>;<\/b><\/font>\r\n            else<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>left =<\/font> -<\/font>1<\/font>;<\/b><\/font>\r\n\r\n            if<\/b><\/font> (<\/b><\/font>column <<\/font> DIMENSION -<\/font> 1<\/font>)<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>right =<\/font> index +<\/font> 1<\/font>;<\/b><\/font>\r\n            else<\/b><\/font>\r\n                graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>right =<\/font> -<\/font>1<\/font>;<\/b><\/font>\r\n\r\n            graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>value =<\/font> index +<\/font> 1<\/font>;<\/b><\/font>\r\n            graph[<\/b><\/font>index]<\/b><\/font>.<\/b><\/font>marked =<\/font> 0<\/font>;<\/b><\/font>\r\n            index<\/font>+<\/font>+<\/font>;<\/b><\/font>\r\n        }<\/b><\/font>\r\n    }<\/b><\/font>\r\n\r\n    move_to_node(<\/b><\/font>0<\/font>)<\/b><\/font>;<\/b><\/font>  \/* start from node 1 *\/<\/i><\/font>\r\n    move_to_node(<\/b><\/font>5<\/font>)<\/b><\/font>;<\/b><\/font>  \/* start from node 6 *\/<\/i><\/font>\r\n    move_to_node(<\/b><\/font>10<\/font>)<\/b><\/font>;<\/b><\/font>  \/* start from node 11 *\/<\/i><\/font>\r\n    move_to_node(<\/b><\/font>15<\/font>)<\/b><\/font>;<\/b><\/font>  \/* start from node 16 *\/<\/i><\/font>\r\n    move_to_node(<\/b><\/font>20<\/font>)<\/b><\/font>;<\/b><\/font>  \/* start from node 21 *\/<\/i><\/font>\r\n\r\n    return<\/b><\/font> 0<\/font>;<\/b><\/font>\r\n}<\/b><\/font>\r\n<\/pre>\n
Code colorized by the CodeColorizer<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
Finally, something a bit more complicated…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[27],"tags":[],"class_list":["post-211","post","type-post","status-publish","format-standard","hentry","category-pickover-puzzles"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/211","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/comments?post=211"}],"version-history":[{"count":0,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/211\/revisions"}],"wp:attachment":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/media?parent=211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/categories?post=211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/tags?post=211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}