Chance of Hamiltonian Path in Sudoku cell

Question

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.

Answer 1

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$.

Answer 2

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}