Any possible steps in a 5x5 grid?

Question

soooo ooooo ooooo ooooo ooooe 

How can I calculate all possible paths without using the same square twice, so that a person can take from s to e ?

I created a grid grid [[1,1] ... [5,5]], but I don't know if this will work.

I also matched the possible squares and tried to create a record, check and a lot of garbage.

Any standard formula I could use here?

Answer 1

There are many standard path finding algorithms that you could use to do this.

It is not related to javascript.

You can use one algorithm without heuristics, and you should not stop on the first decision.

Here's how you can do it:

The trick is that you need to save the already visited squares in the list and check if you are reviewing one of them at every step.

Another trick - you need a certain order between adjacent squares. (Like top / right / bottom / left. This is a really stupid algorithm, but great for this particular case.)

You should also be able to identify the squares (this is possible by its position)

Consider a recursive function (e.g. name it Visit):

 function visit(square) { add the square to the pathlist //pathlist is not a list of paths but a list of squares which is the current path if (square is the goal) { add a copy of the pathlist to the goalslist } else { for (each adjacency in square.adjacencies) { // this can be calculated by adding +1 and -1 to the coordinates, and checking if its overflowing (less then one/more than five) if (adjacency is in pathlist) { //do nothing we have already been here } else { visit(adjacency) } } } remove square from the pathlist!! } 

Run this algorithm by visiting (start). You get your result in goallist, which we hope is a list of paths.

It is also only half the javascript-half pseudocode, but it is easy to write javascript from it.

EDIT: Enjoy the solution:

 <script type="text/javascript"> var start = [1,1], goal = [5,5], pathList = [], solutionList = [], solutionCount = 0, width = 5, height = 5; function squareInArray(square, array) { var i = 0, x = square[0], y = square[1]; for (i = 0; i < array.length; i++) { if (x == array[i][0] && y == array[i][1]) { return true; } } return false; } function visit(square) { var i = 0, x = square[0], y = square[1], adjacencies = [[x-1,y],[x+1,y],[x,y+1],[x,y-1]]; pathList.push(square); if (x == goal[0] && y == goal[1]) { var solution = pathList.slice(0); //copy trick solutionList.push(solution); solutionCount++; //alert(solution); } else { for (i = 0; i < adjacencies.length; i++) { if (adjacencies[i][0] < 1 || adjacencies[i][0] > width || adjacencies[i][1] < 1 ||adjacencies[i][1] > height) { //overflow } else { if (squareInArray(adjacencies[i], pathList)) { //do nothing we have already been here } else { visit(adjacencies[i]); } } } } pathList.pop(); } visit(start); alert(solutionCount); </script> 

8512 goals. Also someone should check if my code is correct.

Check out this script: http://jsfiddle.net/SoonDead/rd2GN/3/

Answer 2

You can use the first depth search with a backtrack to find all possible paths. The idea is simple to start with S and visit any neighbor S, and then from this neighbor visit any other neighbor all the time, marking this vertex as “used” after you return, removing the “used” status from the top so that you can reuse her another way, etc. When you reach E, you increase the number of paths. Paths should be limited, so I assume that you mean paths that don't use the same vertex more than once, or you can have infinite loops.

Frank mentioned the Catalan numbers, and this works, but only for monotonous paths, that is, paths that go either right / down or left / up. In addition, DP does not work because it is an NP-Hard problem (not a polynomial time to find a solution and check, since essentially you need to find all the paths again to make sure they match).

Answer 3

For links and bibliographies on this issue, as well as the repetition relationship, see the Self-Avoiding Walk at Weisstein MathWorld. Unfortunately, I could not understand the article by Abbott and Hanson discussing this issue.

The growth rate of the sequence in the size of the square is huge. According to OEIS A007764, the number of self-destruction walks in a 12 × 12 square is 182413291514248049241470885236, a 30-digit number!

Thanks for this question, this is a really deep and thoughtful problem.

EDIT: If diagonal steps are allowed, the number grows even faster. This is the OEIS A140518 sequence , due to D. Knuth. Hard brute force even for a 5 × 5 square (more than 400 million paths). There are notes from Knut 's lecture on the ZDD method, which he used to calculate these numbers.

Answer 4

2 due to how large your area is. in your case 2 for power od 5 is 32. There are thirty-two different possible routes. This pattern can be proved using the following example. A square that is 0x0, although impossible, would technically have one of the possible ways to get from A to B, because it will already be there. A square that is 1x1 has two possible routes (if you don't believe that I draw and recognize it, this picture is very obvious and even connected with the PAscal triangle. I hope I helped.