• 1. History
  • 1.1. First Encounter with the Logic Mazes
  • 1.2. Two Initial Scripts
  • 1.3. First Version of LM-Solve
  • 1.4. LM-Solve 0.4.0 and 0.6.0
  • 1.5. No BitKeeper for you!
  • 1.6. Recent Work
• 2. Technologies used by LM-Solve
  • 2.1. Makefile.PL
  • 2.2. Getopt::Long
  • 2.3. POD, Pod::Usage and Friends
  • 2.4. Writing an RPM Spec
• 3. Architecture of LM-Solve
  • 3.1. Multiple Solvers Implementation
  • 3.2. Registry
  • 3.3. The Input Module
• 4. Exotic Bugs
  • 4.1. The Hex Swamps Conundrum
  • 4.2. Recursion Limit
• 5. Links and References

• 1.1. First Encounter with the Logic Mazes
• 1.2. Two Initial Scripts
• 1.3. First Version of LM-Solve
• 1.4. LM-Solve 0.4.0 and 0.6.0
• 1.5. No BitKeeper for you!
• 1.6. Recent Work

• One day, an E-mail was sent to a mailing list I am a member of, referring to the "Theseus and the Minotaur" maze. (Originally at Oriel Maxime's Homepage)
• It took me two sessions in front of the computer, in each one spending several hours there, in order to solve it.
• Then I wondered: can a computer solve it as well?

• To find out, I wrote a Perl script (titled mino.pl) to solve it.
  • The script used global variables to manage its data.
  • It used a procedurally-recursive Depth-First Search scan to solve the board.
  • It worked!
• A Google search for "theseus minotaur" revealed that there was an entire site - www.logicmazes.com filled with other interesting puzzles with different rules. One of them that caught my attention was Alice Mazes.
• I took my mino.pl script and gradually converted it to solve Alice Mazes, this time using CVS to manage the code.

• I converted the design to an object oriented one that allowed solving both Minotaur and Alice Mazes as well as the Number Mazes that were also featured on the site.
• Meanwhile, I switched to using BitKeeper to manage my code, because I wanted a version control system that allowed copying and moving files.
• I released LM-Solve 0.2.0 which could solve Alice Mazes, Theseus and the Minotaur Mazes, and Number Mazes, with either Depth-First Search or Breadth-First Search.

• After a while I released LM-Solve 0.4.0 which could also solve three types of "Tilt Mazes".
• Eventually, LM-Solve 0.6.0 was released which could solve rectangular "Plank Puzzles", and could be built as an RPM package out of the box.

• The BitKeeper license changed in a way which I interpreted to mandate publishing the repository contents under a free software license. (it in fact just required making the contents of the repository available)
• I kept layouts of the boards in the repository which were neither under my copyright nor free.
• Thus, I believed was no longer able to use it.
• (I'm now using Subversion for this and other projects.)
• Since then, the BitKeeper license changed once again and now includes a non-compete clause. The current license requires mandatory upgrading, even if the new license has changed.

• A long break, followed by working on solving hexagonal plank mazes.
• Revamping the code, defining an API; adding POD documentation for it, putting on CPAN and releasing LM-Solve 0.8.0.

• 2.1. Makefile.PL
• 2.2. Getopt::Long
• 2.3. POD, Pod::Usage and Friends
• 2.4. Writing an RPM Spec

• I wanted the project to be easily installable so I had to learn how to use Makefile.PL effectively.
• It took quite a bit.
• Recipe:
  Put something like this in your Makefile.PL file:
  

use ExtUtils::MakeMaker;

WriteMakefile(
    'NAME' => 'Games::LMSolve',
    'DISTNAME' => 'Games-LMSolve',
    'EXE_FILES' => ["lm-solve"],
    'VERSION_FROM' => 'lib/Games/LMSolve/Base.pm',
    );

• Prepare a MANIFEST files containing all the files in your distribution, one per line.

• I needed a flexible command line processing, so I looked at Getopt::Long.
• Here's my code snippet:

    # This is a flag that specifies whether to present the moves in Run-Length
    # Encoding.
    my $to_rle = 1;
    my $output_states = 0;
    my $scan = "brfs";
    my $run_time_states_display = 0;

    #my $p = Getopt::Long::Parser->new();
    if (! GetOptions('rle!' => \$to_rle,
        'output-states!' => \$output_states,
        'method=s' => \$scan,
        'rtd!' => \$run_time_states_display,
        ))
    {
        die "Incorrect options passed!\n"
    }

• ! options are boolean. (specified with --rle and --norle)
• =s options accept a string argument.
• pass_through configuration option - process the known arguments and leave the others alone - used for determining the game variant.

• Pod::Usage is a module that displays the POD page associated with the program.
• The following snippet invokes it:

    my $variant = $self->{'default_variant'};
    my $help = 0;
    my $man = 0;

    Getopt::Long::Configure('pass_through');
    GetOptions(
        "g|game=s" => \$variant,
        'help|h|?' => \$help,
        'man' => \$man
        ) or pod2usage(2);

    pod2usage(1) if $help;
    pod2usage(-exitstatus => 0, -verbose => 2) if $man;

• Read the perlpod man page for learning how to write POD. POD is easy and fun, and can be converted to many formats. It is especially useful for writing man pages.

• I wanted LM-Solve to be installable by RPM, and so had to write an RPM Spec.
• After some experiments, I realized that a good way to generate the RPM Spec based on the current version is to put the generation routine in Makefile.PL.
• Building a portable RPM required a bit of experimenting. I can suggest anyone to use my RPM Spec as a skeleton for his own module.

• 3.1. Multiple Solvers Implementation
• 3.2. Registry
• 3.3. The Input Module

• A base class (Games::LMSolve::Base) that handles the scanning logic, without knowledge of the rules of the game.
• Several derived classes (one for each game variant) that supply it with the game-specific logic.

• To manage the different variants solvers and to instantiate the appropriate solver, there is a registry class.
• This class manages a variant ID to class associative array and invokes the right class accordingly.

• The Games::LMSolve::Input module is a utility module used for inputting the board layouts.
• Its board is a set of key = value pairs where there are several types of values. Namely, integers, X-Y pairs, Start-End pairs, and arrays are supported. (albeit not all possible combinations).

• During the development of LM-Solve, I had to deal with many bugs that crept up during the development.
• In this section, I will present several of the more "exotic" ones and how they were resolved.

• 4.1. The Hex Swamps Conundrum
• 4.2. Recursion Limit

• When implementing the Hex planks in the swamp game, I encountered a situation where the first game I tried to solve was unsolvable by the solver.
• To solve it, I programmed a proto-game, that let me play the puzzle, and check each state I reached, whether it was also reached by the solver.
• I then discovered the problem (a moved plank was blocked by its origin state).
• Here's a screenshot of the game:

• When first using the procedurally-recursive version, warnings were given for deep recursion.
• Deep recursion on subroutine "main::sum" at recurse.pl line 17.
• To resolve it one can specify no warnings "recursion".
• However, the perl debugger still warns about "100 levels deep in subroutine calls!".
• To resolve this set the $DB::deep to a large enough value from within the perl debugger.

General Links

• The LM-Solve Homepage
• The Logic Mazes Site - the site by Robert Abbott that contains Alice Mazes, Theseus and the Minotaur puzzles, a Sliding Door Maze, Number Mazes and other resources
• Click-Mazes by Andrea Gilbert - a site that contains many Logic Mazes and puzzles of many kinds.
• Yoah Bar-David's Site - contains interactive Java applets that can be used to construct and solve Alice Mazes, and Theseus and the Minotaur Mazes.

Project's Resources

• LM-Solve's Freshmeat Record - contains history and links.
• GitHub Repository - online version control repository for the project.
• Solving Puzzles with LM-Solve - a Perl.com article about extending LM-Solve to solve a new puzzle.