Mark Pilgrim introduced Matchmaker, a fun bit of image generation - the puzzle is to find the unique match from a number of very similar tiles.
Given that there are so few color combinations, it seems reasonable to sample the pixels, use squash ordering to find an index for the image, then check an array to determine if that image has already appeared. On average N/(2^0.5) where N is the total number of images.
Thomas Andrews does an excellent job explaining how squashed ordering works.
I used this technique when working on the Fairy Chess exercise for Test Driven Development.
Mike coded a version of this puzzle as well, which is a lot easier, because his implementation allows you to specify the colors
May 8, 2003 2:54 PM
| TrackBack
Actually it would be easier than that; internally the patterns are represented as strings, so simple concatenation and a string hashing technique like MD5 or SHA could be used to track unique puzzles.
Comment by: Mark May 8,2003