Hmmmmm. Then a way to look at it is like this: Find a way. Find n-1 other ways which are not the solution.
You can use a random path generating algorithm, starting from one side, selecting a random cell from the possible 8 cell neighborhood, and then repeating the process till you get to the end. This will give you the only correct, random path. Now it is a matter of creating n-1 other random paths which are not the solution in a similar fashion. The beauty is that they will intersect each other as the number increases and will increase complexity in the process. On Fri, Feb 8, 2013 at 3:51 AM, Don <[email protected]> wrote: > I believe that this will generate a maze with multiple cycles, which > violates the requirement stated in the initial question that the maze > have exactly one solution. > > On Feb 6, 11:53 am, Anup Ghatage <[email protected]> wrote: > > There is another algorithm.. The one which involves random division. > > > > Basically, given an M x N matrix > > > > ________________________ > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > |...............................................| > > > > Draw a random line intersecting the maze vertically, then draw another > > random line intersecting it horizontally. > > > > ________________________ > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > |______.|________________.| > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > > > Now since you've got a 'plus' like formation of the two new lines, create > > an opening on each of the new intersecting lines, one on each side of the > > intersect > > > > ________________________ > > |.............|.................................| > > |.............|.................................| > > |...............................................| > > |..............|................................| > > |__....___|_______......______| > > |.............|.................................| > > |.............|.................................| > > |.............|.................................| > > |...............................................| > > |.............|.................................| > > |.............|.................................| > > > > Now you've got 4 new matrices, recursively go ahead drawing more > > intersecting lines on them such that the new ones don't have one end > point > > in the open. > > > > Regards > > > > > > > > > > > > > > > > > > > > On Wed, Jan 30, 2013 at 8:19 PM, Don <[email protected]> wrote: > > > It is George Marsaglia's multiply with carry pseudo-random number > > > generator. It has a period of 2^32, which is long enough for this > > > purpose. It is about as good as a 32-bit rng can be. In real life I > > > use the Mersenne Twister, but I wanted something simple to include > > > here. > > > > > Don > > > > > On Jan 29, 11:46 pm, Piyush Grover <[email protected]> wrote: > > > > @Don can you give the logic of your rnd() function? > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To unsubscribe from this group and stop receiving emails from it, send > an > > > email to [email protected]. > > > For more options, visithttps://groups.google.com/groups/opt_out. > > > > -- > > Anup Ghatagewww.ghatage.com > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- Anup Ghatage www.ghatage.com -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
