1
$\begingroup$

Let's say there is a 5x5 grid with a starting position in the upper left corner, and an ending position is lower left corner. How do I count how many Hamiltonian paths there are through the grid?

I know the answer is 86 for a 5x5 grid. But how should I calculate this? (4x4 is 8, 3x3 is 2) I want to learn calculate larger grids.

$\endgroup$
  • 2
    $\begingroup$ The same topic exists on Math.SE as well as SO. There is no easy way to calculate Hamiltonian Paths. I seem to remember the complexity being O(n^2*2^n) for finding whether or not a Hamiltonian path exists at all. $\endgroup$ – LeppyR64 Oct 17 '14 at 3:49
  • $\begingroup$ mathoverflow.net/a/36378/58988 $\endgroup$ – d'alar'cop Oct 17 '14 at 4:04
  • $\begingroup$ apparently there are 208, not 86 $\endgroup$ – d'alar'cop Oct 17 '14 at 4:05
  • $\begingroup$ No there are 86. The example you linked is travelling from bottom left to top right (diagonally opposed). Tlaxin's post travels from top left to bottom left. $\endgroup$ – LeppyR64 Oct 17 '14 at 4:09
  • $\begingroup$ I also count 86. $\endgroup$ – Florian F Oct 17 '14 at 22:21
5
$\begingroup$

The Hamiltonian path problem is NP-complete.

This means there's no reasonable way for you to find all of these paths yourself on a sufficiently large grid. You might be able to find a few of them manually, but you will have no way of knowing if you've found all of them, even if you have. Counting them with certainty takes an unreasonable amount of computational time - we know of no faster way.

$\endgroup$
  • 3
    $\begingroup$ This is true for the general case. But it is not necessarily true in a special case such as the square grid or a plane graph. $\endgroup$ – Florian F Oct 17 '14 at 8:57
  • 2
    $\begingroup$ True, Florian. My intuition says there's no closed-form formula, because a natural divide-and-conquer approach splits the problem up into many count-P complete problems. BTW, the sequence oeis.org/A000532/list lists the currently known values. $\endgroup$ – Lopsy Oct 17 '14 at 16:09

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.