Spoiler for the July 27 fivethirtyeight.com Riddler Classic:
From Renaud Dubedout, a puzzle perfect for doodling during a boring class or meeting, not that I would ever endorse that sort of thing:
Start with an empty 5-by-5 grid of squares, and choose any square you want as your starting square. The rules for moving through the grid from there are strict:
- You may move exactly three cells horizontally or vertically, or you may move exactly two cells diagonally.
- You are not allowed to visit any cell you already visited.
- You are not allowed to step outside the grid.
You win if you are able to visit all 25 cells.
Is it possible to win? If so, how? If not, what are the largest and smallest numbers of squares you can legally visit?
I was out of the country, so I didn’t get a look at this puzzle until its solution had been published. I found a 24-cell solution and about 80% convinced myself 25 cells was impossible, then looked and found out, no, it’s not. In fact there are 12,400 solutions.
Which I proceeded to verify with a Python script. Actually it’s 12,400 if you count reflections and rotations as distinct. If you don’t, though, then I think there are “only” 1806.
Or something like half that, if you don’t count as distinct a solution and its time reversal. That is, a solution starting at square a and ending at square b can be trivially transformed into a solution starting at square b and ending at square a. That means for every solution there’s another solution that’s basically the same… unless of course it’s a solution that is time symmetric, that is, it is its own time reversal.
Consider for instance this solution:
Starting from the top left square, it goes East, South, West, Northeast, South… and ends up going (from 20) …South, Northeast, West, South, East. The last twelve directions are the same as the first twelve, in reverse order. If you replace each step number with and rotate the square 180°, you get the original solution back again.
There seem to be four such solutions (not counting rotations and reflections). One other also starts in the corner:
which has 1 through 6 and 20 through 25 in the same place as above but 7 through 19 rotated 180°. Then there are:
which are related in the same way.
How about time antisymmetric solutions? For instance, starting with East, South, West, Northeast, South… and ending with …North, Southwest, East, North, West? Nope, none.
Oliver also asks:
If you solved this game and want another game for your next boring event (and who doesn’t?): Can you still win if the grid is 6-by-6?
Exponential growth being what it is, my Python script was a lot slower on this one (in fact it crashed until I realized I could modify it to use a lot less storage) but it eventually came up with 8,250,272 solutions including rotations and reflections; 1,287,875 not including them. It found no time symmetric or time antisymmetric solutions.