Why the perfect solution can contain loops Daniel Hartmeier July, 2nd 2000 As it turned out, one of my fundamental assumptions is wrong: a perfect solution can, in fact, contain loops. The following 4x4 grid is an example of such a case: A--9--B--1--C--1--D | | | | 1 1 9 1 | | | | E--9--F--9--G--9--H | | | | 1 1 5 1 | | | | I--9--J--1--K--1--L | | | | 1 9 1 9 | | | | M--1--N--1--O--1--P The best solution without loops found by my algorithm is: A B--C--D | | | E F G H | | | | I J--K L | | M--N--O--P Path : AEIMNOPOKGKJFBCDHL Moves : 17 Score : 25 But there is an even better solution containing a loop: A B--C--D | | | E F G H | | | | I J--K--L | | M--N--O--P Path : AEIMNOPOKJFBCDHLKG Moves : 17 Score : 21 I see no obvious reason to assume that there aren't cases where the perfect solution contains more than one loop and/or larger loops. Possibly one requires a larger grid to produce such cases, but I guess they are very well possible. The reason why my algorithm found the perfect solutions for the grids posted by Mike so far is that those grids were created randomly. It seems that grids whose perfect solutions contain loops are very rare when created randomly. Unfortunately, I can't easily adapt my algorithm to deal with loops. The whole concept of my recursive sumBridges() function is based on the assumption that there are no loops. I have to go back and come up with a new theory. Thanks to Geoff Bailey for producing the first counter-example.