[Math] How many unique ways to form a path on a 3×3 grid

combinationscombinatoricsdiscrete mathematicsgraph theorypermutations

How many unique ways can you make a path on a 3×3 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!

Best Answer

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.

Related Question