Programming Forums > Application Development > Java

afroboy0731 · Dec 4th, 2006, 4:56 PM

In my computer science class we solved mazes of 0s and 1s using recursion

1 0 0 0 0
1 1 0 1 0
0 1 1 0 1
1 0 1 1 1
0 0 1 0 1

you can only move from a 1 to a 1 and u have to get from the top left to the bottom right. I got the code to say whether or not you can get to the end of the maze, but for extra credit we are supposed to count the number of steps to get there. I was wondering if sum1 could help get in the right direction to counting the number of steps because i dont understand how you could do it since it would count all of the 1s that are connected.

Here is my code:

(Toggle Plain Text)

//Julian
//Recursion Maze
//Comp Sci II AP

import java.io.*;
import java.util.*;
public class recursion
{
	public static void main(String[] args) throws IOException
	{
		Scanner file=new Scanner(new File("recursion.txt"));
		int length=file.nextInt();
		int[][] maze=new int[length][length];
		for(int x=0;x<length;x++)
		{
			for(int y=0;y<length;y++)
			{
				maze[x][y]=file.nextInt();
			}
		}
		mazeSolver ms=new mazeSolver();
		ms.mazeSolver(maze);ms.solving(0,0);
		System.out.println(ms);
	}
}
class mazeSolver
{
	boolean exitFound=false;
	int[][] maze;
	public void mazeSolver(int[][] m)
	{
		maze=m;
	}
	public boolean solving(int r,int c)
	{
		if(r>=0&&c>=0&&r<maze.length&&c<maze.length&&maze[r][c]==1)
		{
			maze[r][c]=2;
			if(r==maze.length-1&&c==maze.length-1)
			{
				exitFound=true;
			}
			else
			{
				solving(r+1,c);
				solving(r-1,c);
				solving(r,c+1);
				solving(r,c-1);
			}
		}
		return exitFound;
	}
	public String toString()
	{
		String output;
		if(exitFound)
		{
			output="Exit Found";
		}
		else
		{
			output="Exit Not Found";
		}
		return output;
	}
	
}

and here is the data

(Toggle Plain Text)

the data should be named "recursion.txt", and the 5 gives you the dimensions of the maze

Arevos · Dec 4th, 2006, 5:44 PM

Quote:

Originally Posted by afroboy0731

I got the code to say whether or not you can get to the end of the maze, but for extra credit we are supposed to count the number of steps to get there. I was wondering if sum1 could help get in the right direction to counting the number of steps because i dont understand how you could do it since it would count all of the 1s that are connected.

If I'm understanding you correctly, it's easier than you might imagine. Imagine your recursive function like a tree, starting from a root and spreading out it's branches, with each branching point representing a step in the maze. Then the number of branching points for a particular branch would also give you the number of steps taken in the maze, would it not?

afroboy0731 · Dec 4th, 2006, 7:51 PM

but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

Indigno · Dec 4th, 2006, 8:29 PM

Quote:

Originally Posted by afroboy0731

but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

Try it and see what happens. I can't answer that myself without punching it in.

kyndig · Dec 16th, 2006, 6:48 PM

Quote:

Originally Posted by afroboy0731

but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

I see what you are saying, you could possibly, add some code to check another step ahead, and see if that 'branch' is a dead end, if it is then dont add that as a step.

Arevos · Dec 17th, 2006, 8:18 AM

Quote:

Originally Posted by kyndig

I see what you are saying, you could possibly, add some code to check another step ahead, and see if that 'branch' is a dead end, if it is then dont add that as a step.

No need. Seeing how old this post is, I don't suppose it would hurt for me to give a more exact answer to the problem. Essentially, with each recursive step you'd pass in a variable that would record the "depth" of that step. So instead of "solving(r+1,c)" you'd use, "solving(r+1,c,depth+1)". Then, when you find the exit, just return the depth. If the exit isn't found, return 0 or -1.

In Python, you'd do something like this:

 python Syntax (Toggle Plain Text) 
def load_maze(filename):
    file = open(filename)
    length = file.readline()
    maze = [[int(x) for x in line.split()] for line in file]
    file.close()
    return maze
 
def solve_maze(maze):
    def explore(x, y, depth):
        if len(maze) == (y + 1) and len(maze[y]) == (x + 1):
             return depth
 
        try: value = maze[y][x]
        except IndexError: return 0
 
        if value == 0: return 0
 
        return explore(x + 1, y, depth + 1) or
               explore(x - 1, y, depth + 1) or
               explore(x, y + 1, depth + 1) or
               explore(x, y - 1, depth + 1)
 
    return explore(0, 0, 1)
 
solution = solve_maze(load_maze("recursion.txt"))
 
if solution:
    print "End of maze reached in %d steps" % solution
else:
    print "No solution"
def load_maze(filename):
    file = open(filename)
    length = file.readline()
    maze = [[int(x) for x in line.split()] for line in file]
    file.close()
    return maze

def solve_maze(maze):
    def explore(x, y, depth):
        if len(maze) == (y + 1) and len(maze[y]) == (x + 1):
             return depth

        try: value = maze[y][x]
        except IndexError: return 0

        if value == 0: return 0

        return explore(x + 1, y, depth + 1) or
               explore(x - 1, y, depth + 1) or
               explore(x, y + 1, depth + 1) or
               explore(x, y - 1, depth + 1)

    return explore(0, 0, 1)

solution = solve_maze(load_maze("recursion.txt"))

if solution:
    print "End of maze reached in %d steps" % solution
else:
    print "No solution"

The Dark · Dec 17th, 2006, 5:07 PM

Won't that try to or two integers together if there is more than one solution to the maze?

Arevos · Dec 18th, 2006, 3:33 AM

Quote:

Originally Posted by The Dark

Won't that try to or two integers together if there is more than one solution to the maze?

Yes, but in Python a boolean "or" means returning the first object considered "True". For instance:

(Toggle Plain Text)

>>> 0 or False or "" or 3 or 5
3

The code doesn't find the fastest route, but does return the number of steps in the first route it finds.

The Dark · Dec 18th, 2006, 5:18 AM

Thanks Arevos, I didn't know that.

Dec 4th, 2006, 4:56 PM	#1
afroboy0731 Newbie Join Date: Oct 2005 Posts: 7 Rep Power: 0	Recursion Maze Question In my computer science class we solved mazes of 0s and 1s using recursion 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 you can only move from a 1 to a 1 and u have to get from the top left to the bottom right. I got the code to say whether or not you can get to the end of the maze, but for extra credit we are supposed to count the number of steps to get there. I was wondering if sum1 could help get in the right direction to counting the number of steps because i dont understand how you could do it since it would count all of the 1s that are connected. Here is my code: (Toggle Plain Text) //Julian //Recursion Maze //Comp Sci II AP import java.io.; import java.util.; public class recursion { public static void main(String[] args) throws IOException { Scanner file=new Scanner(new File("recursion.txt")); int length=file.nextInt(); int[][] maze=new int[length][length]; for(int x=0;x<length;x++) { for(int y=0;y<length;y++) { maze[x][y]=file.nextInt(); } } mazeSolver ms=new mazeSolver(); ms.mazeSolver(maze);ms.solving(0,0); System.out.println(ms); } } class mazeSolver { boolean exitFound=false; int[][] maze; public void mazeSolver(int[][] m) { maze=m; } public boolean solving(int r,int c) { if(r>=0&&c>=0&&r<maze.length&&c<maze.length&&maze[r][c]==1) { maze[r][c]=2; if(r==maze.length-1&&c==maze.length-1) { exitFound=true; } else { solving(r+1,c); solving(r-1,c); solving(r,c+1); solving(r,c-1); } } return exitFound; } public String toString() { String output; if(exitFound) { output="Exit Found"; } else { output="Exit Not Found"; } return output; } } //Julian //Recursion Maze //Comp Sci II AP import java.io.; import java.util.; public class recursion { public static void main(String[] args) throws IOException { Scanner file=new Scanner(new File("recursion.txt")); int length=file.nextInt(); int[][] maze=new int[length][length]; for(int x=0;x<length;x++) { for(int y=0;y<length;y++) { maze[x][y]=file.nextInt(); } } mazeSolver ms=new mazeSolver(); ms.mazeSolver(maze);ms.solving(0,0); System.out.println(ms); } } class mazeSolver { boolean exitFound=false; int[][] maze; public void mazeSolver(int[][] m) { maze=m; } public boolean solving(int r,int c) { if(r>=0&&c>=0&&r<maze.length&&c<maze.length&&maze[r][c]==1) { maze[r][c]=2; if(r==maze.length-1&&c==maze.length-1) { exitFound=true; } else { solving(r+1,c); solving(r-1,c); solving(r,c+1); solving(r,c-1); } } return exitFound; } public String toString() { String output; if(exitFound) { output="Exit Found"; } else { output="Exit Not Found"; } return output; } } and here is the data (Toggle Plain Text) 5 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 5 1 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 the data should be named "recursion.txt", and the 5 gives you the dimensions of the maze

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Help with maze	jl_7	C++	3	Apr 18th, 2006 7:03 AM
Attitudes	Oddball	Coder's Corner Lounge	29	Mar 18th, 2006 9:34 PM
Recursion Question for a "gameboard"	keweedsmo	C++	14	Feb 13th, 2006 2:59 PM
Avoiding Stackoverflow error using recursion to solve a maze	Mjordan2nd	Java	1	Feb 9th, 2006 10:01 PM
c++ recursion question	browning_man9	C++	9	Jan 26th, 2006 6:00 PM

Dec 4th, 2006, 7:51 PM	#3
afroboy0731 Newbie Join Date: Oct 2005 Posts: 7 Rep Power: 0	but if i did it like that then wouldnt i get 10 instead of the correct answer, 8

Dec 17th, 2006, 5:07 PM	#7
The Dark Expert Programmer Join Date: Jun 2005 Posts: 850 Rep Power: 4	Won't that try to or two integers together if there is more than one solution to the maze?

Dec 18th, 2006, 5:18 AM	#9
The Dark Expert Programmer Join Date: Jun 2005 Posts: 850 Rep Power: 4	Thanks Arevos, I didn't know that.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > Java

Recursion Maze Question