Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I tried making a simple-minded implementation of the algorithm in java. My conlusion was that the algorithm you described works, even for finding multiple paths. Or, possibly, you managed to think of a more clever test case than me. (Please post your maze so I can try my algorithm on it)</p> <p>My implementation of the dead end counter is probably not the most efficient one, but it gets the job done. For each current OPEN node that is visited, it checks the 4 surrounding nodes:</p> <ul> <li>If at least one neighbour is OPEN, current node is not a dead end</li> <li>If more than one neighbour is VISITED current node is not a dead end</li> <li>If only one node is VISITED (the one we came from in the previous step) and no other neighbour is OPEN, current node is a dead end</li> </ul> <p>This is the java code I wrote (beware! pretty long). An alternative would be, if you wish, to store the path on a stack, pushing a node each time it is set to VISITED and popping a node each time it is set back to OPEN. Each time the GOAL is reached, the stack holding the current path should be copied and saved. </p> <p>If the if block marked with a comment as "dead-end-investigation-step" is removed, this implementation is almost exactly equal to the one described in the question.</p> <p><code></p> <pre><code>package test; import java.util.HashSet; import java.util.Set; public class MazeSolver { final static int OPEN = 0; final static int WALL = 1; final static int GOAL = 2; final static int VISITED = 3; static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 }, { 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } }; // This is what the field looks like: // // 0 1 1 0 1 // 0 0 0 0 0 // 0 1 1 0 1 // 0 1 0 0 0 // 0 0 0 1 0 // 1 1 0 2 0 static int width = field.length; static int height = field[0].length; static int xStart = 0; static int yStart = 0; // Initiated to start position: (x = 0, y = 0) static int nrSolutions = 0; // Records number of solutions // Used for storing id:s of dead end nodes. // The integer id is (x + y * width) static Set&lt;Integer&gt; deadEnds = new HashSet&lt;Integer&gt;(); public static void main(String[] arg) { System.out.println("Initial maze:"); printField(); findPath(xStart, yStart); System.out.println("Number of solutions: " + nrSolutions); System.out.println("Number of dead ends: " + deadEnds.size()); } private static void findPath(int x, int y) { if (x &lt; 0 || y &lt; 0 || x &gt;= width || y &gt;= height) { // Step 1 return; } else if (field[x][y] == GOAL) { // Step 2 nrSolutions++; System.out.println("Solution nr " + nrSolutions + ":"); printField(); return; } else if (field[x][y] != OPEN) { // Step 3 return; } else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step int uniqueNodeId = x + y * width; deadEnds.add(uniqueNodeId); // Report as dead end return; } field[x][y] = VISITED; // Step 4 findPath(x, y - 1); // Step 5, go north findPath(x + 1, y); // Step 6, go east findPath(x, y + 1); // Step 7, go south findPath(x - 1, y); // Step 8, go west field[x][y] = OPEN; // Step 9 // Step 10 is not really needed, since the boolean is intended to // display only whether or not a solution was found. This implementation // uses an int to record the number of solutions instead. // The boolean return value would be (nrSolutions != 0) } private static boolean isDeadEnd(int x, int y) { int nrVisitedNeighbours = 0; if (y &gt; 0) { // If northern neighbour exists if (field[x][y - 1] == VISITED) { nrVisitedNeighbours++; } else if (field[x][y - 1] != WALL) { return false; } } if (x &lt; width - 1) { // If eastern neighbour exists if (field[x + 1][y] == VISITED) { nrVisitedNeighbours++; } else if (field[x + 1][y] != WALL) { return false; } } if (y &lt; height - 1) { // If southern neighbour exists if (field[x][y + 1] == VISITED) { nrVisitedNeighbours++; } else if (field[x][y + 1] != WALL) { return false; } } if (x &gt; 0) { // If western neighbour exists if (field[x - 1][y] == VISITED) { nrVisitedNeighbours++; } else if (field[x - 1][y] != WALL) { return false; } } if (nrVisitedNeighbours &gt; 1) { // Circular path scenario return false; } return true; // The exhaustive result of this check: this is a dead // end } private static void printField() { for (int yy = 0; yy &lt; field[0].length; yy++) { for (int xx = 0; xx &lt; field.length; xx++) { System.out.print(field[xx][yy] + " "); } System.out.println(); } System.out.println(); } } </code></pre> <p></code> </p> <p>The algorithm above reports four different solution paths and two dead ends to the example maze which is hardcoded into the code.</p> <hr> <p><strong>&lt;EDIT&gt;</strong> Might the reason for why you get too few solution paths be a misinterpretation of what is a solution path? For example, consider this maze:</p> <pre><code>###### ## # ## # # #S # ##E### ###### </code></pre> <p>This maze has only one valid solution path. This is because you are only allowed to visit each node once, so going around the circular path is not a valid solution path since that would visit the node east of S and north of E twice. This definition of a solution path is implied by the algorithm that you use.</p> <p>If one were to allow visiting the same node multiple times, there would be infinitely many solutions, as you could go around the circle 1, 2, 3 ... to infinitely many times. <strong>&lt;/EDIT&gt;</strong></p> <p><strong>&lt;EDIT2&gt;</strong></p> <p>Exactly as you say, I increase the pathLength each time I set a node to VISITED, and decrease the path length each time I set a VISITED node back to OPEN.</p> <p>To record the shortest path length I also have a shortestPath int value which I initiate to Integer.MAX_VALUE. Then, each time I have reached the goal, I do this:</p> <pre><code>if(pathLength &lt; shortestPath){ shortestPath = pathLength; } </code></pre> <p>As for the dead ends... I tried counting them by hand and I thought 9 seemed right. Here is the maze posted by <a href="https://stackoverflow.com/questions/1254400/problem-with-maze-algorithm/1256497#1256497">Sareen</a>, but with the dead ends marked (by hand) with a D:</p> <pre><code>#################### #S # D# D#D D# # # ## ## ### ### # # # # # ## # # # ## # # ### ##### # # # #D #D # ### # ### ### ## # ##### # D#D #D E# #################### </code></pre> <p>Can you find any more? Or did I misinterpret what you meant by dead end? I thought dead end means: A node to which you can only come from one direction.</p> <p>Example 1:</p> <pre><code>###### ## ### ## ### ## ### #S E# ###### </code></pre> <p>The maze above has one dead end.</p> <p>Example 2:</p> <pre><code>###### ## ## ## ## ## ## #S E# ###### </code></pre> <p>The above maze has no dead ends. Even if you are at one of the accessible nodes furthest to the north, there are still two adjacent non-WALL squares.</p> <p>Do you have another definition of dead end? <strong>&lt;/EDIT2&gt;</strong></p>
    singulars
    1. This table or related slice is empty.
    1. POProblem with Maze Algorithm
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USAlderath
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COUsing this implementation on the sample maze posted by Sareen (with an addition to record shortest path) I get: Number of solutions: 62720 Number of dead ends: 9 Shortest path: 41 (exluding S and E) The shortest path with 41 steps is pretty easy to find by hand, without the algorithm, and it's definitely 41.
      singulars
      1. PO
      1. USAlderath
    2. COI managed to get the result right now using your algorithm , problem was in my implementation . But can you explain how you count the steps? i originally steps++ when i mark a path and steps-- when i backtrack. But this obviously doesn't work very well. The dead ends number of 9 doesn't seem right though!
      singulars
      1. PO
      1. This table or related slice is empty.
    3. COI replied to your comment by editing my post, where I could get better formatting. Check the section marked EDIT2.
      singulars
      1. PO
      1. USAlderath
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload