IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra cosa que pueda echar a perder la resolución del problema hasta que hayan pasado por lo menos 60 horas desde el envío de este mensaje. Gracias. IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la date de ce message avant de poster solutions, indices ou autres révélations. Merci. WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser Mail. Danke. BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de eerste 60 uur na het verzendingstijdstip van dit bericht. Waarvoor dank. VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i voobshe lyubye podskazki v techenie po krajnej mere 60 chasov ot daty etogo soobshenija. Spasibo. Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60 Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4 Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4. ---------------------------------------------------------------- [ ADMINISTRATIVE NOTE: In my report yesterday, I included the wrong URL for the example programs. The correct URL is http://perl.plover.com/qotw/misc/r017/ - MJD. ] ---------------------------------------------------------------- [ This isn't the quiz that I planned to send today; there are still some kinks we have to work out of that one. Once again I would like to encourage people to contribute quizzes or to volunteer to do sample solution reports afterwards. Send me mail if you are interested. Thanks, -MJD. ] 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