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.