Beaten By A Puzzle

It pains me to admit that I couldn’t even produce a computer program capable of solving a Pickover puzzle (update: 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:

* * * * * * * *
* X * * * * * *
* * * X * X * *
* * * * * * * *
* * X * * * * *
* * * * * * * *
* X * * * * * *
* * * X * * * *
* * X X * * * *

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.

I started with the brute-force, depth-first graph traversal code from the February 26 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:

solution 1:
 v < <
 v X ^
 > > ^

solution 2:
 > > v
 ^ X v
 ^ < <

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.

I’m disappointed. Here’s the code anyway:

UPDATE: 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:

> > > > > v > v
o X v < < > ^ v
^ v < X ^ X v <
^ > > v ^ < > v
^ < X > v ^ < <
> ^ v < > > > v
^ X v ^ < v < <
^ v < X ^ > > v
^ < X X ^ < < <

Here is his code:


#include <stdio.h>

#define GRID_W 8
#define GRID_H 9

static char grid[GRID_H][GRID_W] =
  { {'*', '*', '*', '*', '*', '*', '*', '*'},
    {'*', 'X', '*', '*', '*', '*', '*', '*'},
    {'*', '*', '*', 'X', '*', 'X', '*', '*'},
    {'*', '*', '*', '*', '*', '*', '*', '*'},
    {'*', '*', 'X', '*', '*', '*', '*', '*'},
    {'*', '*', '*', '*', '*', '*', '*', '*'},
    {'*', 'X', '*', '*', '*', '*', '*', '*'},
    {'*', '*', '*', 'X', '*', '*', '*', '*'},
    {'*', '*', 'X', 'X', '*', '*', '*', '*'} };

static void disp (void)
{
  int x, y;

  for (y=0; y<GRID_H; y++)
    {
      for (x=0; x<GRID_W; x++)
        printf ("%c ", grid[y][x]);
      printf ("\n");
    }
}

static int nb_node (void)
{
  int x, y;
  int count = 0;
  for (y=0; y<GRID_H; y++)

    for (x=0; x<GRID_W; x++)
      if (grid[y][x] == '*')
        count++;;
  return count;
}

static int check (int x, int y, int n)
{
  int ret = 1;

  if (grid[y][x] != '*')
    return 0;

  grid[y][x] = 'o';

  if (--n <= 0)
    return 1;
  if (x > 0 && check (x-1, y, n))
    grid[y][x] = '<';
  else if ((x < GRID_W-1) && check (x+1, y, n))
    grid[y][x] = '>';
  else if ((y > 0) && check (x, y-1, n))
    grid[y][x] = '^';
  else if ((y < GRID_H-1) && check (x, y+1, n))
    grid[y][x] = 'v';
  else
    {
      grid[y][x] = '*';
      ret = 0;
    }

  return ret;
}

int main (void)
{
  int x, y, n;

  n = nb_node ();

  for (y=0; y<GRID_H; y++)
    for (x=0; x<GRID_W; x++)
      if (check (x, y, n))
        {
          disp ();
          return 0;
        }

  printf ("No solution found\n");
  return 1;
}

Code colorized by the CodeColorizer.