|
There is no solution to the given problem. Here is my proof:
I’ll label the squares with coordinates, origin located at the bottom left corner of f. So f is (1,1) and B is (3,8).
Remember that all squares must be visited. Consider (2,8) between A and B. I call this a “dead end” because there is only one “free” entrance into that square. So certain bugs can enter but can’t get out again. In this case, it is a dead end for C, D, E, and F. So either bug A or B must be the one who visits (2,8).
Let’s assume it is bug A. His only choice for his next move, then, is down to (2,7). Now, technically speaking, bug A could move left, right or down. However, if bug A moves right or down, (1,7) becomes a dead end. The only bug that could visit it would be bug A, but that would take A back to his home. So there is no bug that could visit (1,7) in this case.
Therefore bug A must move from (2,7) to (1,7). He is then forced to move to (1,6).
Now we have created two more dead ends: (3,7) and (2,6). (3,7) can be visited by either B or D. (2,6) can only be visited by D. Therefore it must be that B visits (3,7) followed by (4,7). And it must be that D visits (2,6) followed by (2,5), which forces A to move to (1,5) and (1,4).
Again we have a few new dead ends.
(4,8) can only be visited by B, and then his next moves would have to be to (5,8), (6,8), and (6,7).
(4,6), then, can only be visited by E. And his next move would have to be to (5,6).
(3,5) is a dead end too, but that’s not important right now.
And another new dead end is created at (7,7). It has to be C or else C will be completely cut off from his mate. Therefore C moves to (7,7) and then (7,6).
But now both B and C need to pass through (6,6) and this can’t be. Therefore our last assumption must be wrong. Well, everything we have been doing has been FORCED. The last assumption we made was the very first: that bug A must visit (2,8).
Therefore it MUST be that bug B visits (2,8), followed by (2,7) so he can get out.
Now, we know B doesn’t go right, right, up, right, right, down, because that would get us stuck in the same problem with C again.
He COULD go right right, down, right. But then we have two problems. First, since we have to get C out by going past the e (Since we blocked off the path above d), we end up cutting off d from his mate. Second, two squares (4,8) and (5,8) can never be visited by any bug.
Ok, therefore we can conclude that B does not go from (2,7) to (3,7). And he can’t go to (1,7) because that would cut off A. Therefore B must go from (2,7) to (2,6) to (2,5). And by the way, A must go from his start to (1,4).
(3,7) is a dead end now and the only bug that can visit it is D. Therefore D must go from his start to (3,7) (4,7) (4,8) (5,8) due to the dead ends he creates along the way. He could go right to d now, or he could loop around and go (6,8) (6,7) to d. Either way, doesn’t matter.
(4,6) is a dead end now and the only bug that can visit it is E. Therefore E must go from his start to (4,6) (5,6). How he can’t go to (6,6) because that would cut off C from his mate. Therefore E moves to (5,5) (5,4).
C, then moves from his start to (7,7) (7,6) (6,6) (6,5) (6,4). (Well, depending on how you had D move, he could have gone (6,8) (6,7) (7,7) (7,6) (6,6) (6,5) (6,4)). If C moved to (7,4) next, he would be cutting e off from his mate. Therefore C has to move to (6,3). C’s next moves could be to c, (5,3) or (7,3). Moving to (5,3) would cut off E (who is currently sitting at (5,4). And moving to (7,4) would again cut e off from his mate. Therefore C must move to c.
This means E will at some point have to get to (4,1) and then go right, right, right, up, up, up, up to get to e. But the only way E can get from (5,4) to (4,1) now will cut b off from his mate.
Therefore there is NO way to solve the puzzle with the given layout.
However, if you move bug D to the right one space, then there are 3 variations on a solution. The overall paths are the same in all the solutions. It's just that there are a couple variations in the top right corner amongst C D and E. |
