0
$\begingroup$

grid What are the total number of paths that can be taken to get from point A to point B ? Rules :- 1)You can move up ,down ,left , right 2)You CANNOT return to a point that you have been to before ie no crossing your own path 3)You CANNOT move diagonally

(I have tried a similar problem ,wherein you could move only up or to the right , which was pretty easy) (Also if a general formula can be given for l*b grid , it will be appreciated)

$\endgroup$

closed as off-topic by Saad, Lord Shark the Unknown, Claude Leibovici, Cesareo, A. Pongrácz Jan 18 at 8:24

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Saad, Lord Shark the Unknown, Claude Leibovici, Cesareo, A. Pongrácz
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ self-avoiding paths of indeterminate length are rather harder to count than shortest paths $\endgroup$ – Henry Aug 13 '18 at 17:45
  • $\begingroup$ Yess thats the entire problem $\endgroup$ – Ishaan Parikh Aug 13 '18 at 17:45
  • 4
    $\begingroup$ See here. $\endgroup$ – Jens Aug 13 '18 at 17:50
  • $\begingroup$ Not bad , however thats using bruteforce on a computer . Isnt there a mathematical way to solve this problem ? $\endgroup$ – Ishaan Parikh Aug 13 '18 at 18:10
  • $\begingroup$ Again empirically: you could find that out by brute force, using grids of size 2x2 and 3x3 etc and establish a series, which has already been given to you. $\endgroup$ – Weather Vane Aug 13 '18 at 18:17
3
$\begingroup$

This is a self avoiding walk problem. There is no known formula for a generic $m \times n$ grid. In fact it is rumored that this is a computationally hard (NP hard problem).

The particular grid of $4\times 4$ is doable. It comes out to be $184$. If it helps, I can upload a small python/matlab script.

NJA Sloane's IS has it listed for a set of grid size $n \times n$, unto $n=10$: http://oeis.org/A007764

There is a nice article on self avoiding walk (aptly titled 'How to avoid yourself') by Brian Hayes in American Scientist (I couldn't find the exact link, but here is a copy sourced in the internet. http://www.peterbeerli.com/classes/images/f/fa/AmSci1998Hayes.pdf)

$\endgroup$

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