SOMA News 1 Jan 2006 E-Mail.

Burr Tools

Many puzzle solving programs have seen the light of day. Most of these specializing in one or two puzzles. Burr Tools is a completely different type of program.

Produced by Andreas Röver this program can be found on the homepage:

http://burrtools.sourceforge.net/
The current version is Version 0.1.9

Burr Tools capability is very different from most solvers, because it allow all kinds of pieces and movement constraints.

There is also a 60 page long documentation that explains all of the program you need to know to use it and also a bit of the internals.

BurrTools is not only capable of solving SOMA puzzles. It can currently solve everything made out of cube units and that is assembled in a cube grid.

Besides finding the possible ways to align the pieces to make the requested target shape the program can also analyze how the pieces can get into this position. That is even possible for puzzles where you need to shift the pieces around before it falls apart. You get nice animations to show you how to assemble the puzzle.

There is one assembly algorithm that does the search for assemblies. The algorithm is based on Donald E. Knuths "Dancing Link" Algorithm. There is a link for it on the webpage. The basic idea of this algorithm is as follows:
First transform the problem into a table. In this able each row corresponds to one possible placement of one piece inside the result shape that you want to assemble. And there are n+m columns. n for the number of pieces and m for the number of cubes that the result containt.
So let's see what is might look like for the "Soma Cube". Here the table has 7+27 = 34 columns. 7 for the pieces and 27 for the 27 unit cubes of the final cube assembly. Now each piece gets some rows. The 3 unit piece has 144 possible ways to put it into the cube (12 rotations times 12 places for each rotation). The T shaped piece has 72 rows (12 rotations times 6 places for each piece) and so on.
In each row of the table you have either a 0 or a 1. You have a one in the column of the piece and you have a 1 in the columns that stand of the cubes that are occupied by the piece in the placement that the row stands for.
Now all that needs to be done is find a set of lines from this table so that there is exactly one 1 in each of the columns of the selected set of lines.

The SOMA cube with solutions for Burr Tools is found here N060602SomaCube.xmpuzzle.

Lets look at this impressive feature list:
:) Will help you solve a certain kind of puzzle. Namely puzzles that are made out of square or dice shaped units and whose solution also contains only rectangular aligned pieces.
:) Does nearly all that PuzzleSolver 3D which is
:) You can enter all puzzles that are assembled out of dice shaped units
:) Find assemblies for you puzzle
:) Disassemble the found assemblies
:) Show everything in a 3 dimensional image
:) Animate how the puzzle has to be assembled
:) Toggle the visibility of pieces in the solution to have a look at the inner workings of a puzzle. This is especially helpful for box packing puzzles
:) Runs on Windows, Linux and OSX and probably other Unix variants as well.
:) You can specify which cubes to fill and which can be empty or full. PuzzleSolver 3D has only 2 modes. Either all cubes may be left empty in the solution, or the cubes that have an empty neighbor must be filled. BurrTools are more flexible here.
:) More than one problem in one file (e.g. have several Soma Cube problems in the same file)
:) Constraints to piece placements (like checkerboard)
:) Group pieces together to tell the disassembler that they don't need to be taken apart. This is necessary for puzzles like "Cube In Cage" where the cage can not be taken apart but has 3 movable pieces
:) No limits (or at least very high limits) to sizes and number of shapes. As long as your computer has the memory and you the patience the program will do it for you, even if it takes eons.
:) Create images that contain the pieces, or an instruction how to assemble the puzzle
:) Free as in beer. It doesn't cost you anything
:) Free as in speech. The source is available, so you can do your own programming or help me writing this software or even continue improving the program in case I have to stop working on it.
:) Save puzzles with solutions in compressed XML-files. This allows you to create puzzles with other means (like your own burrgrower, ...)
:) A library is provided that helps you to write your own software for puzzle design and analysis

Submitted (2.june.2006) by Andreas Röver <roever@users.sf.net>
Edited by Thorleif Bundgaard <thorleif@fam-bundgaard.dk>

BACK to news index