8
$\begingroup$

Checking the correctness of a daily Sudoku I'd just finished, I noticed a curious pattern in one of the 3x3 cells:

1 9 3
8 2 4
7 6 5

Note that each of the numbers is adjacent in the 8 cardinal directions to the number immediately above and below it, so you can traverse them in order without skipping any. This is certainly not always the case. Consider:

1 2 3
5 6 4
7 8 9

This has a gap between the 4 and 5, so there's no complete path here. I made a mental note to check it in subsequent puzzles to see if it happened again - it seems pretty rare. Even with nine 3x3 grids on each puzzle, once per day for over a month, I've yet to find another. Also, the original is especially unusual as it creates a Hamiltonian Cycle, not just a Path, as the 1 and the 9 are also adjacent. This also isn't always true. Consider:

1 2 3
6 5 4
7 8 9

This has a Hamiltonian Path from 1-9, but not a Cycle because the ends aren't adjacent. My question is, in a 3x3 grid, how many of the possible (3x3)! permutations result in a Hamiltonian Path, and how many of those are also Hamiltonian Cycles? Is there a formula for these that can be generalized to 4x4, 5x5, or other NxN grids? (3x3 is the minimum, as with 2x2, the answer is trivially 100%, since all numbers are adjacent to eachother.)

Cycles seem easiest to pin down, at least in 3x3. There's basically two shapes as far as I can tell, one with no diagonal crossing and one with: (Apologies for crude ASCII art)

1 2 3  ┌────/    1 2 3  ┌────┐
9 4 5  │  /─┐    9 7 4  │ /\/
8 7 6  └────┘    8 5 6  │/ /\

which can be rotated and flipped into 8 configurations each, and then for each configuration, the numbers can be cycled into one of 9 positions, or reversed for another 9. So you get 2 x 8 x 9 x 2 = 288. I have more difficulty figuring out all of the non-Cyclic paths, or coming up with a generalized solution for larger grids.

$\endgroup$
  • $\begingroup$ There is a 2 to 1 correspondence between permutations that make a path and paths you can draw in an mxn grid (pick an endpoint to be 1, and write numbers sequentially along the path). There is a 2mn to 1 correspondence between permutations that make a cycle and cycles you can draw in an mxn grid (pick any point to be 1, pick a direction, and write numbers sequentially along the cycle). So really, you just need to count paths and cycles on an unlabeled rectangular grid. $\endgroup$ – Hurkyl May 10 '14 at 22:45
3
$\begingroup$

These are OEIS sequences A158651 for paths and A140519 for cycles (where the latter needs to be multiplied by $2N^2$ since they only count the cycles and not their realisations through permutations of numbers). The entries refer to the paper Enumerating Hamiltonian Cycles by Ville H. Pettersson in the Electronic Journal of Combinatorics, Volume $21$, Issue $4$, $2014$.

$\endgroup$
  • $\begingroup$ A140519 also links to A140521, which is the same only doubled for N>1. So you'd just need to multiply that by $N^2$ to account for different starting positions on the loop. Then of course you'd need to divide by $N^2!$ to find the actual chance. For a 3x3 board, that comes to 0.29% That times 9 for the 9 cells in a Sudoku board means each puzzle has a ~2.66% chance of a Hamiltonian path/cycle. @Fahrbach's solution covers some smaller non-square boards, but this one is pretty definitive for squares, so I'd say this is the more complete answer. $\endgroup$ – Darrel Hoffman May 5 '16 at 16:31
4
$\begingroup$

I just wrote a program to test the following $m \times n$ boards. The coordinates are (paths from 1 to $mn$, cycles).

\begin{array}{c|cccc} m \backslash n & 1 & 2 & 3 & 4 & 5 \\ \hline \\ 1 & (1,1) & (2,2) & (2,0) & (2,0) & (2, 0) \\ 2 & (2,2) & (24,24) & (96,48) & (416,128) & (1536,320) \\ 3 & (2,0) & (96,48) & (784,288) & \\ 4 & (2,0) & (416,128) & & \\ 5 & (2,0) & (1536,320)\\ \end{array}

$\endgroup$
  • $\begingroup$ Okay, so I guess this answers the 3x3 case. (Glad to see my calculation for Cycles was correct.) How difficult would it be to generalize this to larger grids? I suspect that the runtime for such a program would get prohibitively expensive after a certain point... $\endgroup$ – Darrel Hoffman May 10 '14 at 22:12
  • $\begingroup$ Oh, and for reference, are you counting cycles as paths? Or would the total for paths actually be 784 + 288? $\endgroup$ – Darrel Hoffman May 10 '14 at 22:15
  • $\begingroup$ The paths include the cycles. I'm about to update this for arrays of size $m\times n$. The runtime of this program is $O((mn)!)$, so we can't push it too far. $\endgroup$ – fahrbach May 10 '14 at 22:19
  • $\begingroup$ You could cut the time in half by only doing cases where M >= N, since the results for MxN should obviously be identical to NxM. I think there's probably a more optimal solution - rather than testing every permutation, start with one spot and do a traversal, cutting short any path which isolates a point or points, thus saving unneeded calculation. $\endgroup$ – Darrel Hoffman May 10 '14 at 23:04

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.