i am a beginner in C made to do a course in data structures...i have been given a problem wich reads as such..
"Write a program to solve a maze (with single entry and single exit) puzzle using stack data structure."
can u please provide me a way to go about it??i will be highly obliged...
and please donot say that 'u ought to provide some previous working of this problem' as i donot how to go about it other than writing the standard header files...thanx if u help me out....
We're not going to write the program for you. Where are you stuck? You don't know how to implement the stack? You don't know what a maze is?
If you understand what you're doing, you're not learning anything.
y dun u understand ..plz help me out somehow..i told u i dunno how to go about it..atleast help me with the concepts...
You should have learned about the concepts required in class. If not, you should google them.
And use real English. This shorthand "y dun u" "plz" crap isn't helping you.
And you still didn't answer my questions. If you're not going to put forth any effort then neither is anyone else.
Last edited by itsme86; 09-18-2006 at 08:56 AM.
If you understand what you're doing, you're not learning anything.
Originally Posted by coolvik87
Specifically, in your case you'll have to answer a few questions. What does the maze data look like? How will you get the maze data into your program? Why would you even want to use a stack to solve a maze? Is a stack sufficient for maze-solving? Fortunately, most of this thinking has probably already been done for you in class. Unfortunately, it appears you missed those parts.
- Read some references.
- Write some code.
- Test some code.
- Repeat.
Heh, I enjoyed the conditional thanks.
Last edited by pianorain; 09-18-2006 at 09:15 AM.
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
a) Do you know what a stack is ?
b) When you know what a stack is, then use the stack whenever you get to a junction in the maze (so you can get back to that junction later on).
When you get to a dead-end, go back to the previous junction.
That's pretty much all there is to it.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Some idea's for you to consider:
A "stack" is like a plate dispenser in a diner. Newest plate to the stack, sits right on top, and will be used first, before the plates beneath it. That's called FILO (first in, last out), or LIFO (last in, first out).
So in the maze, we don't know WHICH way to go, so we're basically just using trial and error, here. But we need a way to get back to previous locations, if we take a wrong turn and wind up in a dead end.
Each location is an x & y coordinate, on our screens. Sometimes called a "Cartesian Plane". x is the horizontal location, y is the vertical location, within that plane.
So we start, our stack is empty. Say the entry door is at 2, 3 (x,y). We have three choices we could make for our next move - left, middle, and right we'll say.
Let's choose left, we push 2,3 onto our stack, and goto 1,4 (x,y). It's a dead end, and now we need to come back and pick another path thru the maze.
So, we Pop off our last item on the stack, and see "Hey, it's 2,3", and that's just where we need to go to start another path.
Every location, before we go to the next location, gets put onto the stack. It's our trail of breadcrumbs or thread of string, that will always guide us back, no matter how many steps are in the wrong direction.
It's important to make your choices among the possible routes, in an orderly way. Maybe left to right on the x values, or right to left, or whatever. But it helps to keep the guesses being chosen, in some consistent order.
This isn't really a toughie, but it's not trivial, either. I'm concerned about your seeming to be rather far behind the knowledge you need for this.
Good luck, and get to work. Come back and show us your code and any questions.
Adak
If you didn't listen in class, well, that's your %$!#% problem. We don't give free lessons.
But if you want lessons you can contact me for a good price.
You first think: how would you solve a maze, given that you can only see the current square at any time? You'd need a piece of paper to record down which direction you went in the previous junction so you won't repeat it when you get back. The stack will function as your piece of paper.
Personally, I would just treat it as a graph and do Dijkstra's. It makes me feel all warm and fuzzy inside
Code:#include <stdio.h> void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){ puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9 /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i] ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][ t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}
