«

Ok, I have to solve the "Rat Maze" problem"

I am opening a file called maze.txt which looks similar to this

20 *this is # of rows
20 *this is # of columns
9 *starting row
9 *starting column
11111111111111101111
10101010101010101011
10000010001000101001
10111000100010000011
10111111111111111011
etc....

I have to find the path out of the maze using recursion

This is what I have come up with for the recursion function, ant tips?

int maze(int data[][])
{
data[r][c];

if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
base case
{
cout << "The Rat Is Free!" << endl;
}
if( data[r+1][c] == 0 )
{
cout << "Move Up" << endl;
return maze(data[r+1][c]);
}

if ( data[r-1][c] == 0 )
{
cout << "Move Down" << endl;
return maze(data[r-1][c]);
}

if ( data[r][c+1] == 0 )
{
cout << "Move Right" << endl;
return maze(data[r][c+1]);
}

if ( data[r][c-1] == 0 )
{
cout << "Move Left" << endl;
return maze(data[r][c-1]);
}

else
{
cout << "Rat your are stuck" << endl;
}
}

On Feb 29, 2:17 pm, pleatofthepants <aaronWbry...@gmail.com> wrote:
> Ok, I have to solve the "Rat Maze" problem"
>
> I am opening a file called maze.txt which looks similar to this
>
> 20 *this is # of rows
> 20 *this is # of columns
> 9 *starting row
> 9 *starting column
> 11111111111111101111
> 10101010101010101011
> 10000010001000101001
> 10111000100010000011
> 10111111111111111011
> etc....
>
> I have to find the path out of the maze using recursion
>
> This is what I have come up with for the recursion function, ant tips?
>
> int maze(int data[][])
> {
> data[r][c];
>
> if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
> base case
> {
> cout << "The Rat Is Free!" << endl;
> }
> if( data[r+1][c] == 0 )
> {
> cout << "Move Up" << endl;
> return maze(data[r+1][c]);
> }
>
> if ( data[r-1][c] == 0 )
> {
> cout << "Move Down" << endl;
> return maze(data[r-1][c]);
> }
>
> if ( data[r][c+1] == 0 )
> {
> cout << "Move Right" << endl;
> return maze(data[r][c+1]);
> }
>
> if ( data[r][c-1] == 0 )
> {
> cout << "Move Left" << endl;
> return maze(data[r][c-1]);
> }
>
> else
> {
> cout << "Rat your are stuck" << endl;
> }
>
> }

The way it is currently written, it looks like you get some confusing
output! For example, I can see that it is possible for your program's
output to be:

The Rat Is Free!
Rat your are stuck

Or even a combination of "The Rat Is Free" and one of the other
movement messages (and make further unnecessary moves). Also, if your
rat finds a dead end, how does your algorithm prevent going backwards
and towards the start? I don't see how you keep track of which
direction the rat came from, so it looks like your algorithm will
retry going in the direction that you came from.

On a large maze, it also looks like there is going to a heck of a lot
of recursive calls. Perhaps you can move forward using a while loop
and use recursive call to change or try different directions?

pleatofthepants wrote:
> Ok, I have to solve the "Rat Maze" problem"
>
> I am opening a file called maze.txt which looks similar to this
>
> 20 *this is # of rows
> 20 *this is # of columns
> 9 *starting row
> 9 *starting column
> 11111111111111101111
> 10101010101010101011
> 10000010001000101001
> 10111000100010000011
> 10111111111111111011
> etc....
>
> I have to find the path out of the maze using recursion
>
> This is what I have come up with for the recursion function, ant tips?
>
> int maze(int data[][])
> {
> data[r][c];
>
> if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
> base case
> {
> cout << "The Rat Is Free!" << endl;
> }
> if( data[r+1][c] == 0 )
> {
> cout << "Move Up" << endl;
> return maze(data[r+1][c]);
> }
>
> if ( data[r-1][c] == 0 )
> {
> cout << "Move Down" << endl;
> return maze(data[r-1][c]);
> }
>
> if ( data[r][c+1] == 0 )
> {
> cout << "Move Right" << endl;
> return maze(data[r][c+1]);
> }
>
> if ( data[r][c-1] == 0 )
> {
> cout << "Move Left" << endl;
> return maze(data[r][c-1]);
> }
>
> else
> {
> cout << "Rat your are stuck" << endl;
> }
> }

There is an algorithm for pathfinding that would work perfect for this, but
I'm fairly sure this is homework and the professor wants you to come up with
your own algorithm.

Think of it this way though as a general idea.

Look at your current position and see if it is free.
If not call this function with one position north.
If not call this function with one positon south.
If not call this function with one postion east.
If not call this function with one positon south.

That is a very base and doesn't take into account a lot of things which you
need to code for. The function will need to be called wtih the postion to
check, and also need to return something indicating what it found there.
Impassible, opne or free.

Also, it won't find the most effecient way out, just a way out.

Another possibiltiy is the right wall way. You follow a right wall (or left)
until you are out. This works in all mazes such as this unless the walls
are not continiguous.

I don't want to give too much because this is info, but the function you
have shown is not recursive at all. A recursive function calls itself.


--
Jim Langston

On 29 Feb, 11:19, "Jim Langston" <tazmas...@rocketmail.com> wrote:
> I don't want to give too much because this is info, but the function you
> have shown is not recursive at all. *A recursive function calls itself.

His function is recursive, look at the points of exit.

DP

On Feb 29, 12:33 pm, Triple-DES <DenPlettf...@gmail.com> wrote:
> On 29 Feb, 11:19, "Jim Langston" <tazmas...@rocketmail.com> wrote:

> > I don't want to give too much because this is info, but the
> > function you have shown is not recursive at all. A
> > recursive function calls itself.

> His function is recursive, look at the points of exit.

Yes. The problem is that recursion isn't enough; he needs
backtracking. Basically, at each level of recursion, try up,
right, down and left until one works. The recursive function
must return a value to indicate whether it succeeded or not.
Basically, a loop along the lines of:

bool
try( position )
{
bool found = false ;
for ( direction in up, right, down, left and ! found ) {
if ( open( position + direction ) &&
! visited( position + direction ) ) {
found = try( position + direction ) ;
}
}
return found ;
}

(Obviously, this needs a good deal of fleshing out. That for
isn't going to pass as written, and you also need checks to end
the recursion, and possibly to avoid wandering off the edges of
the maze---although that could also be handled in open(). But
the basic idea is there. And I sort of like the idea of
declaring direction as an enum, with position a class type which
defined addition with a direction. But then, I've already got a
small program which will generate an iterator over an enum, so
the for loop becomes very simple.)

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

pleatofthepants wrote:
> Ok, I have to solve the "Rat Maze" problem"
>
> I am opening a file called maze.txt which looks similar to this
>
> 20 *this is # of rows
> 20 *this is # of columns
> 9 *starting row
> 9 *starting column
> 11111111111111101111
> 10101010101010101011
> 10000010001000101001
> 10111000100010000011
> 10111111111111111011
> etc....
>
> I have to find the path out of the maze using recursion
>
> This is what I have come up with for the recursion function, ant tips?
>
> int maze(int data[][])
This line should not compile.
> {
> data[r][c];
this line is bad.

>
> if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
> base case
> {
> cout << "The Rat Is Free!" << endl;
> }
> if( data[r+1][c] == 0 )
> {
> cout << "Move Up" << endl;
> return maze(data[r+1][c]);
> }
>
> if ( data[r-1][c] == 0 )
> {
> cout << "Move Down" << endl;
> return maze(data[r-1][c]);
> }
>
> if ( data[r][c+1] == 0 )
> {
> cout << "Move Right" << endl;
> return maze(data[r][c+1]);
> }
>
> if ( data[r][c-1] == 0 )
> {
> cout << "Move Left" << endl;
> return maze(data[r][c-1]);
> }
>
> else
> {
> cout << "Rat your are stuck" << endl;
> }
> }

Triple-DES wrote:
> On 29 Feb, 11:19, "Jim Langston" <tazmas...@rocketmail.com> wrote:
>> I don't want to give too much because this is info, but the function
>> you have shown is not recursive at all. A recursive function calls
>> itself.
>
> His function is recursive, look at the points of exit.

yes, you are right. I missed that. It's just not effective.

--
Jim Langston