artist has asked for the wisdom of the Perl Monks concerning the following question:

Math and Perl both are my passion. I am trying to solve various puzzles with Perl and need little help in solving the same. Especially the block puzzles. For example, how do I solve 'How many consecutive width 'L' shapes I can fit exactly within a square or mxn rectangle?

I don't have any strategies to begin with. Challanges like this and others interest me which I collect over various sites. I appreciate any and all input to begin with. Thank you,
artist

Replies are listed 'Best First'.
Re: Solving Puzzles
by wufnik (Friar) on Jul 28, 2003 at 06:52 UTC
    hola artist;

    look forward to seeing the product of your puzzle perousals; in the meantime, here are some ideas which are i hope relevant to your problem:

    i believe general answers to puzzles of this type are to be found in the maths of tilings, which deal with whether or not a particular repeating unit can 'tile' space (2d in your case), and allows you to calculate the number of repeating units etc.

    a good initial link to the subject can be found at http://www.ics.uci.edu/~eppstein/junkyard/tiling.html

    i think the type of shapes you are dealing with in particular - the L shape & variants - are 'polyominoes'. good link on this:

    http://student.cusu.cam.ac.uk/~jsm28/tiling/

    no set of links on tilings would be complete without a reference to beautiful, aperiodic penrose tilings. here is one:

    http://www2.spsu.edu/math/tile/aperiodic/

    best wishes,

    wufnik

    -- in the world of the mules there are no rules --
Re: Solving Puzzles
by pzbagel (Chaplain) on Jul 28, 2003 at 06:18 UTC
        I don't have any strategies to begin with.

    Therein lies the rub. Remember, Perl is a programming language. And programs are simply lists of instructions. You have to figure out what that list is going to be. In order to write a script to help solve a problem, you need to develop a strategy and then convert it into perl code and test.

    Let's take your example above, you can quickly write a Perl program that uses a 2D array to represent the rectangle and then simply write some code that will brute-force every possible combination of "L" shapes in it. This works fine when your grid is small and rectangular, but what happens if it gets larger and/or is oddly shaped. Suddenly, processing time goes through the roof.

    You have to do a couple by hand, and analyze your thought process. You want your Perl program to use that same process or similar one. Remember, computers are fast so they can trade off some iteration for heavy logic pretty easily. The key is to break down your solution into logical steps so they can be expressed in a program.

    Now I'm assuming you want to stick to Perl for your language. Once the complexity of problems goes up, you may get benefits from switching to a language for suited for AI type work such as Lisp. But in the end, you'll have to figure out strategies for your problems so you can give your solution scripts an advantage when they attempt to tackle the problems.

    HTH

      >>I don't have any strategies to begin with.
      >Therein lies the rub.
      Not necessarily. Genetic algorithms, anyone?
Re: Solving Puzzles
by Skeeve (Parson) on Jul 28, 2003 at 06:00 UTC
    1. find a representation for your m×n rectangle.
      e.g. my @rect=[ (1) x $m ] x $n;
    2. find a representation for your L-shapes
    3. code some functions to turn or flip your shapes
    4. code a function that will put one L-shape in every possible orientation into each possible location of your rectangle
    5. after each time putting it in, the function should call itself in order to put another L in
    6. if all possiblities are tried, the function has to return
    That's just one stupid strategy I can think of. With this I solved a puzzle many years ago in LOGO on my C64. I couldn't sleep that night because each time a solution was found, the printer made a loud noise printing it ;-)
Re: Solving Puzzles
by halley (Prior) on Jul 28, 2003 at 13:03 UTC
    You may be able to adapt portions of my Pentominos Solving Quine. It's currently brute-forcing a fixed set of twelve different pieces, but it wouldn't be hard to make it play with a set of identical pieces and report best near-solutions. See the link there to the pre-obfuscated version with full comments and POD.

    If you're interested in using this code as a starting-point, but still need a little help, let me know.

    --
    [ e d @ h a l l e y . c c ]