6
$\begingroup$

How many unique ways can you make a path on a 3x3 grid which passes through every square once assuming rotations and reflections are distinct? No crossing or diagonal moves are allowed.

I am not concerned with a starting or ending position. By just considering as many cases as I can by hand I think the answer may be 16, but this is not convincing at all. Any help would be great!

$\endgroup$
0
7
$\begingroup$

There are 8 paths that start in the middle square (from the middle square , you have four choices of what the first step is, and for each of those, you can choose to continue clockwise or counterclockwise).

There are 4 paths that go in a straight line through the middle square (first choose whether it goes through horizontaly or vertically, then choose whether to continue around clockwise or counterclockwise).

There are 8 paths that turn on the middle square (there are four ways to orient the turn, and for each of those, you have to choose whether the path around the middle will go clockwise or counterclockwise).

This gives a total of 20 paths.

$\endgroup$
5
  • $\begingroup$ Any idea on how to generalize for any $n$ ? $\endgroup$ – P. Quinton Oct 22 '19 at 11:42
  • 1
    $\begingroup$ @P.Quinton Not the slightest. This hinges on the fact that it's very cramped once the middle square is accounted for. $\endgroup$ – Arthur Oct 22 '19 at 11:43
  • $\begingroup$ I guess the middle square is some kind of pivot and when you augment the size of the grid you would have several ones. $\endgroup$ – P. Quinton Oct 22 '19 at 11:44
  • $\begingroup$ @P.Quinton Well.. I don't think so. No middle square for odd $n$ $\endgroup$ – David Oct 22 '19 at 11:46
  • 2
    $\begingroup$ @P.Quinton I did find this, though. The fact that there is no good answer there makes me believe that humanity hasn't found one. We have basically brute-forced up to $n = 17$, and that's it. $\endgroup$ – Arthur Oct 22 '19 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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