Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I asked a question on stack overflow and they suggested I migrate over here. I'm writing a program to solve the following problem:

Given a grid of x by y dimensions, calculate the number of paths through it that start in one corner (let's say top right) and end in another (bottom right) and pass through every vertex exactly once

I've just been brute forcing it but it gets slow quickly and people on StackOverflow said I didn't even need to bother with traversal, and that this was just a math problem. Does anyone have any insight into how I could solve it this way?

share|improve this question
    
I think it would be useful to state of parity checking case in question. –  hate-engine Jan 10 '13 at 0:27
    
Your title seems to imply that in the body you're using the term "route" to denote a path that contains each vertex at most once? I hadn't come across that usage before. –  joriki Jan 10 '13 at 0:30
    
@joriki Not sure what the proper term is, but I edited it to "path." –  CharmQuark Jan 10 '13 at 0:32
1  
No, you introduced a new unexplained discrepancy between the title and the body. –  joriki Jan 10 '13 at 0:37
2  
Augh, nitpicking! It's clear we want the number of Hamiltonian paths. –  Lopsy Jan 10 '13 at 0:44

2 Answers 2

There's the paper "The number of Hamiltonian paths in a rectangular grid", that gives generating functions for $m \times n$ grids with $m \leq 5$. It seems like a difficult problem otherwise.

share|improve this answer

Here's an 'educational' video that tries to answer a similar question:

http://youtu.be/Q4gTV4r0zRs

Also, I think this is an excellent computer science question (ie math is not ready for such hard problems, lol).

Here is your question being used as a programming challenge. My guess is a good computer science answer involves a (depth-first) brute-force search with clever pruning along the way.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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