Consider the following maze problem in which the maze is made up of a regular N

Question

Consider the following maze problem in which the maze is made up of a regular N x N grid of squares, with the squares labelled (i, j) for 1 i; j N. The boundaries between one square and its neighbor may or may not have a wall between them, and there are always walls on the outside of the grid (i.e., before the squares with a coordinate 1 and after the squares with a coordinate N). A “rat” (i.e., an intelligent agent) is introduced into a starting square, and it has to find its way to a specific goal square.

Consider the function H(i, j) computed as follows. Initially, we set H(i, j) = for all squares except the goal square; and we set H(i, j) = 0 for the goal square. A refinement of H considers a square (i, j) and a neighboring square (i’, j’) with no wall in between: if H(i’, j’) > H(i, j) + 1, we replace H(i’, j’) by H(i, j) + 1. This process is repeated until H converges to a set of minimum values in a time that is polynomial in N. Explain how H may be used to compute the optimal path for the rat. Furthermore, discuss H can be used to actually move the mouse from the starting square to the goal square.

P.S. That is not in the task’s description but the solution may be related to Dijkstra's algorithm.

Explanation / Answer

You need to use backtracking methods, either through recursion or through the intelligent design of loops. Recursion is probably easier.

Write a function that calls itself and attempts to head "North" and if it can't, head "East", then "South", then "West". If angles are allowed then check for those as well.

Now check if its a wall, if it is, try the next direction. If it isn't a wall, you need now need to check to see if the place you are headed is somewhere you haven't been before. I.E. you aren't going in circles. I'd probably use a linked list or similar structure to store your path, you could use an array if you are guaranteed a size of the maze. If the new location isn't a wall, and isn't someplace you have already been, move there.

function maze(node, path){

if (node == goal)
return path;

if (north != wall){ //check location to the north
if (checkpath(north node, path) == false);{
add path to the list;
if (maze(new node, path) != false){ //current location, move it north
return path;}

}
}

}
else if (east != wall){//check location to the east
if (checkpath(east node, path) == false);{
add path to the list;
if (maze(new node, path) != false){ //current location, move it east
return path;}
}
}

else if (South != wall){
if (checkpath(south node, path) == false){
add path to the list;
if (maze(new node, path) != false){
return path;{
}
}
else if {West != wall){
if (checkpath(path) == false){
add path to the list;
if (maze(new node, path) != false){
return path;}
}
}
return false;
}

checkpath(node, path):

while (head != null){
if (node == already in list){
return true;
}
path = path.next;
}
return false;//node is not on the path, procede
}

addNode (node){//if needed
create newNode;
return newNode;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.