{"id":218,"date":"2006-03-10T22:12:35","date_gmt":"2006-03-11T06:12:35","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=218"},"modified":"2006-03-11T12:05:38","modified_gmt":"2006-03-11T20:05:38","slug":"beaten-by-a-puzzle","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/beaten-by-a-puzzle\/","title":{"rendered":"Beaten By A Puzzle"},"content":{"rendered":"

It pains me to admit that I couldn’t even produce a computer program capable of solving a Pickover puzzle<\/a> (update:<\/strong> But Aurel Jacobs could; read on). This is another graph traversal puzzle. The setup is that you have an 8×9 graph with 8 blocked nodes:<\/p>\n

<\/p>\n
\r\n* * * * * * * *\r\n* X * * * * * *\r\n* * * X * X * *\r\n* * * * * * * *\r\n* * X * * * * *\r\n* * * * * * * *\r\n* X * * * * * *\r\n* * * X * * * *\r\n* * X X * * * *\r\n<\/pre>\n
<\/center><\/p>\n
Find a path that begins and ends on the same node that covers every unblocked square without crossing itself and moving only vertically or horizontally.<\/p>\n
<\/p>\n
I started with the brute-force, depth-first graph traversal code from the February 26<\/a> puzzle. I modified it and tested it to perform the specified puzzle task, but for a 3×3 graph with the middle node blocked out. The program performs correctly and produces some pretty ASCII output, if I do say so myself:<\/p>\n
\r\nsolution 1:\r\n v < <\r\n v X ^\r\n > > ^\r\n\r\nsolution 2:\r\n > > v\r\n ^ X v\r\n ^ < <\r\n<\/pre>\n
For some reason, the program can’t solve the full puzzle, and it takes 15+ minutes on my AMD64-3400 CPU to chew through all possible paths. The puzzle does show a solution on the back of the day’s calendar page (which I do not have with me at the moment, unfortunately). I’m not especially motivated to keep working at this one since it takes so long to traverse all paths.<\/p>\n
I’m disappointed. Here’s the code anyway:<\/p>\n
UPDATE:<\/strong> Forget my code, Aurel Jacobs came up with a workable solution that only takes about 82 seconds on my machine to find a solution. Here is the solution his program found:<\/p>\n
<\/p>\n
\r\n> > > > > v > v\r\no X v < < > ^ v\r\n^ v < X ^ X v <\r\n^ > > v ^ < > v\r\n^ < X > v ^ < <\r\n> ^ v < > > > v\r\n^ X v ^ < v < <\r\n^ v < X ^ > > v\r\n^ < X X ^ < < <\r\n<\/pre>\n
<\/center><\/p>\n
Here is his code:<\/p>\n
\r\n\r\n#include <<\/font>stdio.<\/b><\/font>h><\/font>\r\n\r\n#define GRID_W 8<\/font>\r\n#define GRID_H 9<\/font>\r\n\r\nstatic<\/b><\/font> char<\/b><\/font> grid[<\/b><\/font>GRID_H]<\/b><\/font>[<\/b><\/font>GRID_W]<\/b><\/font> =<\/font>\r\n  {<\/b><\/font> {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font>,<\/b><\/font>\r\n    {<\/b><\/font>'*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> 'X',<\/b><\/font> 'X',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>',<\/b><\/font> '*<\/font>'}<\/b><\/font> }<\/b><\/font>;<\/b><\/font>\r\n\r\nstatic<\/b><\/font> void<\/b><\/font> disp (<\/b><\/font>void<\/b><\/font>)<\/b><\/font>\r\n{<\/b><\/font>\r\n  int<\/b><\/font> x,<\/b><\/font> y;<\/b><\/font>\r\n\r\n  for<\/b><\/font> (<\/b><\/font>y=<\/font>0<\/font>;<\/b><\/font> y<<\/font>GRID_H;<\/b><\/font> y<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n    {<\/b><\/font>\r\n      for<\/b><\/font> (<\/b><\/font>x=<\/font>0<\/font>;<\/b><\/font> x<<\/font>GRID_W;<\/b><\/font> x<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n        printf (<\/b><\/font>\"%c \"<\/font>,<\/b><\/font> grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font>)<\/b><\/font>;<\/b><\/font>\r\n      printf (<\/b><\/font>\"\\n\"<\/font>)<\/b><\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n}<\/b><\/font>\r\n\r\nstatic<\/b><\/font> int<\/b><\/font> nb_node (<\/b><\/font>void<\/b><\/font>)<\/b><\/font>\r\n{<\/b><\/font>\r\n  int<\/b><\/font> x,<\/b><\/font> y;<\/b><\/font>\r\n  int<\/b><\/font> count =<\/font> 0<\/font>;<\/b><\/font>\r\n  for<\/b><\/font> (<\/b><\/font>y=<\/font>0<\/font>;<\/b><\/font> y<<\/font>GRID_H;<\/b><\/font> y<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n\r\n    for<\/b><\/font> (<\/b><\/font>x=<\/font>0<\/font>;<\/b><\/font> x<<\/font>GRID_W;<\/b><\/font> x<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n      if<\/b><\/font> (<\/b><\/font>grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font>=<\/font> '*<\/font>')<\/b><\/font>\r\n        count<\/font>+<\/font>+<\/font>;<\/b><\/font>;<\/b><\/font>\r\n  return<\/b><\/font> count;<\/b><\/font>\r\n}<\/b><\/font>\r\n\r\nstatic<\/b><\/font> int<\/b><\/font> check (<\/b><\/font>int<\/b><\/font> x,<\/b><\/font> int<\/b><\/font> y,<\/b><\/font> int<\/b><\/font> n)<\/b><\/font>\r\n{<\/b><\/font>\r\n  int<\/b><\/font> ret =<\/font> 1<\/font>;<\/b><\/font>\r\n\r\n  if<\/b><\/font> (<\/b><\/font>grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> !<\/font>=<\/font> '*<\/font>')<\/b><\/font>\r\n    return<\/b><\/font> 0<\/font>;<\/b><\/font>\r\n\r\n  grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font> 'o';<\/b><\/font>\r\n\r\n  if<\/b><\/font> (<\/b><\/font><\/font>-<\/font>-<\/font>n <<\/font>=<\/font> 0<\/font>)<\/b><\/font>\r\n    return<\/b><\/font> 1<\/font>;<\/b><\/font>\r\n  if<\/b><\/font> (<\/b><\/font>x ><\/font> 0<\/font> <\/font>&<\/font>&<\/font> check (<\/b><\/font>x-<\/font>1<\/font>,<\/b><\/font> y,<\/b><\/font> n)<\/b><\/font>)<\/b><\/font>\r\n    grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font> '<<\/font>';<\/b><\/font>\r\n  else<\/b><\/font> if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>x <<\/font> GRID_W-<\/font>1<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> check (<\/b><\/font>x+<\/font>1<\/font>,<\/b><\/font> y,<\/b><\/font> n)<\/b><\/font>)<\/b><\/font>\r\n    grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font> '><\/font>';<\/b><\/font>\r\n  else<\/b><\/font> if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>y ><\/font> 0<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> check (<\/b><\/font>x,<\/b><\/font> y-<\/font>1<\/font>,<\/b><\/font> n)<\/b><\/font>)<\/b><\/font>\r\n    grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font> '^<\/font>';<\/b><\/font>\r\n  else<\/b><\/font> if<\/b><\/font> (<\/b><\/font>(<\/b><\/font>y <<\/font> GRID_H-<\/font>1<\/font>)<\/b><\/font> <\/font>&<\/font>&<\/font> check (<\/b><\/font>x,<\/b><\/font> y+<\/font>1<\/font>,<\/b><\/font> n)<\/b><\/font>)<\/b><\/font>\r\n    grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font> 'v';<\/b><\/font>\r\n  else<\/b><\/font>\r\n    {<\/b><\/font>\r\n      grid[<\/b><\/font>y]<\/b><\/font>[<\/b><\/font>x]<\/b><\/font> =<\/font> '*<\/font>';<\/b><\/font>\r\n      ret =<\/font> 0<\/font>;<\/b><\/font>\r\n    }<\/b><\/font>\r\n\r\n  return<\/b><\/font> ret;<\/b><\/font>\r\n}<\/b><\/font>\r\n\r\nint<\/b><\/font> main (<\/b><\/font>void<\/b><\/font>)<\/b><\/font>\r\n{<\/b><\/font>\r\n  int<\/b><\/font> x,<\/b><\/font> y,<\/b><\/font> n;<\/b><\/font>\r\n\r\n  n =<\/font> nb_node (<\/b><\/font>)<\/b><\/font>;<\/b><\/font>\r\n\r\n  for<\/b><\/font> (<\/b><\/font>y=<\/font>0<\/font>;<\/b><\/font> y<<\/font>GRID_H;<\/b><\/font> y<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n    for<\/b><\/font> (<\/b><\/font>x=<\/font>0<\/font>;<\/b><\/font> x<<\/font>GRID_W;<\/b><\/font> x<\/font>+<\/font>+<\/font>)<\/b><\/font>\r\n      if<\/b><\/font> (<\/b><\/font>check (<\/b><\/font>x,<\/b><\/font> y,<\/b><\/font> n)<\/b><\/font>)<\/b><\/font>\r\n        {<\/b><\/font>\r\n          disp (<\/b><\/font>)<\/b><\/font>;<\/b><\/font>\r\n          return<\/b><\/font> 0<\/font>;<\/b><\/font>\r\n        }<\/b><\/font>\r\n\r\n  printf (<\/b><\/font>\"No solution found\\n\"<\/font>)<\/b><\/font>;<\/b><\/font>\r\n  return<\/b><\/font> 1<\/font>;<\/b><\/font>\r\n}<\/b><\/font><\/pre>\n
Code colorized by the CodeColorizer<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
Not even a computer can solve this one?<\/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-218","post","type-post","status-publish","format-standard","hentry","category-pickover-puzzles"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t