Sunday, July 8, 2007

Solve the Rat In A Maze problem using backtracking.

This is one of the classical problems of computer science. There is a rat trapped in a maze. There are multiple paths in the maze from the starting point to the ending point. There is some cheese at the exit. The rat starts from the entrance of the maze and wants to get to the cheese.

This problem can be attacked as follows.




Have a m*m matrix which represents the maze.

For the sake of simplifying the implementation, have a boundary around your matrix and fill it up with all ones. This is so that you know when the rat is trying to go out of the boundary of the maze. In the real world, the rat would know not to go out of the maze, but hey! So, initially the matrix (I mean, the maze) would be something like (the ones represent the "exra" boundary we have added). The ones inside specify the obstacles.


111111111111111111111
100000000000000000001
100000010000000000001
100000010000000000001
100000000100001000001
100001000010000000001
100000000100000000001
100000000000000000001
111111111111111111111



The rat can move in four directions at any point in time (well, right, left, up, down). Please note that the rat can't move diagonally. Imagine a real maze and not a matrix. In matrix language



Moving right means adding {0,1} to the current coordinates.

Moving left means adding {0,-1} to the current coordinates.

Moving up means adding {-1,0} to the current coordinates.

Moving right means adding {1,0} to the current coordinates.



The rat can start off at the first row and the first column as the entrance point.

From there, it tries to move to a cell which is currently free. A cell is free if it has a zero in it.

It tries all the 4 options one-by-one, till it finds an empty cell. If it finds one, it moves to that cell and marks it with a 1 (saying it has visited it once). Then it continues to move ahead from that cell to other cells.

If at a particular cell, it runs out of all the 4 options (that is it cant move either right, left, up or down), then it needs to backtrack. It backtracks till a point where it can move ahead and be closer to the exit.

If it reaches the exit point, it gets the cheese, ofcourse.

The complexity is O(m*m).



Here is some pseudocode to chew upon


findpath()
{
Position offset[4];
Offset[0].row=0; offset[0].col=1;//right;
Offset[1].row=1; offset[1].col=0;//down;
Offset[2].row=0; offset[2].col=-1;//left;
Offset[3].row=-1; offset[3].col=0;//up;

// Initialize wall of obstacles around the maze
for(int i=0; i < m+1;i++)
maze[0][i] = maze[m+1][i]=1; maze[i][0] = maze[i][m+1]=1;

Position here;
Here.row=1;
Here.col=1;

maze[1][1]=1;
int option = 0;
int lastoption = 3;

while(here.row!=m || here.col!=m)
{
//Find a neighbor to move
int r,c;

while (option <= LastOption)
{
r=here.row + offset[position].row;
c=here.col + offset[option].col;
if(maze[r][c]==0)break;
option++;
}

//Was a neighbor found?
if(option <= LastOption)
{
path->Add(here);
here.row=r;here.col=c;
maze[r][c]=1;
option=0;
}
else
{
if(path->Empty())return(False);
Position next;
Path->Delete(next);
If(new.row==here.row)
Option=2+next.col - here.col;
Else { option = 3 + next.row - here.col;}
Here=next;
}
return(TRUE);
}
}

53 comments:

Mukund said...

Kindly give the explaination for the code.. I will be very much obliged. thank you

Mukund said...

Kindly give the explaination for the code.. I will be very much obliged. thank you

Anonymous said...

nice and easy explaination ...but the code should b elaborated a bit for the students who have just started datastructure...thank you..

Anonymous said...

Please explain the Code.

Anonymous said...

Genial dispatch and this enter helped me alot in my college assignement. Thank you for your information.

Anonymous said...

can u xplain d code with a simple em\xample

Anonymous said...

Copied from crack the interview!!! SUCKER!!

Goran said...

Could make use of recursion... much more effective and smaller!

public boolean move(int x, int y, Maze maze){

//If we found the cheese!
if (x==endX && y==endY) {
maze.printMaze();
return true;
}

/*Are we hitting a wall?*/
if(maze.isWall(x,y)) return false;
else maze.setTrail(x, y);
System.out.println("x:"+x+" y:"+y+" size:"+maze.getSize());

//First we try to move right:
if( (x+1)0 && this.move(x-1, y, maze) ) return true;
if( (y-1)>0 && this.move(x, y-1, maze) ) return true;

//No options... lets take a step back?
maze.clearTrail(x, y);

return false;

}

Anonymous said...

I think in the else part of function
while setting option value

It must be set as
option = 3 + next.row - here.row

amit said...

This blog is very interesting for me and others, I will return very soon for other items, thank you very much!


Ant treatment Vancouver

Anonymous said...

I blog quite often and I genuinely thank you for your information.
This great article has truly peaked my interest. I'm going to book mark your site and keep checking for new information about once per week. I opted in for your Feed too. sprawdĹş to, http://www.clubdiy.com/zbxe/index.php?mid=study_tusang&document_srl=1794

Anonymous said...


You actually said that fantastically!
My site: sex dziewczyny,
tani sex telefon: http://tanisextelefon.waw.pl

Anonymous said...

whoah this blog is magnificent i really like reading your articles.
Stay up the great work! You realize, many persons are looking around
for this info, you could help them greatly.

Feel free to visit my website :: calculate bmr

Anonymous said...

Spot on with this write-up, I seriously think this web site needs far more attention.
I'll probably be back again to read through more, thanks for the info!

My site :: diet that works

Anonymous said...

Howdy! This blog post couldn't be written much better! Reading through this post reminds me of my previous roommate! He always kept preaching about this. I most certainly will send this article to him. Fairly certain he'll have a
very good read. I appreciate you for sharing!


Check out my web-site :: raspberry ketones

Anonymous said...

Hello, I read your blogs daily. Your writing style is awesome,
keep up the good work!

My page: calories walking calculator

Anonymous said...

I am actually delighted to glance at this weblog posts which carries tons of helpful facts, thanks for providing these data.


Here is my blog :: calories walking

Anonymous said...

I don't know whether it's just me or if everyone else experiencing problems with your website.

It appears as if some of the written text within your content are running off the screen.
Can somebody else please comment and let me know if this is
happening to them too? This might be a problem with my web browser because I've had this happen previously. Thanks

Feel free to visit my blog post; cellulite treatment

Anonymous said...

I am really impressed with your writing skills and also with the
layout on your weblog. Is this a paid theme or did you customize it yourself?

Anyway keep up the excellent quality writing, it's rare to see a nice blog like this one these days.

my weblog :: magic flight launch box

Anonymous said...

Good web site you have here.. It's difficult to find quality writing like yours nowadays. I truly appreciate individuals like you! Take care!!

Here is my web site - how to file bankruptcy in florida

Anonymous said...

An intriguing discussion is definitely worth comment. I believe that you ought to publish more about this subject, it
may not be a taboo subject but generally folks don't discuss these issues. To the next! Cheers!!

Review my web blog ... prywatne ogłoszenia

Anonymous said...

Pretty! This was an incredibly wonderful post.
Many thanks for providing this info.

my web site Diet Plans

Anonymous said...

I love what you guys are up too. This type of clever work and coverage!
Keep up the excellent works guys I've included you guys to my blogroll.

my web blog :: frankrijk

Anonymous said...

Wonderful beat ! I wish to apprentice while you amend your website, how can
i subscribe for a blog site? The account aided me a
acceptable deal. I had been tiny bit acquainted
of this your broadcast offered bright clear concept

Feel free to visit my blog :: Urbanskaters.Co.Uk

Anonymous said...

It's a shame you don't have a donate button! I'd certainly donate to this superb blog! I guess for now i'll settle for bookmarking and adding your
RSS feed to my Google account. I look forward to new updates and will talk about this site with my Facebook group.
Talk soon!

Feel free to surf to my webpage: payday loan lenders

Anonymous said...

It's actually a nice and useful piece of information. I am glad that you shared this helpful info with us. Please keep us informed like this. Thank you for sharing.

my blog ... payday loans no brokers payday lenders not brokers

Anonymous said...

I just like the helpful information you provide in your articles.
I will bookmark your blog and test again right here regularly.
I am quite sure I will be informed lots of new stuff proper right here!
Good luck for the next!

Here is my web page ... vakantiewoningen frankrijk huren

Anonymous said...

Die fetten Brüste klatschen hierbei richtig laut und selbst die Muschis triefen ausschließlich so vor sich
hin. Einiges erkennst du schon gleich auf diesem Profilbild dieser Livestrip
girls, denn Features wie Webcams mit Ton, HD-Sex Webcams oder
3D-Cams, Dildocontrol und meiner Voyeurzugang werden direkt angezeigt, wenn vorhanden.
Auf meiner Livesex Seite namens Live-Strip gibt es die wohl
heißesten und viele fast alle Lesben Webcams die wir je gesehen haben.


Feel free to visit my web blog :: sexcam-sexcam

Anonymous said...

Machine printers will grant features if anyone else is in regard to to future
health. Plenty of people alcohol moisture immediately following they manufacture this method having something made
also very in good health. Element , Rr features brilliant manufacturer's warranty to actually slide before for in the case. Discover checking out, huge shard or sometimes a certain amount of pulp will finish ready essentially ejected.

My blog hand held blenders currys

Anonymous said...

Howdy! I'm at work browsing your blog from my new iphone 3gs! Just wanted to say I love reading through your blog and look forward to all your posts! Carry on the outstanding work!

Look into my web blog; Visiter le site web de l'utilisateur

Anonymous said...

Hi there friends, its impressive post concerning cultureand completely defined, keep it up all the time.


Here is my blog post; france map travel guide

Anonymous said...

I was able to find good info from your content.

My web page: master cleanse weight loss

Anonymous said...

Eіne feste Рartnerschaft suсhe ich nicht.
Dann schгеib mir unԁ lebe deіne Lust nun
mit uns zusammen аuѕ. Du wіrst eгstаunt ѕein, wіe heiß es
in еinem Wald werԁen könntе.

Lies mеine Webpagе partnersuche österreich

Anonymous said...

Around ain't anything else to know... They make majority of these juice extractors keeping the car safe but also usability idea. Each blender is amongst paramount appliances for the kitchen to hold. Its also wise to you should try merging many different fruits and veggies conjointly as a way to invent a range of types of on getting beverages.

Feel free to visit my webpage :: juicelady juicer 210

Anonymous said...

I am sure this piece of writing has touched all the internet viewers, its really really nice
article on building up new webpage.

my webpage; Calories Burned walking

Anonymous said...

The often preparing shaft could be very good and is correctly
installed in box, coffee mug in order to how the baskets.
A totally free seriously advise that you get one.
This method halogen oven as well as works to make a pot of soup,
nevertheless , crushes the ice and moreover makes in mid-air
smoothies too. It really is not on passivity that may discourages only out
of designing distinct most popular discs. Lots of tv shows over
the internet which in turn show you the simplest way
to rush, take apart, and even fresh new the assorted models.


Feel free to surf to my webpage: blender reviews

Anonymous said...

I needed to thank you for this very good read!! I certainly loved every little
bit of it. I have got you book marked to check out new stuff you post…

Here is my web page ... huis huren frankrijk

Anonymous said...

A lot of the by its shot for this joining together
wand attachment, since there are chrome steel razor blades in accordance with the house.
A tremendous special machine for those with limited funds.
You will have the comfort of successfully causing a satisfying positive liquid intake.


Also visit my web-site - Blender Reviews

Anonymous said...

Post writing is also a fun, if you know then you can write or else it is complicated to write.


my weblog; vakantiehuizen

Anonymous said...

Hi! This is kind of off topic but I need some guidance
from an established blog. Is it tough to set up your own blog?
I'm not very techincal but I can figure things out pretty quick. I'm thinking
about setting up my own but I'm not sure where to start. Do you have any ideas or suggestions? With thanks

my page; particuliere vakantiehuizen

Anonymous said...

Having read this I thought it was really enlightening.
I appreciate you finding the time and effort to put this short
article together. I once again find myself personally spending a lot of
time both reading and leaving comments. But so what, it was still worth it!



Look at my web blog - diet plans that work

Anonymous said...

sеtka

trаktoωał, iż ωszystek, co tyczyło sіę łоωóω Pгoclamations *hyperlinklist.net* nа smoki ѕtаłо ωіeԁzą taϳеmną.

Sаmodzielnіe wybitnie chciаł ϳeј гazu jeԁnego dostąpić,

przеto nagle ślеdził wszеlkie opeгacja.
Zaczеrwienіł ѕię.

Anonymous said...

You really make it appear so easy with your presentation but I to find this
topic to be really one thing which I feel I might by no means understand.
It seems too complex and very vast for me. I'm taking a look ahead for your next submit, I'll try to get the hang of it!


My website ... acid reflux article

Anonymous said...

Reviewing, connector lalannes effectiveness juice extractor is suffering from a
ideal nutritional supplement, simply just rich in exceptional aspects.
Ovum 100 % free Mayonnaise: Variation 1st trophy fat-free cottage cheese,
2 tablespoons oil, 1 tbsp . tap water, One specific tbsp . cider white
wine vinegar, 1st teaspoon dry off mustard,
1 or 2 tsp paprika and a noticeably splash of water
coming from all spice up. Thence they purchase just about anything that seems to regularly in
their wedding budget.

Feel free to surf to my site: mixers kitchen maid

Anonymous said...

It's truly very complex in this active life to listen news on Television, therefore I simply use web for that purpose, and get the hottest information.

my webpage - 자유게시판 - Açıköğretim sınav sonuçları açıklandı.

Anonymous said...

She recommends using a lightweight formula designed
for acne killer-prone skin, they
will improve your immune system and help it to combat undesirable bugs; take
two a day.

Anonymous said...

I could not resist commenting. Very well written!


Feel free to visit my website - detox diets ()

Anonymous said...

Way cool! Some extremely valid points! I appreciate you penning this article
plus the rest of the website is also really good.

Feel free to visit my site :: curly hair ()

Anonymous said...

If some one needs to be updated with latest technologies then
he must be visit this site and be up to date all the time.



Also visit my homepage; bmr calculator to lose weight

Anonymous said...

I every time spent my half an hour to read this weblog's content everyday along with a mug of coffee.

My blog: bachlaufpumpen solar

Anonymous said...

I am really impressed with your writing skills and also with the layout on your weblog.
Is this a paid theme or did you customize it yourself?
Anyway keep up the excellent quality writing, it's rare to see a nice blog like this one nowadays.

Also visit my blog post; http://www.bing.com/search?q=www.darmowe-sex-filmiki.org.pl&go=&qs=ds&form=FDNF

Anonymous said...

wonderful submit, very informative. I wonder why the opposite experts
of this sector don't realize this. You must proceed your writing.
I'm confident, you have a huge readers' base already!


my web site ... calvin klein underwear uk

Anonymous said...

Whoa! This blog looks exactly like my old one!
It's on a entirely different subject but it has
pretty much the same layout and design. Wonderful choice
of colors!

my site; mynationwidelending.com