package back.tracking;
import static java.lang.Thread.sleep;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
*
* @author Aditya Vijayvergia @ codingEdge
*/
public class Maze {
int x,y; //pos saves x and y coordinates of current position
int ways=0; //saves the number of ways when we reach a node
public char[][] maze =
{{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
{' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', '#'},
{'#', ' ', '#', '#', ' ', '#', ' ', '#', ' ', '#'},
{'#', ' ', ' ', '#', ' ', '#', ' ', ' ', ' ', '#'},
{'#', '#', ' ', '#', '#', '#', ' ', '#', '#', '#'},
{'#', ' ', ' ', ' ', ' ', '#', '#', '#', ' ', '#'},
{'#', '#', '#', '#', ' ', '#', ' ', ' ', ' ', '#'},
{'#', ' ', ' ', ' ', ' ', '#', '#', '#', '#', '#'},
{'#', ' ', '#', '#', ' ', ' ', ' ', ' ', ' ', '#'},
{'#', 'O', '#', '#', '#', '#', '#', '#', '#', '#'},};
Maze()
{
x=1;//we start the maze from (1,0)
y=0;
//printing the maze
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
System.out.print(maze[i][j]+" ");
}
System.out.println();
}
try {
sleep(4000);
} catch (InterruptedException ex) {
Logger.getLogger(Maze.class.getName()).log(Level.SEVERE, null, ex);
}
//System.out.println("working");
maze[x][y]='x';
if(solve("start")){
System.out.print("\n\nSolved Maze:\n\n");
//printing the solved maze
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
System.out.print(maze[i][j]+" ");
}
System.out.println();
}
}
else
System.out.print("\n\nThis maze doesnot no solution");
}
public boolean solve(String... move)
{
int x1 =-1,y1 = -1;
int ways1=-1;
if(move.equals("start"))
{
//System.out.println("started solve");
if(solve(checknext("left")))
return true;
}
if(ways>1)
{
ways1=ways;
x1=x;//x1 and x2 save the position of a node
y1=y;
//System.out.println("\nnode at "+x1+","+y1+"\nways="+ways);
ways=0;
}
for(String s:move)
{
if( s=="down"){
x++;
System.out.println("down");
}
else
if(s=="up"){
x--;
System.out.println("up");
}
else
if(s=="right"){
y++;
System.out.println("right");
}
else
if(s=="left"){
y--;
System.out.println("left");
}
else
if(s=="end")
{
return false; //here a reach the end of a path(i.e., we reach a leaf) so we need to backtrack
//to the last node
}
int x2=x,y2=y;//x2 and y2 save the path taken to reach the goal
if(maze[x][y]=='O'){
//System.out.println("\n\nSolved");
return true;
}
if(solve(checknext(s)))
{
maze[x2][y2]='O';//highlighting the path
return true;
}
else
{
if(x1==-1)//if this is not a node then go back further untill a node is reached
{
return false;
}
else
{
ways1--;//decreasing the number of ways left at a node after we have tried it
x=x1;
y=y1;
System.out.println("\n\nbacktracking to "+x+","+y+"\nways left="+ways1);
if(ways1==0)//if we have tried all the ways of a node
{
return false;//backtrack to the last node
}
}
}
}
return false;
}
public String[] checknext(String s)//s saves the last movement as we do not want to go back on our last position
{
//System.out.print("started checknext");
ways=0;
String[] canmove=new String[3];//canmove saves all the possible ways at this particular position
int i=0;
if(s!="down"&&x>0&&maze[x-1][y]!='#'){
ways++;
canmove[i++]="up";
}
if(s!="left"&&y<9&&maze[x][y+1]!='#'){
ways++;
canmove[i++]="right";
}
if(s!="up"&&x<9&&maze[x+1][y]!='#'){
ways++;
canmove[i++]="down";
}
if(s!="right"&&y>0&&maze[x][y-1]!='#'){
ways++;
canmove[i++]="left";
}
if(ways==0)
canmove[0]="end";
//System.out.println("ended check next");
return canmove;
}
public static void main(String ar[])
{
new Maze();
}
}
No comments:
Post a Comment