Sample solutions and discussion Perl Expert Quiz of The Week #17 (20040602) Last year my mother-in-law gave me a delightful little puzzle, called "The Sphinx". It's seven variously shaped wooden tiles, which you try to arrange into various configurations. I did a lot of this kind of puzzle when I was younger; in particular I spent many many hours playing around with pentominoes, which are a set of 12 different-shaped tiles each made by sticking five squares together. Writing a program to solve pentomino puzzles is not hard, because the configuration you're typically trying to achieve has all the pieces aligned with the points of a square grid. The "Sphinx" puzzle was a nice change for me, because the tiles aren't square at all. I've illustrated the seven tiles at http://perl.plover.com/qotw/misc/e017/sph.jpg http://perl.plover.com/qotw/misc/e017/sph.ps Exact descriptions follow: Tile Description Angles Sides Area A Equilateral 60 60 60 1 1 1 1 triangle B Isosceles 30 30 120 1 1 S 1 triangle C Right triangle 30 60 90 1 S 2 2 D Right triangle 30 60 90 1 S 2 2 E Quadrilateral 60 150 30 120 1 S 2 1 3 F Trapezoid 120 60 60 120 1 1 2 1 3 G Rectangle 90 90 90 90 S 1 S 1 4 An "S" in the "Sides" column represents a side with length sqrt(3). The areas in the "Area" column are measured in multiples of tile A, which actually has an area of sqrt(3)/4 square units. Piece "E" is rather irregular. It is formed by taking a copy of tile C and gluing a copy of tile A to its short side. Tiles C and D are identical. It is permissible to flip the tiles over. And, of course, to rotate them or slide them around on the table. But it is not permitted to overlap them. Your job is to write a program which can solve Sphinx puzzles. The program will be given an input file which describes the configuration that into which the tiles are to be placed. See http://perl.plover.com/qotw/misc/e017/conf.jpg http://perl.plover.com/qotw/misc/e017/conf.ps for an example. The program should figure out a way to place the tiles into the specified configuration, if there is one, and report the arrangement unambiguously on the output; if no arrangement is possible, it should say so. It's up to you to determine the format of the input and the output. The puzzle, by the way, was designed by Nob Yoshigahara, a famous designer of puzzles. The Sphinx puzzle is a little out of his usual line. He specializes in puzzles in which you have to fit a bunch of objects into a container. For example, see http://www.johnrausch.com/PuzzleWorld/puz/pack_the_asparagus.htm ---------------------------------------------------------------- Regrettably, there is no sample solution available, because I did not complete one and because nobody sent one to the discussion list. However, there are still some points of interest. 1. I posed this quiz because I did not know a good way to solve the problem and I wanted to see what people would come up with. I think I did come up with a reasonably good general approach, which is described in some detail at http://perl.plover.com/~alias/list.cgi?1:msp:1740 I did try to do an implementation based on this idea, and I think I succeeded, or else I almost succeeded. But I wasn't entirely sure, so I didn't clean up the code and put it in order to serve as an example. There are two versions. The first one I did had a serious omission. It would search for a solution to the puzzle, and stop when it found one, but it wouldn't keep any record of how it had placed the tiles. So it would finish by saying "I found a solution," with no way of reporting what the solution was. Oops! I got to work on a second version that remedied this. The second version does not work right. I am not sure if the defect is in the search or in the code that generates the final display, and I didn't have time to find out where the problem was. If anyone is interested in tinkering with it, I put my code at http://perl.plover.com/qotw/misc/e017/sphinx1.pl http://perl.plover.com/qotw/misc/e017/sphinx2.pl 2. The output from version 2 of my sphinx program is in PostScript. I thought I'd take a moment to plug PostScript a little. PostScript is amazingly well-designed. It truly achieves the goal of making simple things simple and difficult things possible. Like Perl, it has a very gentle learning curve, you can get useful work done in PostScript with only a few simple features. The syntax is extremely simple. The language features are so clear and intuitive that one's can look at a program that contains unfamiliar constructions, make educated guesses about what they might be doing, and have a good chance of being correct. Over the past four years I've averaged about one PostScript project per year. Each project took me far less time than I expected it would, considering that I was working in a totally unfamiliar language. Each project was a huge success, yielding a large benefit in relation to the amount of time I had to put in. For example, a year or two ago I needed to write a tool that would take a series of PostScript documents and reorganize them into two-up format. It turned out to be 42 lines of Perl code, and I now use this tool all the time. This year I decided that if PostScript was yielding so much benefit for me even though I didn't know it, I'd get even bigger benefits if I actually tried to learn it. This has paid off. The complete language reference manual is available for free download from Adobe's web site. It is clear and pithy. With the language manual in hand, you can sit down and study a few sample PostScript programs and make a great start on learning the language. I have nothing bad to say about PostScript. People who know me may find this amazing. 3. Kevin Pfeiffer did some work on a solution to this quiz, but the code is in C++. (Great heavens!) http://www.tiros.net/pfeiffer/processing/2004/seven_tiles_in_progress/ Personally, if I were choosing a language in which to write this program, I would probaly pick Haskell or SML. C++ would be near the bottom of the list. Now that I think about it, PostScript might not be a bad choice. Rod Adams discussed a strategy for solution, and pointed out a complication: You'll need to check that the tile you are "subtracting" from the shape does not go outside of the shape at any other of the tiles corners. This is not a trivial task. Ah, but but but! In PostScript, it *is* a trivial task, because there is a builtin operator for it! 4. Ben Okopnik pointed out a similar project: http://gtans.sourceforge.net/ This one is written in C. Several people have posted favorable comments about it on the discuss list. 5. Nob Yoshigahara, the designer of this puzzle, died suddenly on Saturday. One of the eulogies on his mailing list read, in part: In 1977 [Nob] was complaining of the shortage of new puzzle ideas in Japan; but he was largely responsible for changing Japan into one of the best places for collectors to go puzzle hunting. I hope that God enjoys Nob's puzzles at least as much as I have. 6. My medical emergency is over. My apologies to anyone who was worried. I should have mentioned that although it was an emergency ("a sudden occurrence of a serious and urgent nature that demands immediate action") it was neither unexpected nor unwelcome. In any event, it has been resolved satisfactorily. Thanks to everyone who expressed concern. I will try to send a new quiz on Wednesday.