"stand" in the middle of a square, and the "walls" are always square
boundaries.
The most basic strategy is just to pick a wall an follow it. You'll be
stuck in one of three situations: a loop, a solution path, or an unsolvable
maze (which is a subset of loop).
Detecting a loop is as simple as checking that you never occupy the same two
sequential squares in the same order. If you do, you're looping. If you
detect a loop, then you have to somehow start on a new path.
Since you're solving with a computer, it's easy enough to track the places
you've been, so just wander until you reach a place you haven't been, or
start a new course (follow the other wall) from the place you are.
Detecting an unsolvable maze is nastier, because you have to actually do
some plot checking. If you plot everywhere you've been, and the outer edge
of all those places are all "walls", then you know you cannot escape from
that area. If you've not found a solution by the time that condition is
true, then you're in an unsolvable maze.
Following a wall is certainly not the optimal solution in terms of steps,
but it's one that should ALWAYS work.
To reduce the number of steps, I think I'd start by tracking everywhere I've
been, and where there were walls, as if I were computing whether I'm in an
unsolvable maze. Then whenever I got to a square that gave me a choice of
which way to turn, I'd analyze my plot, and try and compute which direction
was the most "open". Of course, on a complex maze, you'll probably have a
lot of "correct" turns that point you into a nearly closed space, then twist
around, and escape out of the last hole in that area.
I've not actually written any code based on these thoughts, but thought I'd
share anyway.
Cheers,
barneyb
> -----Original Message-----
> From: Jim Davis [mailto:[EMAIL PROTECTED]
> Sent: Friday, January 16, 2004 1:10 PM
> To: CF-Talk
> Subject: RE: Fancy a ColdFusion Challenge?
>
> That I could see - especially for this challenge.
>
> No code, but a theoretical overview of "maze solving" (path
> choice, path
> abandonment, etc) could be beneficial. The same might not
> work for all
> challenges but maybe for this one.
>
> (I'm apparently the guy who would rather talk about the challenge of
> challenges than actually try to meet the challenge. ;^) )
>
> Jim Davis
>
> _____
>
> From: Casey C Cook [mailto:[EMAIL PROTECTED]
> Sent: Friday, January 16, 2004 3:45 PM
> To: CF-Talk
> Subject: Re: Fancy a ColdFusion Challenge?
>
> I figured someone would post this response. Typically I just
> need a place
> to start, this doesnt take any creativity out of it, is just
> starts the
> process of creative thinking. Ever ask consult a coworker
> about a problem
> you've run into with code, not expecting them to have the answer, but
> something that you can take away from the conversation that
> will help your
> thinking arrive at a solution?
>
> CC
> _____
>
>
>
[Todays Threads] [This Message] [Subscription] [Fast Unsubscribe] [User Settings]
