Solutions and Discussion for Perl Quiz of the Week #17 (Expert Edition)

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.