<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2657.73">
<TITLE>Perl 'Expert' Quiz-of-the-Week #17</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>-----Original Message-----</FONT>
<BR><FONT SIZE=2>From: Mark Jason Dominus [<A HREF="mailto:mjd@plover.com">mailto:mjd@plover.com</A>] </FONT>
<BR><FONT SIZE=2>Sent: Wednesday, June 02, 2004 6:21 PM</FONT>
<BR><FONT SIZE=2>To: perl-qotw@plover.com</FONT>
<BR><FONT SIZE=2>Subject: Perl 'Expert' Quiz-of-the-Week #17 [x-adr]</FONT>
</P>
<BR>
<P><FONT SIZE=2>IMPORTANT: Please do not post solutions, hints, or other spoilers</FONT>
<BR><FONT SIZE=2> until at least 60 hours after the date of this message.</FONT>
<BR><FONT SIZE=2> Thanks.</FONT>
</P>
<P><FONT SIZE=2>IMPORTANTE: Por favor, no enviéis soluciones, pistas, o cualquier otra</FONT>
<BR><FONT SIZE=2> cosa que pueda echar a perder la resolución del problema hasta</FONT>
<BR><FONT SIZE=2> que hayan pasado por lo menos 60 horas desde el envío de este</FONT>
<BR><FONT SIZE=2> mensaje. Gracias.</FONT>
</P>
<P><FONT SIZE=2>IMPORTANT: S'il vous plaît, attendez au minimum 60 heures après la</FONT>
<BR><FONT SIZE=2> date de ce message avant de poster solutions, indices ou autres</FONT>
<BR><FONT SIZE=2> révélations. Merci.</FONT>
</P>
<P><FONT SIZE=2>WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für</FONT>
<BR><FONT SIZE=2> diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser</FONT>
<BR><FONT SIZE=2> Mail. Danke.</FONT>
</P>
<P><FONT SIZE=2>BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de</FONT>
<BR><FONT SIZE=2> eerste 60 uur na het verzendingstijdstip van dit</FONT>
<BR><FONT SIZE=2> bericht. Waarvoor dank.</FONT>
</P>
<P><FONT SIZE=2>VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i</FONT>
<BR><FONT SIZE=2> voobshe lyubye podskazki v techenie po krajnej mere 60 chasov</FONT>
<BR><FONT SIZE=2> ot daty etogo soobshenija. Spasibo.</FONT>
</P>
<P><FONT SIZE=2>Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60</FONT>
<BR><FONT SIZE=2> Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4</FONT>
<BR><FONT SIZE=2> Xie4Lou4 Da2An4 De5 Jian4Yi4. Xie4Xie4.</FONT>
</P>
<BR>
<P><FONT SIZE=2>----------------------------------------------------------------</FONT>
</P>
<P><FONT SIZE=2>[ ADMINISTRATIVE NOTE: In my report yesterday, I included the wrong</FONT>
<BR><FONT SIZE=2> URL for the example programs. The correct URL is</FONT>
</P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/r017/" TARGET="_blank">http://perl.plover.com/qotw/misc/r017/</A></FONT>
</P>
<P><FONT SIZE=2> - MJD. ]</FONT>
</P>
<P><FONT SIZE=2>----------------------------------------------------------------</FONT>
</P>
<P><FONT SIZE=2>[ This isn't the quiz that I planned to send today; there are still</FONT>
<BR><FONT SIZE=2> some kinks we have to work out of that one. Once again I would</FONT>
<BR><FONT SIZE=2> like to encourage people to contribute quizzes or to volunteer to do</FONT>
<BR><FONT SIZE=2> sample solution reports afterwards. Send me mail if you are</FONT>
<BR><FONT SIZE=2> interested. Thanks, -MJD. ]</FONT>
</P>
<P><FONT SIZE=2>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.</FONT></P>
<P><FONT SIZE=2>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"</FONT></P>
<P><FONT SIZE=2>puzzle was a nice change for me, because the tiles aren't square at all. </FONT>
</P>
<P><FONT SIZE=2>I've illustrated the seven tiles at</FONT>
</P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/e017/sph.jpg" TARGET="_blank">http://perl.plover.com/qotw/misc/e017/sph.jpg</A></FONT>
<BR><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/e017/sph.ps" TARGET="_blank">http://perl.plover.com/qotw/misc/e017/sph.ps</A></FONT>
</P>
<P><FONT SIZE=2>Exact descriptions follow:</FONT>
</P>
<P><FONT SIZE=2> Tile Description Angles Sides Area</FONT>
</P>
<P><FONT SIZE=2> A Equilateral 60 60 60 1 1 1 1</FONT>
<BR><FONT SIZE=2> triangle</FONT>
</P>
<P><FONT SIZE=2> B Isosceles 30 30 120 1 1 S 1</FONT>
<BR><FONT SIZE=2> triangle</FONT>
</P>
<P><FONT SIZE=2> C Right triangle 30 60 90 1 S 2 2</FONT>
<BR><FONT SIZE=2> D Right triangle 30 60 90 1 S 2 2</FONT>
</P>
<P><FONT SIZE=2> E Quadrilateral 60 150 30 120 1 S 2 1 3</FONT>
</P>
<P><FONT SIZE=2> F Trapezoid 120 60 60 120 1 1 2 1 3</FONT>
</P>
<P><FONT SIZE=2> G Rectangle 90 90 90 90 S 1 S 1 4</FONT>
</P>
<P><FONT SIZE=2> An "S" in the "Sides" column represents a side with length</FONT>
<BR><FONT SIZE=2> sqrt(3). The areas in the "Area" column are measured in multiples</FONT>
<BR><FONT SIZE=2> of tile A, which actually has an area of sqrt(3)/4 square units.</FONT>
</P>
<P><FONT SIZE=2> Piece "E" is rather irregular. It is formed by taking a copy of tile</FONT>
<BR><FONT SIZE=2> C and gluing a copy of tile A to its short side.</FONT>
</P>
<P><FONT SIZE=2> Tiles C and D are identical.</FONT>
</P>
<P><FONT SIZE=2>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.</FONT></P>
<P><FONT SIZE=2>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 </FONT></P>
<P><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/e017/conf.jpg" TARGET="_blank">http://perl.plover.com/qotw/misc/e017/conf.jpg</A></FONT>
<BR><FONT SIZE=2> <A HREF="http://perl.plover.com/qotw/misc/e017/conf.ps" TARGET="_blank">http://perl.plover.com/qotw/misc/e017/conf.ps</A></FONT>
</P>
<P><FONT SIZE=2>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. </FONT></P>
<P><FONT SIZE=2>It's up to you to determine the format of the input and the output.</FONT>
</P>
<P><FONT SIZE=2>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</FONT></P>
<P><FONT SIZE=2> <A HREF="http://www.johnrausch.com/PuzzleWorld/puz/pack_the_asparagus.htm" TARGET="_blank">http://www.johnrausch.com/PuzzleWorld/puz/pack_the_asparagus.htm</A></FONT>
</P>
</BODY>
</HTML>