5
$\begingroup$

In the grid below, create a path that starts at cell 1 and ends at cell 49, moving horizontally and vertically only.

The path must touch each of the 49 cells exactly once and contain a:
A. Maximum of 2 consecutive moves N (North),
B. Maximum of 2 consecutive moves W (West),
C. Maximum of 2 consecutive moves S (South), and
D. Maximum of 1 consecutive move E (East)

The solution is unique, but finding the path is not the true goal. The point is to work through it logically and articulate your logic in detail using diagrams.

I'm requesting no partial answers. You are welcome to find the path using a computer, but knowing the path will not help you answer this puzzle, since you need to show each logical step, which will show that the solution is unique.

The accepted answer will have plenty of images. It will have detailed explanations for each image and scenario, be organized and probably lengthy (compared to most puzzles on this site), but not as lengthy as one might think, considering that there are 111,712 possible paths if rules A through D are discarded.

enter image description here

Text version of the grid above (for those who cannot view images):
It is a 7x7 grid with a 1 in the top left cell and a 49 in the bottom right cell. All other cells are blank. Above the grid is an N for "North". To the right of the grid is an E for "East". To the left of the grid is a W for "West". Under the grid is an S for "South".

$\endgroup$
1
  • 1
    $\begingroup$ I have no idea how you found out there was only 1 solution with these constraints, but that was very fun to work through! :) $\endgroup$ Sep 2, 2022 at 11:44

1 Answer 1

7
$\begingroup$

Solution!

enter image description here


Logical reasoning

(For referencing cells, I will imagine the grid is filled out with numbers 1-49 like this)

  1. The start

There's only one real place to start, and thats the only place you know exactly how the path leaves and enters the cell: the two empty corners. As there are just two entry points, the path must start like this:

enter image description here

Now we actually have a bit more information. Cell 44 must be moving east, as if it was moving west then the path would be cut off from its route to the 49. Similarly, cell 14 must be moving down, meaning cell 6 is moving east.

That means cell 44 must then move up, and cell 13 must move up to reach 6 to avoid consecutive east moves:

enter image description here

  1. One way path

Notice now that the paths along the edges only have one entry/exit point, so the path must continue that way. To avoid consecutive moves, they must also then cut back into the board, which in turn means cells 13 and 37 only have one way they too can go.

We also know two ways the path can't go to avoid double east moves, so we can block off that path.

enter image description here

  1. No cell left behind

Consider cells 12 and 38. If cell 12 is reached by cell 19, then cell 5 is completely unreachable, so cell 12 must be reached by cell 5, which in turn extends the path along the edge. Similarly for cell 38, it must go to 39 or risk isolating it.

Continuing these paths require an east move, which means we have to extend the path back into the grid too to avoid consecutive east moves.
enter image description here

  1. Endpoints

We also know at this point that one arrow must join the back of the other arrow, while that arrow goes to the 49 and the tail extending back to the 1. Lets have a look at these endpoints actually.

enter image description here

The endpoints are corners so also have two possible entries/exits - except only one is used. If the 1 goes to 2, it must then go down to 9 - but this leaves cell 3 isolated. Similar with the 49, entry from 48 leaves 47 isolated.

Hence 1 must go to 8, and 49 must be reached by 42. Now imagine 8 extends down to 15, then having to cut into 16. This would leave 22 isolated, so 8 must go to 9 instead (and same bottom right, 42 must be reached by 41.

To avoid isolating cells, 9 must go to 2 which must extend to 3 and 10 - and 49 must trail round similarly:

enter image description here

  1. Finishing the sides

Consider 20 and 30. If they extend in the same direction, and then have to cut back into the grid, they leave cells 22 and 28 completely unreachable without a 2 move east, so 20 and 30 must cut into the grid, and then into 22 and 28 to avoid isolating them.

This continues a loop round that completes the sides:

enter image description here

  1. Connecting the dots, well, lines

Finally, we just need to join the lines correctly and fill in the middle.

So lets look at the middle. We've actually 'created' some corners, which we can use the logic from part 1 on:

enter image description here

Now look at 10. If it continues down, it creates a loop that has to go 2 east across the middle to connect the sides. So 10 goes right, and everything falls into place:

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Nicely done. I like your method better than mine, since it is more concise, but i still had fun working through it all. As for how i found that those constraints produce a unique solution, I wrote a c# program years ago that outputs all paths for an n x n grid, and i put them in excel and filtered based on consecutive moves in the same direction. $\endgroup$
    – JLee
    Sep 2, 2022 at 12:18
  • $\begingroup$ @JLee ah, clever! Hopefully there were some other unique solutions for a potential part 2 $\endgroup$ Sep 2, 2022 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.