A common puzzle problem is to count the number of paths that start from the bottom-left-hand corner of a grid and end at the top-right hand corner, with the restriction that you can only move upwards or rightwards.

For example, for a 3 by 3 grid (as shown below), the total number of ways is $\binom{6}{3}=20$

If we modify the problem to allow the path to contain downwards and leftwards moves, but maintain a restriction that you cannot visit an intersection twice, what is a general solution for the number of possible paths?

(In the case of the 3 by 3 grid below, I enumerated the total paths with a computer program and got 210).

enter image description here

  • 4
    $\begingroup$ This is called "self-avoiding rook walk", see mathworld.wolfram.com/Self-AvoidingWalk.html . $\endgroup$ – benh Apr 9 '14 at 15:27
  • $\begingroup$ Is oeis.org/A007764 what you want? $\endgroup$ – Gerry Myerson Apr 10 '14 at 11:06
  • $\begingroup$ I'm not convinced by your 3 by 3 grid giving 20 paths under restriction of moving up or right: I'd rather say 6 paths: $\endgroup$ – Wouter M. Apr 10 '14 at 19:46
  • $\begingroup$ UURR URUR URRU RRUU RURU RUUR and that's it. No? And oeis.org/A007764 contains a specific example for the non-intersecting rook paths as a(3)=12, not 210! (exclamation mark, not factorial). What's going on? $\endgroup$ – Wouter M. Apr 10 '14 at 19:55
  • $\begingroup$ @Wouter, you are moving from one square to another, Vincent is moving from one vertex to another. $\endgroup$ – Gerry Myerson Apr 11 '14 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.