# Graph Traversal Puzzle

February 26th, 2006 by Multimedia MikePickover 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

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.

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.

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:

1 6 11 16 17 12 7 8 3 4 5: sum = 90 1 6 11 12 7 8 13 14 9 4 5: sum = 90 1 2 7 12 17 18 13 8 3 4 5: sum = 90 1 2 7 6 11 12 13 14 9 10 5: sum = 90 1 2 3 8 7 12 13 14 15 10 5: sum = 90

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.”).

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:

1 6 11 16 17 12 7 8 3 4 5: sum = 90 1 6 11 12 7 8 3 4 9 14 15: sum = 90 1 6 11 12 7 8 13 14 9 4 5: sum = 90 1 6 7 2 3 8 9 4 5 10 15 20: sum = 90 1 6 7 12 13 8 9 4 5 10 15: sum = 90 1 2 7 12 17 18 13 8 3 4 5: sum = 90 1 2 7 6 11 12 13 14 9 10 5: sum = 90 1 2 3 8 7 12 13 14 15 10 5: sum = 90 6 1 2 7 12 13 8 3 4 9 10 15: sum = 90 6 1 2 7 12 13 14 15 20: sum = 90 6 1 2 7 8 13 14 19 20: sum = 90 6 1 2 3 8 13 18 19 20: sum = 90 6 1 2 3 8 13 14 9 4 5 10 15: sum = 90 6 1 2 3 8 13 14 15 10 9 4 5: sum = 90 6 1 2 3 8 7 12 13 14 9 10 5: sum = 90 6 1 2 3 4 9 8 13 14 15 10 5: sum = 90 6 1 2 3 4 5 10 9 8 13 14 15: sum = 90 6 11 12 7 8 13 14 9 10: sum = 90 6 11 12 13 8 7 2 3 4 9 10 5: sum = 90 6 11 12 13 14 9 10 15: sum = 90 6 7 8 3 4 9 14 19 20: sum = 90 11 6 1 2 7 12 13 14 9 10 5: sum = 90 11 6 1 2 7 8 3 4 9 14 15 10: sum = 90 11 6 1 2 7 8 13 14 9 4 5 10: sum = 90 11 6 7 2 3 8 9 14 15 10 5: sum = 90 11 6 7 8 9 14 15 20: sum = 90 11 16 17 12 7 8 9 10: sum = 90 11 12 7 8 13 14 15 10: sum = 90 11 12 13 8 7 2 3 4 5 10 15: sum = 90 16 11 6 1 2 3 8 9 4 5 10 15: sum = 90 16 11 6 7 8 13 14 15: sum = 90 16 11 12 7 6 1 2 3 8 9 10 5: sum = 90 16 11 12 13 14 9 10 5: sum = 90 16 17 12 7 6 1 2 3 8 9 4 5: sum = 90 16 17 12 13 8 9 10 5: sum = 90 16 17 12 13 14 9 4 5: sum = 90 16 17 18 13 8 9 4 5: sum = 90 16 17 18 19 20: sum = 90 21 16 11 6 1 2 7 8 9 4 5: sum = 90

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.

Here is my solution program:

/* * Program to brute force the solution to Cliff Pickover's * 2006/02/11 puzzle. */#include <stdio.h> #define DIMENSION 5 #define TARGET 90 typedef struct{intup;intdown;intleft;intright;intvalue;intmarked;}node;staticnode graph[DIMENSION * DIMENSION];staticintpath[DIMENSION * DIMENSION];staticintpath_index = 0;staticintsum = 0;staticvoidmove_to_node(intindex){inti;graph[index].marked = 1;path[path_index++]= graph[index].value;sum += graph[index].value;if((graph[index].up != -1)&&(!graph[graph[index].up].marked)){move_to_node(graph[index].up);}if((graph[index].down != -1)&&(!graph[graph[index].down].marked)){move_to_node(graph[index].down);}if((graph[index].left != -1)&&(!graph[graph[index].left].marked)){move_to_node(graph[index].left);}if((graph[index].right != -1)&&(!graph[graph[index].right].marked)){move_to_node(graph[index].right);}/* check the path */if((sum == TARGET)&&((path[path_index - 1]== 5)||(path[path_index - 1]== 10)||(path[path_index - 1]== 15)||(path[path_index - 1]== 20)||(path[path_index - 1]== 25))){/* valid path found; print the path */for(i = 0;i < path_index;i++)printf(" %3d",path[i]);printf(": sum = %d\n",sum);}/* erase the tracks */graph[index].marked = 0;path_index--;sum -= graph[index].value;}intmain(intargc,char*argv[]){intcolumn,row;intindex = 0;/* set up the graph */for(row = 0;row < DIMENSION;row++){for(column = 0;column < DIMENSION;column++){if(row > 0)graph[index].up = index - DIMENSION;elsegraph[index].up = -1;if(row < DIMENSION - 1)graph[index].down = index + DIMENSION;elsegraph[index].down = -1;if(column > 0)graph[index].left = index - 1;elsegraph[index].left = -1;if(column < DIMENSION - 1)graph[index].right = index + 1;elsegraph[index].right = -1;graph[index].value = index + 1;graph[index].marked = 0;index++;}}move_to_node(0);/* start from node 1 */move_to_node(5);/* start from node 6 */move_to_node(10);/* start from node 11 */move_to_node(15);/* start from node 16 */move_to_node(20);/* start from node 21 */return0;}

*Code colorized by the CodeColorizer.*

Posted in Pickover Puzzles **|** 2 Comments »

May 6th, 2006 at 8:43 pm

First thing I thought after reading the problem (and noticed you mentioned it in your explanation of your solution too) was going over squares more than once, and I came up with this solution:

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

How many times must you go back and forth on 2/3 so that you travel in a line straight across from 1 -> 5 and summing every square gives you 90? I came up with the following formula where X is the number of times.

1 + X(2+3) + 4 + 5 = 90

X(2+3) = 80

5x = 80

x = 16

1 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 2 + 3 + 4 + 5 = 90

Didn’t find all solutions, but it found one.

(Sorry for posting in such an old article, but I’ve been reading through all your archives ;) )

ND

May 7th, 2006 at 9:03 am

No problem, comments are always open, and I’m always monitoring. :) Novel solution, given the problem parameters (or lack thereof).