javascript - All possible moves in a 5x5 grid? - Stack Overflow

admin管理员组

文章数量:1305012

s o o o o
o o o o o
o o o o o
o o o o o
o o o o e

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

I've created a grid array [[1,1]...[5,5]] but i dont know if that will work.

I've also mapped possible squares, and tried to create a record and check and lots of junk.

Any standard formula I could put to use here?

s o o o o
o o o o o
o o o o o
o o o o o
o o o o e

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

I've created a grid array [[1,1]...[5,5]] but i dont know if that will work.

I've also mapped possible squares, and tried to create a record and check and lots of junk.

Any standard formula I could put to use here?

• javascript
• arrays
• algorithm
• function
• formula

Share Improve this question Follow asked Feb 7, 2012 at 6:43 boomboom 11.7k99 gold badges4747 silver badges6666 bronze badges 9

• What do you mean with 'without using the same square twice'? Please elaborate more. – Kristiono Setyadi Commented Feb 7, 2012 at 6:51
• Just meaning on your path you never go over the same square again. – boom Commented Feb 7, 2012 at 6:51
• @boom: did you try a brute force solution perhaps for a 5X5 grid that would be good enough – Daniel Commented Feb 7, 2012 at 6:59
• and by your design, do you mean the move should only go right and down or it could possibly go everywhere (up and right, in addition to left and down) without using the same path twice? – Kristiono Setyadi Commented Feb 7, 2012 at 7:19
• @Daniel Since he needs all the paths there is no use in using anything else than brute-force solutions. – vinczemarton Commented Feb 7, 2012 at 7:25

 |  Show 4 more ments

5 Answers 5

Sorted by: Reset to default 5

There are quite a few standard path finding algorhythms you could use for this.

This is not related to javascript.

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

Here is how you can do it:

The trick is you'll need to store the already visited squares in a list and check if you are revisiting one of them on every step.

The other trick is you need definite order between the adjacent squares. (Like top/right/bottom/left. Which is a really silly algorhythm but fine for this particular case.)

Also you need to be able to identify the squares (it is possible by its position)

Consider a recursive function (for example 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!!
}

Start this algorythm by visit(start). You get your result in the goallist which is a list of pathlists hopefully.

Also it's only half 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 right.

Check out this fiddle: http://jsfiddle/SoonDead/rd2GN/3/

You can use a depth first search with backtracking to find all possible paths. The idea is simple start at S and visit any neighbor of S, then from that neighbor visit any other neighbor all the while marking that vertex as "used" once you backtrack removed the "used" status from the vertex so you can reuse it in another path, etc.... once you reach E you increment the number of paths. Paths have to be restricted so I'm assuming you mean paths that don't use one vertex more than once or you could have infinite cycles.

Frank mentioned the Catalan Numbers and this does work but only for monotonic paths, ie paths that go either only right/down or left/up. Also DP does not work because this is an NP-Hard problem (non polynomial time to find the solution and to verify since essentially you need to find all paths again to make sure they match).

For references and bibliography on this problem, as well as a recurrence relation, refer to Self-Avoiding Walk in Weisstein's MathWorld. Very unfortunately, I could not get hold of the Abbott and Hanson's article that discussed this problem.

Rate of growth of the sequence in the size of square is formidable. According to OEIS A007764, the number of self-avoiding walks in a 12×12 square is 182413291514248049241470885236, a 30-digit number!

Thanks for the question, that is indeed a profound and thought-provoking problem.

EDIT: If diagonal steps are allowed, the number grows even quicker. This is the OEIS sequence A140518, due to D. Knuth. It is hard to brute-force even for a 5×5 square (over 400 million paths). There are notes from Knuth's lecture on the technique called ZDD that he used to pute these numbers.

if you work in a 5x5 grid there is a simple math solution. Write 1 across the bottom and top of the grid and add the corners till you get to the end, the number in the corner at the end is the number of pathways. This is assuming that you can only move right and down.

Here is an example:

1 1 1 1 1 1 1 1 1 1 1 o o o o o 1 2 3 4 5 6 1 o o o o o --- 1 3 6 10 15 21 1 o o o o o --- 1 4 10 20 35 56 1 o o o o o 1 5 15 35 70 126 1 o o o o o 1 6 21 56 126 252

So the answer is 252

You could also use factorials the formula is (number of grids on each right and downsides)! divided by (left side)! divided by (downside)!= number of pathways.

So your equation would look like 10! divided by 5! divided by 5!= 252

Remember this only works if the guy can go only down and left!

2 to the power of how ever big your square is. in your case 2 to the power od 5 is 32. there are therefor thirty two different possible routes. This patterned can be proved using the following example. A square that is 0x0 although impossible, would technically have one possible way to get from A to B, because it would already be there. A square that is 1x1 has two possible routes( if you don't believe me draw it and find out. This pattern is very obvious and even related to PAscal's triangle. Hope I helped.

本文标签： javascriptAll possible moves in a 5x5 gridStack Overflow