My first thought for your algorithm is to essentially follow the solution path that your user might end up taking. Your user will be clearing areas out, opening them up. Your algorithm could start with an empty grid and fill in around a starting seed, growing the tile array outward.
1) empty grid 2) generate random sequence of pairs with the blank embedded in it, such as 4,4,27,27,1,1,36,<blank>,36, etc 3) choose random location for first tile, and place it there, and take it off the pair queue. 4) choose an unfilled location which is 4-connected to any filled location, and put the next tile from the queue in it. 5) repeat 4) until the queue is empty. In this system, putting the "blank" in a location counts as filling that location, so the value for "blank" needs to be different than the initial values in the grid. So for example, if -1 means uninitialized and 0 means blank: -1,-1,-1 -1,-1,-1 -1,-1,-1 then -1,-1,-1 -1,-1,04 -1,-1,-1 then -1,-1,04 -1,-1,04 -1,-1,-1 then -1,-1,04 -1,27,04 -1,-1,-1 then -1,-1,04 -1,27,04 -1,27,-1 then -1,-1,04 01,27,04 -1,27,-1 then -1,-1,04 01,27,04 -1,27,01 then 36,-1,04 01,27,04 -1,27,01 then 36,00,04 01,27,04 -1,27,01 then 36,00,04 01,27,04 36,27,01 This guarantees that a solution exists, because the algorithm essentially traces out the solution as it generates the level. This presumes that players are not allowed to move tiles around yet leave them on the board while solving the puzzle - it assumes that tiles just disappear from the grid when the user selects a pair which has a clear path between it, and that's the only interaction allowed. If they can slide them around, my algorithm will still produce solve-able puzzles, but they won't be as difficult as they could be, I think. :) Interesting problem! Dave On Wed, Mar 11, 2009 at 6:09 AM, Glen Pike <[email protected]>wrote: > Jobe Makar's book about Flash Games Demystified has a wordsearch that > shuffles words in a grid - it will keep shuffling upto a point, then decide > that it is getting nowhere and try again. There may be some examples of > this sort of thing online - I have the book at home if not :) > > > Paul Steven wrote: > >> I am trying to write the code to populate a 9 by 9 grid of tiles with 40 >> pairs of matching tiles. >> >> I have 4 different types of tiles and I want to create a grid that has 40 >> matching pairs and 1 blank tile. >> >> I do not want the pairs all to be next to each other but there needs to be >> at least one solution that enables a player to match each and every pair. >> To >> match a pair there needs to be a clear path between each member of the >> pair. >> >> 1,2,1 >> 2,0,3 >> 4,4,3 >> >> In this simple example, a user could clear all tiles by matching in the >> following order: >> >> 4 - 4 >> 3 - 3 >> 2 - 2 >> 1 - 1 >> >> Note that until they have matched the pair of 2's they cannot match the >> 1's >> as there would be no clear path between them. >> >> All my attempts so far to create this grid is resulting in script errors >> due >> to my code being unable to find a solution. My code basically gets about >> 60% >> of the board created then finds it cannot any more clear paths to create >> the >> remainder of the grid. >> >> I would really appreciate any help cracking this function. >> >> Thanks >> >> Paul >> >> >> _______________________________________________ >> Flashcoders mailing list >> [email protected] >> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders >> >> >> >> > > _______________________________________________ > Flashcoders mailing list > [email protected] > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > _______________________________________________ Flashcoders mailing list [email protected] http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
