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 <dondod...@gmail.com> 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 <ghat...@gmail.com> 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 <dondod...@gmail.com> 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 <piyush4u.iit...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com. > > > 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 algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
