<\body> ||>> <\table-of-contents|toc> <\with|par-mode|right> \ <\with|par-mode|right> \; \; What are ? contain two main parts. On the one hand there is a program that assembles and disassembles burr-type puzzles. That program contains a graphical user interface (GUI) which allows creation and editing puzzle definitions, solving the puzzle and the display and animation of the found solutions. This is probably the most interesting part for most people. On the other hand there is a >> library that may help with the search for and design of new puzzles. This library contains all the necessary tools to write programs that do the things that the graphical interface does (and more). The first part of this document describes the graphical program. It should contain descriptions of all concepts and explain how to use them in the GUI program. The second section will contain a description of the library and some internals. Also, some of the used algorithms are explained. This section is probably only interesting for people wanting to use the library for their own puzzle design explorations. But first a little bit of history of this program. There are already two programs that do the same that can do. One is written by Bill Cutler. Cutler's programs are very versatile, they even can handle space grids different from cubes. The other one is by André van Kammen. I had bought this program a while ago and have generally been quite satisfied with it. I have taken over quite some ideas from the GUI that André developed. So why another program you might ask. Here are a few reasons: <\enumerate-numeric> The available programs are not for , which is my operating system of choice, the available programs are binary only programs and hence it is quite hard to do more interesting things like burr growing in an automated way, the programs do cost money, seems to be abandoned. There hasn't been any update for quite a while, and has some nasty limits to the shape sizes and the number of possible placements. Anyway, I was not completely satisfied with the available software. Then in summer 2003 a German computer magazine, started a competition to write a program that counts the number of solutions to a merchandising puzzle of them as fast as possible. My program wasn't the fastest but it was the starting point for the . As there are many people out there that are a lot more creative than I am and that could use a program like this to design nice puzzles I decided to make it public and free<\footnote> Free as in free speech and as in free beer (see ) . I added a GUI that can work on many operating systems, including and . This has the disadvantage that the GUI looks a bit different from what the normal user is used to, so stay calm if things look a bit unusual, they behave in fact quite similar to how a normal -program behaves. Lately 2 people played important roles in the development of the program. These 2 are Ronald Kint-Bruynseels and Derek Bosch. Ronald has rewritten the first part of this manual and has generally contributed lots of well organized suggestions. Derek is resposible for the OSX port of the program. Without him there would be no binary for this operating system available. I want to thank both of them for their work. I also want to thank all the other people that have sent in bug reports, suggestions and praise. Their input is very welcome and cruicial to the further development of the program. All this work has taken nearly 3 years to reach the current state, I hope it was worth it and you have a lot of fun with the program. \; <\with|par-mode|right> Andreas Röver <\with|par-mode|right> The first part of this user guide is written from a approach. Rather than sequentially describing the elements of the GUI and their functions, this manual guides you through the program the way you should create your first design in tems may be briefly repeated in several places of the text. Although too much redundancy has been avoided. Throughout the text the following fonts and notations are used: \; <\with|par-mode|left> <\with|par-mode|right> ||||||>|>|>|>|.>>|>|>|>>|depth explanation follows.>>|>|>|>|>|>|>|>>|'.>>>>> is an software project. The most recent release of the program is always available for download at the website: <\with|par-mode|center> \ \; At the bottom of that page you can select the proper download for your operation system. This will bring you to the download page where you have to select a mirror site to start the downloading. It's highly recommended to select the mirror site on the server nearest to your location. users can either download the >> (a zipped file which needs manual extraction and installation) or the self-extracting . Unless you have a slow connection to the internet downloading the intaller is probably the best option. To use on a platform you can either download provided precompiled version or the files and compile the program on your system (see installation guidelines below). If you downloaded the , just extract the file into the directory of your choice and the GUI is ready to be used. When you opted for the , start the executable and follow the instructions on your screen. For detailed installation instructions please refer to the manual or help files of your operating system. For users comes in two versions: a precompiled binary and source code. The binary is provided in the hope that it is working on many variants of the OS. It is compiled for intel processors and requires a more or less modern system. As distinct versions of differ widely it is likely that the binary will not work for your system. In that case you need to compile yourself. If you want to try the binary, just download the archive with the current version. Decompress the archive into a directory of your choice and start within that directory. It either works or it doesn't. If it doesn't make sure you have at least the following libraries installed on your system: , , and . Of course you also need a working X windowing system. If the program still doesn't work call from the console within the path where you decompressed the files. This will list all libraries required by the binary and where the system could find them. If one of the listed binaries is not available try to install that. If all that doesn't work you should consider compiling on your own or mail me. These installation instructions just contain some hints for the compilation of . As requires a few not so widespread libraries it is not the easiest task to do this. To install for you first need to make sure you have the following libaries installed: , , and . These libraries are usually installed on every system. You just have to make sure that you have installed the development packages, otherwise it is not possible to compile a program that use these libraries, but just start programs that use them. Additionally the following libraries are required: , and . is the library used for the GUI of . It may be included in your distribution or it may not. The problem is that we need a version of this library that is not compiled with the default switches. This library must be compiled with C++ exceptions enabled. If you don't do this the program will simply shut down when an internal error occures instead of displaying an error message and making an emergency save. To compile with exceptions enabled you have to do the following: <\itemize-dot> Download and decompress as usual Run just as usual Remove from the file Finish normally be calling and > It is of course possible to use a normal version of the library, you just don't get the emergency save feature if there is a bug in the GUI of . But as the number of bugs is hopefully quite small right now that should not be such a big problem. is not included in most distributions. So you need to install it manually. It is installed in the usual way. Refer to installation instructions of that library. can be compiled without but then the File Open Dialog is really ugly. The last library, , can be hard to find, so here a link <\with|par-mode|center> This library is compiled and installed in the usual unix way, read their installation documentation. Now can be compiled and installed the usual way with , , . After installing the following files should be on your system: \; <\with|par-mode|left> <\with|par-mode|right> ||||>|.>>|>|>|>|. This file may be deleted to save on disk space, but should always be included when sharing the program. Read it carefully before sharing or modifying the program.>>|>|>|>|>|>|. Here all (more or less important) changes to the different versions are collected in a comprehensive list. This is probably the place to look for what changed when downloading a new version. This file may be deleted to save on disk space.>>|>| with the .>>>>> Also a new folder, , is created. This subdirectory contains a few examples of existing puzzles that illustrate the capabilities and functions of . A brief overview of the examples is presented in Appendix . Before we start describing the functions of , let's synchronise our use of vocabulary and explain a few concepts that crucial to the way works. <\description> A voxel is a space unit in the 3-D space. The shape of the voxels is defined by the space grid type. Currently only supports cubic voxels. Each voxel has one of the following three states: , () and (>). Additional to that each voxel can also contain supplementary information in the form of colours that are attached to the whole or parts of that voxel. Currently can only attach one single colour to the voxel as a whole. This is a definition of a 3-dimensional object. Shapes are assembled out of voxels.\ A piece is a shape that is used as a part of the puzzle. Some pieces may have the same shape. requires you to tell it that two or more pieces do have the same shape, otherwise it will find all solutions with all permutations. So a multipiece is a piece that's used more than once in the problem. A collection of pieces (and/or multipieces) than can move with respect to each other, but cannot be separated from one another. Denoted with {}. This is the shape that the pieces of the puzzle are supposed to assume once the puzzle is assembled. A problem in consists of a list of pieces and/or multipieces, a result shape and possibly some constraints. You can have more than one problem in a file as it may be possible to have more than a single task with the same set of pieces (e.g. Piet Hein's ). In other words, a problem is a statement about with the pieces. A puzzle is either a single problem or a collection of problems. A unique code to identify a shape, colour or problem. This consists of an automatically assigned prefix to which a custom name may be added. An assembly is a physically possible (meaning the pieces do not overlap in space) arrangement of pieces so that the resulting shape is formed. It is not guaranteed that it is actually possible to get the pieces into the positions of the assembly without using advanced technologies like Star Trek beaming. A Solution is an assembly with instructions how to assemble/disassemble the pieces. The part of the program or algorithm that tries to assemble the puzzle. The part of the program that tries to find out how the pieces must be moved to assemble the puzzle. It does this by trying to disassemble an assembly. Some puzzles like don't require checking for disassemblability, they are always constructible. That's why these two tasks are separated. A short name to refer to the assembler and disassembler as a unit or just one of these without specifying which one. As described above works with shapes which are merely a collection of voxels that each can have either one of three different states: , or . Particularly the difference between fixed and variable voxels has a great impact on the way the solver works and which solutions are considered to be valid and which are not. Besides that, the validity of solutions can be further restricted by imposing colour constraints.\ <\description-compact> The empty state is rather superfluous as it can also be regarded as the absence of any voxel. It is just used in the result shape to indicate the spots that can't be filled at all (holes). The normal or fixed voxels in the final result, otherwise it is not considered to be a valid assembly. The variable state is used to instruct the program that for a particular voxel it is unknown whether it will be filled or empty in the final assembly. This is required for puzzles that have holes in places (like all the higher level six-piece burrs). All voxels that be empty >>> have the > state in the result shape. The variable state can only be used in > and the solver will pop up an error message whenever it encounters a variable state in a normal piece. The question now is: ? This is a matter of speed. When the program tries to find assemblies and encounters a voxel that it is unable to fill with the available shapes it can immediately abort if that voxel has the filled state in the result shape. As the algorithm is instructed that it fill this particular voxel but it cannot do so, something is wrong. On the other hand, If the state of that voxel is variable the algorithm knows nothing and has to carry on. Colours allow you to add constraints to the possible placement of pieces. This is done by assigning a colour to one or more voxels of the piece(s) and the result shape (>). Then you can set some colour placement conditions for each problem (>). The program will place pieces only at positions that fulfil the colour conditions defined. These colour conditions currently allow the definition of what coloured voxels of the pieces may go into what coloured voxels in the result shape. The is different, since it always fits. Voxels in a piece that are in the neutral colour fit everywhere and neutral coloured voxels in the result shape can accommodate for every piece voxel, independent of its custom colour. Currently the assigned colour is used just like painting the whole voxel with this colour, but in the future more advanced possibilities for colouring and conditions may be added. was initially very much based on by André van Kammen but diverged quite a bit from that. We strongly advise you to read this user guide since there are some features in that work somewhat different as their counterparts in and there are also some functions that PuzzleSolver3D doesn't have. Below are the most prominent differences that need your attention: \; <\enumerate-numeric> doesn't handle holes automatically as does. This may at first sound like a disadvantage but in fact it isn't. Unless you select on the solve tab, treats all cubes of the target shape as cubes that might be filled but don't need to be. Cubes that be filled however speed up the search process. The more there are of these (as compared to the total number of cubes), the faster the solver will run as fewer possibilities are left to test. requires you to specify exactly which cubes in the result shape must be filled and which ones may be empty. The solver doesn't automatically detect multiple identical pieces. You need to specify if a piece is used more than once. If you just copy them the way you do in the program will find way too many solutions. For example, with Bruce Love's Piece Burr> it will find nearly 40,000,000 times as many solutions as there realy are. So be careful. allows you to define multiple problems in a single session. So you can, for example, save all the (Piet Hein) problems within one single file. has no limits to the number and size of pieces. You can have as many pieces as you want and they are not confined to a grid of 24>24>24. There is no limit to the number of possible positions for the pieces. So it won't happen that complains about too many placements. As long as your computer has sufficient memory the program will merrily continue working - even if it would take longer than the universe exists - to complete the search. also has capabilities for files. So there's no need to redo your designs from scratch, although some postediting may be required because of the differences in handling duplicates of pieces and holes in the puzzle. <\with|par-mode|right> When BurrTools is started for the very first time the GUI will look like Figure which shows the main window. Although some small variations may occur depending on your operating system, screen resolution and display preferences settings. The GUI has four major parts. On top there is a that allows handling of files and offers extra functionality as well as some preferences settings for the program. At the bottom there is a traditional presenting relevant information about the task at hand. In between there is a on the left and a D viewport> on the right. |The main window on start-up> Below is a brief overview of the main menu entries with references to the places in the text where a more detailed explanation is provided. <\description-compact> >This menu holds the procedures for handling files within and for exiting the program (>). >Swaps the 2-D and the 3-D grids for the tab (>). >Allows you to export the contents of the 3-D viewer that can be used to create high quality solution sheets (>). >Allows appending textual information to the puzzle file (>). >This menu item provides some preferences settings (>). >Shows a window with some information about the program. The > menu has all the traditional entries for handling files. Many of these are well known from other software and need not much explanation. Some of the items also have keyboard shortcuts as indicated in the menus. Prior to executing most of these commands a warning (and option to cancel) is given whenever changes to the current design haven't been saved yet. \; <\description-compact> >Starts a new design after removing all the information of the current one. >Opens a file. A notification will pop up when a solved design is loaded. Shortcut: . >This entry opens a traditional file dialog that allows importing files () into Although these imported designs often can be subjected to the solver right away, some postediting may be required because of the differences in the way handles holes in the result and uses duplicates of pieces. BurrTools will import the pieces from the file and assign them to the shapes S1 to S-1. Accordingly, the from the file will be assigned to the last shape (S). Also a problem definition is automatically created (>Chapter ). Since all imported shapes consist only of fixed voxels, the result shape may need some editing (puzzles that have internal holes or pieces not filling the outskirts of the result shape) to make the solver run. Also duplicated pieces are preferably deleted from the list (>) but certainly from the list (>), otherwise will find way too many solutions as it will differentiate between all the possible permutations of these identical pieces. >Saves your work into a file. If the design had not been saved before (indicated with '' in the BurrTools windows title bar) the command will be activated. Shortcut: . >Allows you to save any changes to a new file and thus keeping the original design the way it was. >Shuts down Except when the solver is actually , saving your work is always possible. This means that after stopping (pausing) the solver it is possible to save the results found thus far. Later on these partially solved puzzles can be loaded again and the solving process may be resumed. This allows you to subject 'huge' problems (e.g. 25 Y-pentominoes in a 5>5>5 cube assembly) to and have them solved in several sessions overnight or whenever you don't need your computer for other tasks. The > item on the menu bar opens a new window (Figure ) to set some options for the GUI. These settings will be stored in a file that is either in your home directory () or in your profile (). The program will use these settings each time it is started. |The configuration window> \; <\description-compact> >This option affects the way pieces that from the rest are depicted. Hence, the effects are only visible after running the solver (>). >This option toggles the use of a spotlight in the 3-D viewer. When disabled the items in the 3-D viewport get a uniform (high) illumination, wheras enabling this option provides a more rendered appearance of the objects by adding a spotlight in the upper right corner of the 3-D viewport and shading the faces of the objects. However, on some systems this may result in a relatively dark left bottom corner that can hamper a clear view on the objects. >By default shows tooltips for most of its controls, but to the more experienced user these become soon very annoying. This option allows you to switch these tooltips off. The status line has two parts. On the left information about the task at hand is given and on the right are some tools to alter the 3-D view. Currently only the option > is available. When checked all custom colours (>) will be shown in the 3-D viewer, whereas the shapes will be represented with their neutral colour if this option is left unchecked. In between the menu bar and the status line is the most important part of The section that allows you to submit existing puzzles to the solver, but more even important lets you create and test your own designs. The tools section has three major tabs that somewhat can be compared with real people in the world of mechanical puzzles. First there is the tab, which can be seen as the craftsman who different but hasn't to bother about the purpose of these (>Chapter ). As long as his saw blade is sharp he's the happiest man in the whole wide world. Next, we have the tab. This is the weirdo who thinks it's fun to come up with completely insane to be solved with the otherwise very innocent objects of our craftsman (>Chapter ). However, his contribution to the preservation of our planet is considerable... by saving a lot of wood scraps from the incinerator. And last we have the , the poor guy who spends not only a great deal of his money on these finely crafted puzzles but almost all of his leisure time on them (>Chapter ), only to feel very euphoric when he finally succeeds. But scientists are still breaking their heads over the question wheter this is caused by the sweet smell of succes, or is merely due to severe sleep deprivation. Although the layout of the GUI is designed to suit the needs of most users, it sometimes may be useful to resize some elements to enhance the comfort in using Besides the traditional resizing of the main window, has a couple of features to alter the relative importance of its controls. First, the tools tabs can be made wider or narrower (thus making the 3-D viewport more or less important) by dragging the right edge of the tools section. Hovering your mousepointer over that edge will make it change into a left-right arrow, indicating that you can start dragging it. Second, within each of the three main tabs some sections (panels) can be resized as well. For example, if you have a design with many different shapes but no colour constraints at all, reducing the size of all colour related controls and maximising those concerning shapes could be very advantageous. The panels on the tool tabs are separated by so called resize handles (Figure ). The separators that allow resizing are easily recognised by a little beveled square on their right end. Hover your mousepointer over the lines until it changes into an up-down arrow, indicating that you can drag the separator up or down to resize the panel.\ \; <\big-figure> Resize handles> Note that it is possible to drag certain panels completely out of view and that it may be nescessary to drag 'the same' separtor up down to make these sections visible again. Normally the biggest part of the GUI is reserved for the 3-D viewport. In fact this 3-D viewer is threefold and has different properties for each of the tabs of the tools section. For the tab the 3-D viewport shows the currently selected shape and reflects all editing operations performed on that shape. Also the x-, y- and z-axes are shown to assist navigating in space. With the tab activated an overview of the current problem is presented: the result shape (double sized) on top and a single instance of each shape used as pieces below it. Finally, for the tab, the 3-D viewer can be used to browse all found assemblies and/or show an animation of the moves involded in the disassembly of the puzzle. Any object in the 3-D view can be by simply dragging it and the scrollbar on the right allows in or out on that object by respectively moving the slider down or up. Note that the zoom settings are independent for each of the three tools tabs. Extra options for the 3-D viewer are available in the menu (>). <\with|par-mode|right> The key concept of is . A shape is simply a definition of an object in 3-D space and consists of a collection of voxels (space units). These voxels in turn may have their own characteristics such as and . Note that this definition also includes shapes made out of voxels that are only attached to each other by a single edge, just a corner or even are completely separated in space. The solver certainly won't bother... but how these shapes could be crafted in the workshop is beyond the scope of the program. |Creating shapes on the Entities tab> All functions and tools for creating and editing shapes - once the grid type is set - are located on the > tab (shapes are the that can make a puzzle when subjected to certain rules) which has - from top to bottom - three main sections (Figure ): panel>This section is mainly a list of the available shapes and has the tools for creating and managing the shapes. Shapes to be edited can be selected in this list (>). panel>This section provides the tools to build or edit the currently selected shape. This panel contains a series of subtabs with several tools for adjusting the >> of the shapes, >> them in 3-D space and some extra editing >>. Below these subtabs there's a toolbar with the devices for actually constructing the shapes in the 2-D grid at the bottom of the panel (>). panel>This panel contains - besides a list of the available colours - the tools to create and edit custom colours which can be assigned to the voxels of the shapes. These colours can be merely ornamental or can have a serious impact on the way the solver will work by imposing restrictions on the possible placements of the pieces (>). > Currently only handles cubic grids. So no further action needs to be undertaken as the program defaults to this grid type. In the future other grid types and transformations of these (skewing and stretching) may be implemented. The very first step is to initialise the shapes that can be used in your puzzle design. All the tools to do so are just below the > caption (Figure ). Clicking the > button starts a completely new one with an empty grid, while > allows you to edit a previously entered shape without destroying the first. Obsolete and redundant shapes can be dicarded with the > button. All shapes are identified with an '>>' prefix. This prefix serves as a unique identifier for the shape throughout the GUI and cannot be removed or altered, but > allows you to add a more meaningful name. Note that on the status line the shapes will only be referred to by their prefixes. By clicking an identifier in the list the shape becomes selected and ready to be edited. Also a short description of that shape appears on the status line. The currently selected shape is indicated with a white border around its identifier in the shapes list. The buttons with the arrows pointing left and right allow you to change the position of the shape in the list. The first one moves the selected shape toward the front of the list, whereas the other button moves the shape toward the end of the list. Note that rearranging shapes will cause to change their prefix but not the additional name. Unlike the pieces in shapes don't need to be part of the puzzle. This means that you can build a file that contains a vast number of shapes, e.g. all 59 notchable six-piece burr pieces, of which you assign only 6 to the pieces of your puzzle design. Since shapes are defined as objects in 3-D space and theoretically 3-D space is unlimited in size, it's convenient somehow to be able to define a more feasable subspace to work with. This, and some more advanced scalings of the shapes, can be accomplished with the functions on the > subtab (Figure ) of the > panel. |Grid and scaling functions> When the very first shape is initialised it has a default grid size of 6>6>6, but all other new shapes will inherit the grid size of the currently selected shape. This feature can be very useful in creating a series of shapes that are restricted with respect to certain dimensions (e.g. all pentacubes that fit in a 3>3>3 grid). Selecting the proper shape before creating a new one often can save a considerable amount of time by avoiding otherwise necessary grid adjustments. Adjusting the grid size to your needs can be done either by entering values in the input boxes next to the axis labels or by dragging the spin wheels. When you enter values the grid will be updated as soon as you select one of the other input boxes (either by a mouse click or by the key) or when you press the key. Note that the grid is also updated by simply clicking in or next to the 2-D grid. To avoid unexpected results it's recommended always to confirm the entered values with the key. Increasing any grid dimension is completely harmless, but decreasing them needs some caution since it can destroy parts of the shape. The checkboxes for - to the right of the spin wheels - allow you to adjust two or all dimensions simultaneously. All linked dimensions will > or decrease by the same amount. However, none of the dimensions can be made smaller than 1 unit. Linked dimensioning is very useful in creating bigger and complex shapes such as the result shape of (Ronald Kint-Bruynseels), which is easily done by first creating the central burr in a 6>6>6 grid and adding the extensions after resizing the grid to 14>14>14 and centering the 'core' in that enlarged grid. has some powerful time saving functions to manipulate the position of the shape in its grid or to rescale a shape together with the grid. These features are grouped below the captions > and > on right side of the subtab. The first set of three will only affect the grid and/or the position of the shape in the grid, the other procedures however will have an impact on the shape as such by scaling it up or down. Below is an overview of these functions, explaning what they precisely do and with an indication of the purpose they were introduced in . No doubt you'll soon find other situations in which these tools can prove to be valuable. \; Grid> tools.> Most of these tools are somewhat extended versions of the more general transformation tools (>) and have the advantage that they can act on all shapes at once (>). \; |||||||>| This function will minimise the grid to fit the dimensions of the shape it contains. Use it to reduce the disk space occupied by your puzzle files. Note that the result of this function is strictly based on the contents of the grid and will have no effect whatsoever on empty grids.>>|>| This function centers the shape in the surrounding grid thus allowing you to edit all sides of the shape. In some cases this will also one or more dimensions of the grid by a single unit to provide truly centering. The function is most useful in editing symmetrical shapes in combination with the compound drawing methods (>). >>|>| This function brings the shape as close as possible to the origin of the grid. It can very useful if you want to make a descending series of rectangular blocks by copying the shape and manually adjusting the grid dimensions.>>>>> tools.> Use the following functions wisely because unnecessary and extreme scaling up of the shapes will bear a heavy load on your system resources and can increase solving time dramatically. Also, trying to undo such 'ridiculous' upscalings with the 1:1 tool can take a considerably long time. So, \; |||||||>|> -> This function tries to make the shape as small as possible without any loss of information and at the same time scales down the grid by the same factor. Use this function to check the design for oversized shapes which would slow down the solver. Note that although this function can undo the effects of both the next scaling functions, the result cannot be guaranteed since the algorithm may scale down beyond the initial size.>>|>| This function will double the scale of the shape (and its grid). In other words, it will replace every voxel in the shape with 8 voxels that all have the same characteristics (state and colour) as the original voxel. This can be very useful to introduce half-unit notches or colouring into the design without having to redraw the shape(s).>>|>| This function is similar to doubling the scale. Only now a scaling factor of 3 is used and hence every voxel in the shape will be replaced by 27 identical voxels. This can be very useful if you want to introduce > into your design.>>>>> A last, but certainly not least, item to mention is the > checkbox. When checked shapes, whether they are selected or not, will be affected by the settings and procedures on the >> subtab. This is very useful and time saving when a certain adaptation needs to be done to all the shapes, e.g. transforming a six-piece burr with length 6 into one with length 8. However, some precautions are build in to prevent unnoticed destroying of shapes. Manually reducing any grid dimension will still only be performed on the currently selected shape, whereas increasing (which is completely harmless to the shapes) will affect all grids. On the other hand, minimising the grids will be applied to all shapes since it is content related. The 1:1 tool won't affect any shape unless shapes can be scaled down > factor>. This to prevent ending up with an unintended mixture of differently scaled shapes. <\with|par-par-sep|0> Once a shape has been initialised the 2-D grid wherein it can be build becomes accessible on the > panel. Basically one needs only three tools to create any shape, but some more features are added to make life easy. All these are on the toolbar right above the 2-D grid (Figure ). The first four buttons are the and . These are all toggle buttons, meaning that enabling one will disable the others. They affect the presence and/or the state and colour of the voxels by clicking in, or dragging over the cells in the 2-D grid. |Toolbar and 2-D grid> Next come two toggle buttons that allow you to select the . This is the way the basic drawing tools will respond to dragging the mouse over the grid cells. Finally, a series of follows. These extend the range of the basic drawing tools and can all be cumulatively added to them. D and 3-D> Building and editing takes almost exclusively place in the 2-D grid to which the 3-D viewport only acts as a visual aid. Both have their corresponding axes in the same colour: for the x-axis, for the y-axis and for the z-axis. For the 2-D grid, which actually can show only a single layer at a time, the z-axis is represented with a scrollbar (Figure ). By default every new shape starts on the bottom layer and the scrollbar allows you to move up and down through the different layers along the z-axis (the number of z-layers is always indicated with the proper number of thicks along the scrollbar). Another way to navigate these z-layers is by pressing (moves up one layer) or (moves down one layer) on the keyboard. <\with|par-par-sep|0> \ \ \ \ |Selections of grid cells in 2-D an 3-D> Moving the mouse cursor over the 2-D grid gives an indication of the cell(s) - depending on the state of the compound drawing tools - that will be affected by clicking. These indications are also reflected in the 3-D viewer. Furthermore, to facilitate positioning on different layers every non-empty voxel on the 2-D layer just below the current one 'shines through' in a very light shade of the neutral colour associated with that shape (Figure ). This makes building shapes from bottom to top very easy. With larger grid sizes the cells of the 2-D grid can become very small, even when the available area for the grid on the tab is maximised. To overcome this inconvenience the 2-D grid and the 3-D viewport can be exchanged. To do so, click the > item on the menu bar or press . Note that this only affects the position of the 3-D viewport for the tab. The basic drawing tools affect only the presence and/or the state of a particular voxel in the shape. In fact they're - together with the brush tool (>) - all that's needed to create any shape in . The following is a description of these tools. Note that each is also accessible through a keyboard shortcut. \; ||||||||||||>| Use this tool to draw or voxels. Fixed voxels are represented by completely filled cells in both the 2-D and the 3-D grid (>). Remember that these fixed voxels in the final result. Keyboard shortcut: .>>|>| This tool allows you to draw voxels. In the 2-D grid these variable voxels do not completely fill the cells, but have a narrow border showing the background of the grid. In the 3-D viewport the variable voxels have a black inset (>). Variable voxels instruct the solver that these particular places may be in the final result. So variable voxels are only allowed in result shapes and the solver will give a warning whenever it encounters any variable voxels in a shape used as a piece. Shortcut: .>>|>| The eraser will remove voxels from the shape. Note that clicking or dragging with the right mouse button has the same effect of erasing voxels. The eraser tool however proves its use in minute adaptations of shapes. Shortcut: .>>>>> has two different drawing styles. These styles affect the way voxels are drawn/erased or colours are added by with the mouse. In drawing shapes by simply clicking 'cell-by-cell' both are equivalent.\ \; |||||||>| On dragging over the 2-D grid with the mouse just a of cells will be made. This is shown with a heavy border around the selected cells and the voxels will only be altered on releasing the mouse button. Releasing the mouse button outside the actual grid however will make the whole operation void and can serve as some kind of 'undo'. This style not only proves its use in drawing rectangular shapes or parts, but is extremely useful for adding colour to (large areas of) the shape.>>|>| All drawing and colouring operations will be performed on a single cell basis and the mouse cursor is dragged over that particular cell. This drawing style is very useful for creating complex and irregular shapes and colour patterns.>>>>> The status of these drawing styles is remembered by so that it always defaults to the drawing style that was active on the last shutdown of the program. Although the basic drawing tools are all that is needed for creating shapes, some compound drawing tools are added to speed up the process. The compound drawing tools can be added to the basic drawing tools and only extend the range of action for the latter ones. \; ||||||||>| For every voxel drawn, erased or coloured its symmetrically placed counterpart (with respect to the center of the grid and along one of the space axes) will be affected as well. Activating only one of these options will double the number of edited cells, whereas activating two or all three will affect respectively four times and eight times as many cells simultaneously. These options are not only useful for drawing symmetrical shapes, but they are also very well suited for finding the center of the grid and (temporarely) setting the extends of a shape. >>|>| These options - possibly combined with the symmetrical drawing tools - can really speed up drawing shapes as they will affect voxels that are in the same row or column along one of the space axes. The number of voxels that will be affected depends on the size settings of the grid. Hence, to take fully advantage of these functions the grid should be first adjusted to the proper dimensions.>>>>> There are basically two reasons for using colours in your puzzle designs. The first is merely and colours are only used to explore the looks of the puzzle. This can help you selecting the proper species of woods or stains before taking your design to the workshop. The second however is far more important as it uses colours to force c.q. prevent certain possitions of particular pieces in the assembly. These techniques can be very useful to pursue a unique solution for a puzzle design. Of course one can try to achieve both the aesthetical and constraining goals at the same time. Figure shows an example of (Ronald Kint-Bruynseels) in which colours serve both. The red and black voxels are meant to impose constraints on the placements of the pieces, whereas the white colour of the parts on the inside of the pieces is only used to make them look nice. |A shape with custom colours> Even when no 'special' colours at all are used, all created shapes do look different with respect to their 'colour'. This is the so called and is only there to the shapes from one another. These neutral colours are standard for each newly created shape (the first one in the shapes list is always blue, the second one green, the third one red, etc...) and cannot be altered. As far as the solver is concerned, the neutral colour doesn't even exist as all appearances of it are fully interchangeable. So any voxel in the pieces that has only the neutral colour can go into any voxel of the result shape and every voxel in the result that has no other colour than the neutral can accommodate for any voxel of the pieces, independent of its colour. Independent from their neutral colour, voxels can have customised colours as extra attributes. To avoid confusion, it's recommended to have these colours well distinguishable from the neutral colours in use, since a custom colour that is identical to one of the neutral colours will have a completely different effect on the way the solver behaves. Almost without exceptions custom colours need some constraint settings (>) to make the solver run. The tools for creating and editing colours are located on the >>> panel of the >>>>> tab. This panel also has a list in which the colours can be to be used in the design or to become edited. The >> button allows you to create a custom colour. A dialog will pop up and present you the necessary tools to create the colour you need. Accordingly the > button allows you to transform an already existing colour using a similar dialog. This dialog also shows the currently selected color for comparison (unless the neutral colour is selected, which makes the dialog to show the default medium gray). Note that the neutral colour can be neither removed or changed. It's important to realise that the engine only discriminates custom colours by number as indicated in their prefix '>>' and not by the actual colours themselves. Hence it is possible to create identical colours that nevertheless will be treated as different colours. So, it's strongly advised to introduce only colours for which the difference can easily be discerned. Otherwise, finding out why a puzzle has no solutions can be very hard. The > button will not only discard the colour from the list, but will also remove it from any voxel that has it as an attribute by replacing it with the neutral color. Colours can be applied while drawing the shape. Just select a colour and it will become an extra attribute of the fixed pen or the variable pen. Additional colouring can be done by using the tool. \; ||||||>| tool -> This is a device and merely adds the selected colour to the voxels without altering their state. The brush tool can also be activated by pressing on the keyboard.>>>>> The behaviour of this brush tool is similar to that of the drawing pens. So it obeys the drag styles and can be extended with the compound drawing tools. Note that the right mouse button will still completely erase the voxel. Voxels can either be fixed or variable and each of these can come with or without an additional custom colour. In all of these have their own specific representations in the 2-D grid as well as in the 3-D viewport. Figure shows an overview of these. In this picture the neutral colour is red (= shape S3) and the custom colour is green (RGB = 0.600, 0.753, 0). <\big-figure| \ \ \ \ > Representations in 2-D and 3-D Fixed voxels always fill the cell completely in the 2-D grid as well as in the 3-D grid. In both the pictures of Figure the cubes on the left are fixed voxels. Variable voxels only fill the cell partially in 2-D and have a black inset in 3-D (the cubes on the right in Figure ). Voxels that have a custom colour added (the bottom cubes in Figure ) show this colour as an inset in the 2-D grid, whereas in the 3-D viewer they are completely painted with this colour (provided that the > on the status line is checked, otherwise they will be painted in the neutral colour). Note that in both grids the neutral colours also have a slightly checkered pattern which can assist navigating in space. Editing complex shapes can be very cumbersome and requires often a lot of navigating through the 2-D grid. So, properly positioning and/or orientating the shape in the 2-D grid can save a lot of time. comes with a set of functions that help you adjust the position and orientation of the shapes. These functions are grouped on the > subtab of the > panel (Figure ). |Transformation tools> |||||||>| These 'three' functions are merely and the only difference is the orientation of the mirrored shape they provide. The first will mirror the shape along the x-axis (or in a plane through the centre of the gid and parallel to the YZ-plane). The other do perform the same task, but along the y-axis (XZ-plane) or the z-axis (XY-plane) respectively. Note that each button can either undo its own action as well as the actions of the other buttons since the result of each function can be obtained by simply rotating the outcome of any other. However, there are three buttons to provide some control over the orientation of the mirrored shape in the grid space, which can have a time saving effect if the shape needs further editing.>>|>|These functions provide (along the x-axis, y-axis or z-axis respectively) of the shapes in their surrounding grids. These buttons have two parts, of which the left part will shift the shape towards the origin of the grid and the right part will move it away from the origin. Note that shifting a shape beyond the boundaries of the grid will (partially) destroy it. So these nudging operations can also be used to erase unwanted parts on the outer limits of the shapes.>>|>| These functions allow you to the shapes around an axis parallel to the x-axis, y-asis or the z-axis. Again, these buttons have two parts, of which the left rotates the shape 90 anti-clockwise (viewed towards the origin) and the right button turns the shape 90 clockwise. To avoid destroying shapes by rotating them the grid may become rotated as well.>>>>> The > subtab (Figure ) offers extra editing tools. Currently only some constraint related tools are available. |Extra editing tools> These tools are tools that somehow have an impact on the possible placements of the pieces in the final result. They act either on the inside or the outside of the shape. Voxels that are considered to be on the inside are voxels that have another voxel adjacent to of their faces. Consequently, outside voxels have at least one empty voxel neighbouring. \; ||||||||||||>| These functions allow you to change the state of the voxels that are either on the inside (left button) or on the outside (right button) of the shape into fixed voxels. Although one can think of situations in which these can be useful as such, they are mostly used to undo the effects of the next two functions.>>|>| These functions will respectively make all the voxels on the inside or the outside of the shape variable. Making the inside variable is very useful for puzzles with internal holes in undetermined places. On the other hand making the outside variable can prove its use in a lot of design situations (e.g. adding extensions to the pieces). Clicking both buttons will make the shape completely build out of variable voxels. Use these wisely as the more variable voxels there are, the slower the solver will run.>>|>| These buttons will remove any custom colours from the voxels that are either on the inside or the outside of the shape and replaces them with the neutral colour. Removing the colour from the inside can prevent having to apply complex colouring to the result shape in situations were the colour constraints are only relevant to the overall appearance of the puzzle. >>>>> \; Currently only the shapes can be rearranged with the left and right arrow buttons of the section, but more advanced maninging procedures will be added in the future. \; Below are some tips and tricks that can be useful to simplify your designs, speed up the designing and/or solving process, or can be used as work-arounds for some limitations of We encourage the reader to share his own tips and tricks with us so that we can incorporate them in a futere update of this document. <\description-compact> The more variable voxels (as compared to the total number of voxels) there are in the result shape the slower the solver will run. Also the number of pieces has an impact on the solving time. Hence, replacing varibale voxels with empty spaces for determined holes in the puzzle is to be considered. Also leaving out a piece in complex packing puzzles (and making its position in the result empty) can reduce the solving time considerably. Also the size of the shapes has an effect on the solving speed, since bigger shapes inevitably lead to more possiblities: for a 1>1>1 cube there's only one possible placement in a 2>2>2 grid (excluding symmetries), but for a 2>2>2 cube there are four of them in a 4>4>4 grid. So trying to minimise shapes with the 1:1 tool before taking the puzzle to the solver is highly recommended for complex designs. Often complete sets of pieces (e.g. the hexacubes in ) can be easily made by repeatedly copying the current shape and editing it with the properties of left and right clicking. A detailed treatment of some symmetry issues will be added to the next update of this document. <\description-compact> Colouring shapes as a whole is easily done with the brush tool in combination with the rectangle dragging style and z-columns switched on. When colours are solely used for aesthetical reasons make sure that the shape has only the neutral colour. This will prevent having to set a lot of constraint conditions. Polyominoes can be made one-sided by having them two layers high and adding different constraint colours to both the layers. The constraint settings (>) should simply be a 'one-to-one' relationship. For puzzles in which the goal is to hide a certain piece on the inside of the assembly (e.g. Trevor Wood's ) constraint colours should be used. One for the exterior and one for the voxels on the inside of the result shape. Also colour the piece that must be hidden with this 'inside' colour and apply the 'outside' colour to all other pieces. The constraint settings (>) must then be such that the piece to be hidden is only allowed to go into the 'inside' colour and the other pieces may go into either colour. <\with|par-mode|right> Typically a puzzle problem in consists of a collection of pieces (shapes) and a goal, say another shape that the pieces should form when correctly assembled. This is what we call a . Note that it may well be not that 'simple' to solve it in real life. More elaborated or contain also colour constraints and/or grouped pieces. As stated before, a puzzle can be a collection of problems, either simple, complex or a mixture of both. The > tab (Figure ) provides all the tools needed to build a variety of puzzle problems that are suited for the . |Defining problems on the Puzzle tab> As defined above, a simple puzzle problem consists only of a collection of pieces and a result shape that can be assembled (and preferably also be disassembled) with these pieces (Figure ). Bear in mind that a simple problem also implicates that the pieces can be separated from one another. It takes only two steps (which are also required for complex problems) to create such a problem: the problem and shapes to the pieces and the result. The first step is to the problem(s). All the tools to do so are just below the > caption. Just like with shapes this can be done by clicking the > button to start a completely new one, or by using > to edit a previously created problem definition without destroying the first. Accordingly, problems can be removed with the > button. All problems find their place in the problems list below these buttons and are identified with a '>>' prefix to which a more meaningful description can be added by clicking the > button. Also the methods for selecting and rearranging problems are similar to their counterparts on the tab and need no further explanation here. |A simple puzzle problem with multipieces> Until now we dealt with shapes as rather abstract concepts. Only by >> these shapes to the pieces or the goal of a puzzle they become meaningful. All available shapes are presented in the top list of the > panel in which they can be selected and be given their purpose in the puzzle. Since a strict distinction is made between shapes and pieces, it's not nescessary that all shapes are used in a single problem or in any problem at all. Although not mandatory, it's probably best to assign the result shape first: select the appropriate shape and click >. The result shape is then depicted in the top left part of the 3-D viewport (which also shows a smaller example of the currently selected shape) and the status line shows some information about the problem at hand. Next, any other shape can be assigned to the pieces of the puzzle by selecting it and clicking >>. This adds a single copy of the shape to the second list which holds all the shapes used as pieces. If multipieces are involved, just add as many instances of the shape as required by the same means. In the list of pieces any multipiece has an instance counter added - between brackets - to its identifier. A single instance of every shape used in the puzzle is shown in the lower part of the 3-D viewer. To make corrections, pieces can be removed from the puzzle by selecting them (they also can be selected by clicking them in the pieces list) and clicking 1>>. Again, this only removes a single instance and needs to be repeated for removing multipieces. Since it doesn't make sense to have a certain shape to be result and piece at the same time, the shape set as result cannot be added to the list of pieces. Consequently, assigning a shape that's already in the list of pieces to the result will remove it from the list. Whenever the total number of cubes in the pieces is within the boundaries set by the result shape (which can be inspected on the status line) this kind of simple puzzle problems can be taken to the solver. Note that the solver won't run when one or more pieces contain any variable voxels.\ Something we deliberately haven't mentioned in the description above is the fact that the solver will halt whenever it is unable to separate some pieces from each other. In other words, the solver will attempt to separate the pieces from each other and reports that no solution exists when it fails to do so. This is just what is required for most puzzles as you need to have single pieces as a starting point. But there are a few puzzles for which you have groups of pieces that are but . Here the piece groups come in handy. Probably everyone familiar with ever experienced the futile attemps of that program trying to solve such designs by nearly endlessly shifting the entangled pieces back and forth. Not so with as piece groups allow you to tell the disassembler that it is OK when it cannot separate a few pieces from one another. When the disassembler finds two or more pieces that cannot be taken apart it checks whether all of the involved pieces are in the same group. If that's the case it rests assured and continues. If the pieces are in the same group the disassembler aborts its work and reports that the assembly can not be disassembled. This is the basic idea, but there is a bit more to it. A special case is 0'>. All pieces in this group from each other. This group is included so that it is not required to place all the pieces into their own group, when you want to completely disassemble the puzzle. Pieces automatically go into Group-0, so you don't need to take care of that. As a matter of fact you won't even find any reference to that Group-0 in the GUI. On the other hand, when dealing with puzzles of which is known that certain pieces (say S and S) can't be separated from each other, grouping these pieces will cause the solver to report a valid disassembly for which the grouped pieces are treated as a single piece. Be it not a rigid piece since the parts can freely (within certain boundaries) move with respect to each other. <\with|par-mode|center> {S, S} Group-1 > S+S Of course this technique can also be used (in a truly designing situation) for pieces that be entangled. If these pieces are indeed unseparable the solver will report so, but if they can be separated the solver may report the complete disassembly as well:\ <\with|par-mode|center> {S, S} ? Group-1 > S+S Result: {S, S} and/or S, S Now for the hard part: . If you have e.g. a puzzle for which you know that piece S either interlocks with piece S or piece S and cannot be separated from it, but you don't know which of those (S or S) piece S is attached to, you can assign Group-1 to S+S and Group-2 to S+S: <\with|par-mode|center> {S, S} or {S, S} Group-1 > S+S Group-2 > S+S This way the disassembler detects that both pieces are in Group-1 when S and S are inseparable and it finds that both pieces are in Group-2 when S and S cannot let go from each other. In both cases the solver will report a valid disassembly. However, if S and S are entangled the solver is not able to find a valid disassembly All instances of a multipiece need to have the same group assignment, but you can instruct how many of these may be in a group . That means you can make statements like 'not more than 3 pieces of S be in Group-1': <\with|par-mode|center> S>>, S>, ... S> Group-1 > S>>+S>+S> Now how does it all come together? The disassembler starts to do its work. For each subproblem (a subproblem is a few pieces that it somehow has to get apart) it first checks if there is a unique group assignment for all involved pieces - i.e. all pieces have exactly one group assigned and that group is the same for all of them - it doesn't even attempt to disassemble that subproblem. \ If this is not the case it tries to disassemble. In case of a failure it adds the pieces that are in this subproblem to a table of lists of pieces. This is an array and each entry contains a list of pieces. Once done with the disassembler the program comes back to this table and tries to assign a group to each of the lists of pieces in the array. It just checks all possibilities by comparing the entries of the table with the group assignments made by the user. Whenever the sum of pieces (of a certain shape S) in such a 'problematic' table entry is bigger than the value the user designated to that particular piece, no valid group assignment can be made. If the program can find a valid assignment the puzzle is disassembled, if it can not the puzzle is assumed to be not disassemblable. Assume we have a puzzle that contains (among others) 5 pieces of shape S. Three of them might go into Group-1 and another 2 into Group-2. There is also a piece S that might go into Group-1: <\with|par-mode|center> Group-1 > S>>+S>+S>+S Group-2 > S>+S> After the disassembler ran we have the following lists of pieces in the table:\ <\enumerate-numeric> S, S S, S, S Now the program has to assign Group-2 to the first set of pieces and Group-1 to the second set of pieces. Because otherwise piece S would be in the wrong group, it can only be in Group-1. If there would be another piece S in the first set it would not be possible to assign groups because we can only have two pieces S in Group-2. But it would be possible to have another piece S in the second set. We have no idea how useful this might be with puzzles as most of the currently available puzzles require a complete disassembly. But who knows, maybe this feature will help in the design of lots of puzzles new and crazy ideas. Although the above may sound complicated, implementing piece groups is actually very simple. All actions take place in the > (Figure ) which becomes activated by clicking the > button. Initially the shows a tabulated overview of the pieces used in the problem. The first column () lists the pieces by their prefix and name, the second () enumerates the instances of each. Note that it is possible to add or remove instances by changing these -values. |The Group Editor> Creating piece groups is straightforward as the > button simply adds a new group to the problem. Each new group gets its own column (, , etc...) in which one can specify the number of instances of a certain piece that can go in that particular group. Just click on a cell and it will become an input box. Cells that contain a value \ 0 will receive the neutral colour of the correspondig shape, cells with zero are gray and no number is shown. Any group that has no values at all in its column will be deleted on closing the . Hence, deleting all the values of a previously made group will remove the group even if its column stays present in the . The > panel (Figure ) also has two lists. The first one shows all the available custom colours and allows selecting a certain colour for which then some relations can be set. These relations simply indicate which colour(s) in the result can accommodate for which colour(s) in the pieces. By allowing certain combinations (which is in fact prohibiting all other combinations) constraints are imposed on the theoretically possible placements of the pieces. These relationships are shown and constructed in the second list. This list has three columns of which the first shows the 'piece colours', the last shows the 'result colours' and the one in between clearly depicts the relationships by a series of arrows pointing from the piece colours to the result colours. The list is either sorted by the piece colours or by the result colours. The buttons > and > switch between these two views. \ \ \ \ |Colour assignment> When (the left part of Figure ), the bottom list is showing you that every voxel of the pieces with colour C can go into every voxel of the result that has one of the colours on the end points of the arrows starting from Cx. When (on the right in Figure ), the list shows which piece colours will be allowed to go in a particular colour of the result. To set these relationsships, first click the piece colour (or result colour, depending on the sorting method) for which you want to set the constraints. This will activate the 'relations line' for that particular colour which is indicated with a dark surrounding box (note that clicking anywhere on this relations line has the same effect). Next, the down and up pointing arrows will respectively add or remove the colour selected in the top list to or from the constraint settings. Currently puzzle problems can only be rearranged with the left and right arrow buttons of the section, but more advanced maninging procedures may be added in the future. Some tricks and tips will be added to the next update of the user guide. <\with|par-mode|right> Solving puzzles is what is really about. Without its solving engine the program would be nothing more than a simple tool for drawing a very specific kind of 3-D objects... a task a lot of other software is no doubt even better suited for. Solving puzzles is very straightforward with BurrTools as the > tab (Figure ) only has a few controls. On top there is the panel, that contains a list allowing you to select a specific problem to be solved, provides option settings for the solver and has a series of buttons to direct the solving process. Finally, some information of the ongoing solving process is presented. A second panel () has the tools to browse the different solutions found, animate the moves to disassemble the puzzle and to the solutions in detail. |Solving puzzles> In order to make the solver run a problem must be selected first. A list of all previously defined problems is available right below the > caption. Selecting problems to be solved is completely similar to selecting shapes, colours or problems on the other tabs. Note that only the selected problem will be solved and that solving one problem will preserve the results of any already solved or partially solved problem. Currently there are only two options for the solver. Both deal with the kind of information the solver will report. <\description-compact> >When checked the solver will also try to disassemble the assemblies found and only those that indeed can be disassembled will be added to the list of solutions. If this option is left unchecked, the solver will merely search for all possible assemblies, i.e. assemblies for which the pieces do not overlap. Since solving disassemblies takes time (and often far more than assembling), it's recommended to leave this option unchecked for puzzles that always can be disassembled (e.g. problems and other packing problems). For that kind of puzzles running the disassembler would only slow down the process without any gain in information. Also saving and loading the disassembly instructions takes a lot of time and memory, so if they are not really needed they are just a waste of time. >When checked the solver will only count the number of solutions. Check this option if you're only interested in the number of solutions and not in the solutions themselves.\ Next to the solver options are some buttons to direct the solving process. Problems can be solved either in an automatic way or in a (manually) step-by-step manner. An automatic search will proceed untill all solutions, i.e. assemblies and disassemblies (when requested) are found. To begin an automated search click the > button. Typically the solving process consists of a preparation phase followed by several cycles of assembling and disassembling. The latter one is of course omitted when the option is left unchecked. The automatic solving process can also be interrupted by clicking >, but often the solver needs to finish some tasks first before it can actually halt (>). Any interrupted solving process can be saved to the puzzle file and be resumed in another session with . In fact, on loading such a partially solved puzzle will inform you about the possibility to continue with the search for solutions. When the solver is interrupted the shapes (>Chapter ) and/or the problems (>Chapter ) can be edited. If no editing whatsoever of these has been done the solving process can be simply resumed (>), otherwise you need to start all over again. But keep in mind the this savingof the internal state of the solver is very version depentent. So it is likely that a new version of can not resume solving a puzzle saved with an older version. So it is good practive to finishe solving jobs with one version of before updating to the next. When the solver is running it provides a lot of information about its current state (what it is doing) and an estimate of the time it will need to finish the search. All this information is presented on six lines immediately below the solver control buttons (Figure ). The first line of the solver information is a progress bar indicating the percentage of work it has done. The fifth (>) and the sixth (>) line respectively show the time already spend on the search and an estimate of the time still needed to finish the solving process. Note that the latter one and also the information about the percentage done are since these are based on the possible placements of the pieces already tested and still to test. However, the possible placements to be tested are constantly fluctuating as they are determined by the positions of previously placed pieces (>). |The solver information> Probably more important is the > and result information provided by the solver. The line not only tells you what the solver is currently doing, but it also whether the solver can be interrupted or not. The following is an overview of the activities of the solver: \ <\description-compact> This indicates that the solver is ready to be started (provided a valid problem is selected) and that no information is available about earlier attemps to solve the selected problem. The solver is creating the internal data structure for the assembler. This structure is more or less a listing of all the possible places that all the pieces can go to. >In this second stage of the preparation the placements for each piece are tested for plausibility. Some placements are just nonsense in a way that they result in unfillable holes or prevent the placement of other pieces. These placements are removed from the data structure (>). The program is currently searching for assemblies. An assembly was found and is now tested for disasembability. A search was started and interruped. The search was completed, all found solutions become ordered by the total number of moves an can sequentially be inspected (>). The user wanted to stop the search, but the program still has to finish what it is doing right now. Only the assembler is interruptible. The preparation and optimisation stages need to be finished. The disassembly search also has to be finish first. Something is wrong with the puzzle and an error message, providing more specific information on the error, is usualy displayed. Finally the solver gives information about the thus far found > (i.e. assemblies for which the pieces do not overlap in 3-D space) and > or disassemblies (i.e. assemblies that also can be constructed in real life using the particular pieces of the puzzle). Note that the are only reported (and in fact tested) when the option is enabled. Besides the automated search allows you to run the solver step-by-step. Note that this feature is still under construction and that it has a lot of shortcomings. For instance, it won't add the found solutions to the list or update the solver information. So it certainly needs a lot of improvements in a future release of the program. For the time being it is only useful to check the assembly process when something went wrong with the automated search. A manual search needs the initial preparation phase as well as an automatic search. This can be accomplished by clicking >. The solver will halt after this initial phase and the subsequent steps of the assembler can be seen in the 3-D viewer by clicking the > button. The > button opens a window (Figure ) that lets you examine the positions for each piece that will by tried by the assembler. The placements displayed in this window are the possible positions left in the current state of the assembler. So if the assembler has placed a piece S and this prevents placing another piece S at some positions, these positions of piece S will be visible in the list. If you want to see every placement tried you either have to initialise a manual search (click the button), stop the assembler before is starts to do anything (click while in preparation or optimisation stage) or you have to wait until the assembler has finished its work.\ |Pacement browser> The > window (Figure ) has a very simple layout and consist mainly of a 3-D viewer and some additional scrollbars. This 3-D viewport, that shows the outline of the result shape and therein the shape for which the possible positions are to be analysed, behaves similar to the one of the main window. Drag the piece to rotate it in space and use the scrollbar on the right to zoom in or out. Each piece in the problem (note that each instance of a multipiece is available) can be selected with the scollbar on top of the window. The left scrollbar allows browsing all the different placements for the selected piece. Both these scrollbars can also be controlled with the cursor keys on the keyboard: and [ for the left scrollbar and and to select the piece. Be careful though, the first stroke on the keyboard that doesn't fit the current scrollbar will just select the other one and the following keystroke will start to move the slider. As soon as any result is found the solutions list becomes available on the > panel and the 3-D viewer shows the first solution in the list. Note that subsequent solutions are simply added to that list and that they only can get sorted by the total number of moves (in case disassembly was requested) after the search is completed. Already found solutions can at any time be inspected and this does not interfere with the ongoing solving process, but bear in mind that on completing the search resetting the scrollbar for browsing the solutions may be needed to show the solutions properly ordered. This panel has three components: a scrollbar (>) to browse the different solutions, a second scrollbar (>) to view the moves involved in the disassemby and a list of all instances of the pieces in the puzzle problem, which allows you to alter the visibility of particular pieces in the solution(s). By moving the slider of the top scrollbar (>) any solution from the list can be selected as is indicated by its number in the textbox left of the it. Above the scrollbar there is an indication of the total number of solutions already found. When the scrollbar is active it can also be controlled by the and cursor keys. The second scrollbar (>) also has a textbox on the left, this time reflecting the stage of disassembly (i.e. the number of moves executed in the disassembling process) of the currently selected solution. Moving the slider to the right will animate the dissasembly, moving it to the left will reassemble the pieces in the 3-D viewer. Again, when activated the scrollbar can be controlled by the and cursor keys. Above this scrollbar the number of moves required for the dissambly is shown followed by the level(s) of the selected solution. Note that this scrollbar is only visible for searches which have the option checked. The position of the scrollbar isn't affected by selecting any other solution and thus allows easily comparing the different solutions at a particular stage in the disassembly process. In the list at the bottom of the panel all pieces used in the problem are represented by their identifier. Instances of multipieces have a counter added to their prefix which now takes the form '>' and their neutral colour may be slightly modified to tell them apart. By clicking an identifier the visibility state of that particular piece is altered in the 3-D viewer. Each piece can have three states: or Clicking an identifier repeatedly just cycles through these states and also alters the way the identifiers are depicted in the list. These features are very useful in designs for which the pieces are packed in a box, since the box would hide most of the action that is going on inside (e.g. , >Appendix ). Also they are very useful for inspecting the interaction of a few pieces and allow comparison between different solutions as the visibilty states remain invariant in selecting solutions. By default the pieces that become separated from the rest gradually fade out during the final move. Sometimes this is unwanted as it may hinder a clear view on what's going on. This can be avoided by unchecking > on the options window (activated through > on the menu bar). <\with|par-mode|right> comes with some extra features to assist you in making puzzle solution sheets, either for your personal archives or to be issued with your exchange puzzles and commercially produced puzzles. Currently, these capabilities are very basic and need to be improved in a future update of the program. So, don't expect too much from them right now, but rather consider them to be merely a preview or a teaser to stick to . The > entry on the menu bar opens a new window that allows you to add textual information to the puzzle file. It can be used to append extra information to the puzzle such as the name of the designer, or a 'to do' list for your own designs. <\float|float|tbh> |The image export window> The > entry on the menu opens a window that allows you to export a portion of the current puzzle in to (a list of) images (see Figure ). The window has a 3D view on the right and input elements that control what is beeing created on the left. On the very bottom of these controls you can select what you want to create images of. Depending on what is present in the puzzle, the following things can be exported: <\description-compact> An image of a single shape is created. You can select which shape with the shape selector below. An image containing all shapes that are used for a problem is created. Again you will find the problem selector below that is used to select which problem you are going to create images of. An image showing the positions of the pieces in an assembly is created. You can select the problem. Of that problem the first assembly is exported. An image containing all steps necessary to disassemble a problem is created. In this case you also select the problem with the selector below. The images will be created for the last solution of that problem. This is the first thing that you have to select. Naturally only the choices are available to wich the puzzle has data. So if you have not run the solver on the current puzzle it is impossible to export solutons or assemblies. Above these selector you find the file output parameters. First the name and the path to where the images are supposed to be created. If you give no path the images are put into the working directory of teh program. The filename is just a prefix, so if you keep 'test' as filename you get files of the form 'test000.png', 'test001.png', >. Finally you can say how many images you intend to create. will try to do so, but might use less. If you only have one assembly to export, only one page can be created. The entry is ignored by the software for the time beeing, it will be used later on. Above these input elements you find the last section that defines how you want to output, what you output. You can define the quality and some additional parameters that influence how the images look, but not what is to be seen. In the top left corner you find the definition of the background of the image. You can choose between transparent or white. Transparent is useful if you want to have a background with patterns or want to further edit the images. Below you find the settings for the oversampling factor. The higher that is the smoother the images will look, but the more memory and calculation time is required. Below you can select if you want to use the constraint colours for the output or rather the neutral colour of the shapes. The checkbox makes draw pieces that are not involved in the current move in a lighter color, so that the actually moving pieces are easier to spot. This, of course, only works when exporting solutions. Finally there are the parameters for the image size that the program creates. You have 2 possibilities. Either define the pixel size directly, or define the size of the image in millimeters and the DPI printer resolution. If you want to create A4 or letter sized images for printing you can use the predefined sizes. To position the shapes in the output images you can use the 3D view at the right of the export window. All images exported will use the same settings for angle and zoom as in that 3D view. If the shapes reach above or below the 3D view they will be cut. Left and right is different. The width of the images to generate is not fixed. So the program will make them quite a bit wider to accomodate the horizontal spread of the pieces. If you have finished with all settings press >. You will see a flurry of images in the 3D view. The program draws the shapes there and grabs the content from the display. This may take a while. First the size of the images is determined then the images are drawn in the required high resolution for the output. The progress can be seen on the left besides the 2 buttons. You will see how many images are finished and how many there are overall. Hint: If you get unexpected results and broken images try to do nothing while the images are exported. On Linux it is forbidden to change the virtual desktop because then nothing is drawn. The export is far from what we want it to be, many important features are missing, so you can expect some progress in later versions of . <\with|par-mode|right> So, what are our future plans? There are a lot of things still missing (or in need of improvements) from the current program. A list of things that might be interesting to implement are the following: \; <\itemize-dot> Add some special algorithms that are faster for certain kind of puzzles. The current algorithm is quite good for nearly all puzzles, but it's not fastest. Add more colour constraint possibilities, e.g. edge matching, ... Add different space grids, or at least parameters to the cube grid (lengths and angles). Add rotation checks to the disassembler. Add a shape generator: create all piece shapes that fullfill certain rules (shape, colors, union of two shapes, ...) Libraries of shapes to import pieces from. Add tools for puzzle design (see below). Make it possible to divide problems so that they can be solved parallel on several computers and then the solutions are merged back together in one file. Improve multithreading so that multi-core CPUs are better used. Improve assembler to cope with ranges of piece numbers (e.g. 1-5 of piece x) and doesn't need to place all pieces. So that is is possible to solve piece sets and also to create puzzles by defining a set of pieces and let the program find out which of them results in a nice puzzle. Better tool for colorization of a piece. E.g. checkering, but it needs to be more general than just checkering. Make it possible to save only a few solutions. For puzzles that have a lot of solutions this might be useful. Create a debug window to make it possible to find out why there is no assembly or why an assembly can not be taken apart. Speed improvements. We would be very happy to get contributions from other people. After all there are quite a few people out there that have their own puzzle solving programs, maybe they have some nice additions. There is one important thing to keep in mind: the additions have to run on . So you can not use any proprietary library that is not available for . The following paragraphs are written as if the features were already implemented, but this is only done so that the text can be copied into the real book without having to rewrite a lot of it. There are 3 possible design methods implemented in BurrTools <\enumerate-numeric> BurrGrowing after Dic Sonnevelds ideas Constructing, the natural aproach Destructing, the inverse way, take the assembled puzzle and try to assign cubes to one of the pieces The following sections will describe these methods The idea behind Constructing is to create new puzzles out of a set of pieces, try all possibilites and select the best found. To give the designer a great number of possibilities there are loooots of options here beginning with the design of the pieces ending with the method of how to solve the generated puzzle and how to save them. The basis for the Burr Construction is a normal puzzle file containing some shapes. These shapes are then taken by the constructor and made into many puzzles that are solved. So lets start with the piece generation. Each piece for the puzzle that needs to be generated may be assembled out of the following possibilities: a fixed piece, a list of pieces, a merger of 2 or more pieces, a piece containing variable cubes. The whole possibilities can be stacked on one another, so you can specify a list of 2 pieces where is piece is the merger of 3 pieces containing variable cubes... . All this can result in many possibilities, so be careful if you want a full analysis this side of eternity. Because of the complexity the program also might encounter the same puzzle several times. It will also be possible to let the program select puzzles out of the definition space by chance insted of doing a full analysis. So what do the possibilties mean. <\description-compact> a shape containing no variable cubes. This shape is directly used a shape containg n (n\0) variable cubes. All shapes are used that have one of the > possible conditions for the variable cubes are used the pieces in the list are taken one after the other a new piece is constructed containing the union of both pieces, where the union is set, if one of more of the shapes to merge is set and the others are not set and variable is at least one is variable. At the end of the process it is possible to define the type of connection that must exists inside the shapes, shapes that do not fulfill this requirement are dropped All these possibilities may lead to a huge number of shapes, so be careful. Now it is possible to select the way the puzzle is solved. This includes disassembly (if or if not), also reduction and parameters for reduction can be set Finally it is possible to select the way the created puzzles are saved. <\itemize-dot> All / only Solvable / only uniquely keep best with least number of solutions keep best with highest disassembly level keep best with biggest disassembly tree (most branches on the way out) keep best with highest number of not disassembable solutions \ Save puzzles with solution(s) or without to save space The puzzles are all saved into single directory, that must be selected It woult be nice to be able to stop the search process and continue later on, the parameters for the constructor should be saved into the source puzzle file (including the current state) Destruction is in some way the inverse process of construction. Here you start with the finished assembly and you assign the outer voxels to certain pieces. Now the search process starts by assigning the not yet assigned cubes to pieces or to voids. All possibilities are tried and the best are kept. Additionally it is possible to pose certain requirements on the piece shapes. You can say in which way the pieces must be connected (by faces, edges, corners), if the pieces need to be mashine makable. Also it is possible to do the whole process randomly instead of completely This method has been pioneered by Dic Sonneveld. It is suitable to create extremely high level burrs. The algorithm works by adding cubes to pieces to prevent certain moves and hope that the puzzle will still be disassembable in a different way. <\with|par-mode|left> <\with|par-mode|right> This chapter explains some of the internals. It is still quite incomplete, probably out of date and might even be wrong... For those people that want to do things that the GUI is not supporting the exact file format of the files used by the GUI and the library may be of interest. The format is actually a gzip compressed XML-File. The program can read both, compressed and uncompressed files transparently so you don't need to zip them before loading into the program. The GUI always writes compressed files so if you want to change something in them you first need to decompress it. I wont describe all the elements of the XML-File, it's easier if you enter something similar to what you need in the GUI and look in which way the program saves these information. Because this is probably the most complicated part of the format here is a description of how the voxel spaces are saved. The size of the space is saved inside the attributes of the node and the contents of the node is saved in text of the node. The 3 voxel states are saved with 3 characters: <\itemize-dot> '' for empty voxels '' for filled voxels '' for variable voxels. Colours can not be attached to empty voxels but to voxels with the other 2 states. Currently colors are just a number (up to 2 digits) that are simply written as a decimal numer and are appended to the voxel state. If the colour number is 0 (which is the neutral color) nothing is appended. The library is available for all people who want to do an analysis that would be too much work to do by hand with the GUI. A bit of C++ programming experience is necessary to handle the task. There are 4 important classes in the library. The class c> handles a 3 dimensional array. Each position inside the array corresponds with one cube inside the piece. The class is responsible for the whole puzzle containing a set of pieces and a solution. The classes and (where is a number which may be available to select different algorithms that do the same task) are responsible to find assemblies and to disassemble the found assemblies. The important aspects of these classes will be explained in the next sections. This class contains functions to organise, modify, transform 3-dimensional arrays of cubes. Each entry inside the array contains 2 values: <\itemize> The type of voxel (is it empty , filled or a variable cube The colour constraint colour. Here values between 0 and 64 are possible. 0 is the neutral colour. The class provides a set of functions to rotate, translate, mirror, resize and minimise the shape. The function allows to generate all possible rotations also including mirroring, if wished. The function calculates which of these transformations result in the same shape. finds out the all the cubes in the shape are connected in one big piece (neither the assembler nor the disassembler requests that this is the case). If all this is not enough then there are functions that return the value of the different cubes inside the shape and also to set the value of the cubes. These functions exists in different versions. One requires the x, y and z coordinate of the cube requested. The other just takes one number. For this function all the cubes are in one long row. This function is efficient to use if all cubes are traversed and an action is done that is independent of the exact position of this cube inside the shape. Finally there is a set of get functions that also work with coordinates outside the box of the shape. These function always return for cubes outside the bounding box. Then there is a bounding box that encloses all non empty voxels. This box is used by the selfSymmetry function. It only transforms the part inside of the box and then compares. There are 2 comparison functions: one compares the voxel space one by one the other one compares the space inside the bounding box, so the content may be shifted and still they are considered identical. This class contains all the information of the puzzle including the shapes, the result shape and piece shapes and number, the colour constraints, the solutions, the grouping information and some statistics. This class contains all the information that gets saved in hard disc. The class contains a huge amount of functions that allow you to set and get the contained information. As already explained this class tries to find assemblies for a puzzle. It uses the dancing link algorithm explained later. The caller is informed about found solution via a class that the caller has to provide. This class contains a function. This function is called for each found assembly with the found solution as parameter. The caller can then do whatever he pleases. He can just count the number of solutions by increasing a counter. He can save the found solutions. He can analyse, if the found solution is disassembable. If the caller is not interested in the solution he has to delete it. The disassembler tries to find out if an assembly can be taken apart. And if it can be taken apart it will return a shortest disassembly sequence. The class contains some datastructures to make it possible to quickly check multiple assemblies of the problem. So it is possible to chreate one instance of this class and disassemble a whole set of puzzles and then destroy it. This class contains an assembly of a puzzle. The assembly is always connected to a specific problem of a puzzle because it takes reference to the piece numbers defined in the problem and also to the shapes of the pieces defined within the puzzle. The assembly itself contains just a list of positions and transformations. What shape is behind that must be asked from the puzzle class Assemblies can be transformed. This changes to placement and transformation of all the included pieces so that the resulting piece arrangement is rotated. Assemblies can also be compared. This is required for the rotation avoiding technique describes below for the assembler. This class contains all the information to completely (or with piece grouping not completely) disassemble the puzzle. It contains a tree. On each branch of the tree the puzzle separates into 2 parts. If one part can not be further assembled (e.g only one piece is in that part or the grouping makes is not necessary to disassemble that part) the pointer to the subtree is . Each node of the tree contains a list of piecepositions that are the steps to take the problem apart. A very simple example can be found within the source code of the project. Check the burrTxt sources. They just check a few command line options, load the puzzle and then solve it, no fuzz with user interface, multi threaded application, ... There are only two algorithms of interest inside this program. One is the assembly algorithm. This one is based on the ``Dancing Link'' algorithm from D.E.Knuth. I needed to update the algorithm in 2 ways: <\enumerate-numeric> We require cubes that as well as cubes that . The original algorithm only provides the 2nd type of cubes. We need to do something about multiple identical pieces. The original algorithm will find shapes>num(s)!> as many solutions as there really are. The 2nd interesting algorithm is the disassembler. This is mainly a breadth first tree search over all possible placements of the pieces. As already said this algorithm is based on the Dancing link algorithm. This algorithm is mainly a very efficient and elegant backtracking method that stops much more early than many other algorithms. It stops when is finds that a piece can not be placed any more. It stops when it finds that a cube of the solution shape can not be filled any more. These recursion stops don't need to be implemented separately, but they are part of the algorithm. But bevore we go on describing the details, there is one mayor problem that needs to be solved: avoid finding solutions multiple times. Now this is a complicated problem. There is the naďve approach which would be to save all found assemblies and check new found assemblies against this list. This has major problems. You need to save all assemblies and there can be many. You need to check against all those save assemblies and that can get slow. If you want to make a break and later on continue you need to save all those solutions on harddisc and load them again. An of course the worst problem is that you waste a lot of time. If it just would be possible to not find those solutions in the first place. To solve this problem let us first analyze what kind of double solutions exist <\description-compact> These are solutions that do look completely identical (they are not even rotated). There are 2 possible reasons for this to happen: <\enumerate-numeric> Two or more identical pieces that are exchanged One piece has symmetries and the (invisible) difference between the 2 found solutions is that this piece is rotated A bug in the code that makes the program find identical assemblies. Lets assume that this is a rare event. These are solutions that are identical but need to be rotated first to find that out. The first kind of assemblies can be avoided relatively easily by removing rotations from pieces that result in the same piece. And by being careful with identical pieces and avoid finding the permutations of these pieces. With these precausions it can be assured that identical looking assemblies are found. The second kind is very hard. The recursive part of the program will find them. It is possible to avoid finding a few of the rotations and in some puzzles is even possible to avoid finding any of them but there are puzzles where the program find some or even all possible rotation, so a solution needs to be found that can detect rotations when they are found. But first let's see how we can avoid as many of the possible rotations as possible. This is done by selecting one piece and dropping a few of the rotations that are possible with this piece. As this piece can not only be inside the solution in certain positions all solutions that would require that piece to be rotated will not be found. If we can be sure that all solutions that are dropped also exist as a rotation inside the solutions that we find we are lucky. But which piece to select? And what rotations to drop? To find out which piece it helps to think of the perfect piece. Lets assume our target is a cube and it has only one solution. A cube has 24 symmetries so we would normally find 24 solutions (maybe even more, due to mirror solutions, but let's forget about this for a while). With each rotation that we drop from our selected piece one of the possible rotations for the solutions wont be found until we have only one possible rotation left for the selected piece and so we find only that solution where this piece is in that left over rotation. All other rotations would require the piece to be in another rotation, which is not in our list to try. But this only works, if the piece really has 24 differen rotations from which we can drop 23. If the piece is symmetric in one way or another it will not have that many different rotations as a few of them will result in the same piece and thus can not be considered. So the best choice is always a piece with no symmetries. What to do if there is none such piece? Select one has has the least overlap with the symmetries of the result shape. Before we make clear what that means we have to see which rotations need to be dropped. We need to drop those rotations that might result in a rotated solution. A rotated solution is one that has the same exterior appearance. So the possible rotations result from the shape of the result. If all these rotations do exist in the selected piece we can supress the rotations from the solutions by dropping them.\ And now back to the clean and general solution. Here Bill Cutler came to my help. He told me what he did and that is something very ingenious. The first thing to do it to be able to compare two assemblies that are the same but one is a rotation of the other and be able to say assembly > is smaller or larger or equal to assembly >. This comparison can be implemented by comparing piece positions and transformations. It can be completely arbitrary. It just must be assured that the rotation suppression with the pivot piece does not remove the one transformation that is the smallest when compared with the comparison. Now the following is done for each assembly found. At first all rotions of this assembly are generated that result in the same shape for the assembled shape. These assemblies are compared with the found one. If there is one that is smaller than the found one drop the found assembly and go on searching. If the found assembly is the smallest one do whatever needs to be done with it. There are 2 left open the question. What to do if the found assembly is the smallest but there is another assembly just as small? And how can be assured that the rotation selected by the comparions function is not removed by the rotation avoiding method. First to the first question. When does this happen? This happens then when solution itself (not only the shape of the result but the also the construction) has some symmetry. That means that there are 2 indetical looking solutions that differ in exchanged pieces ore a rotation of a piece that does result in an identical looking piece. This kind of identical solution has already been successfully avoided, so there is no need to take special precautions, that case is ignored. If the found assembly is one of the smallest it is taken, if there is one ore more smaller assembly, it is dropped. Now on to the 2nd problem. Here we need to make sure that the rotation avoiding method knowns about the comparison function and makes sure that the smallest of the assemblies is kept. Here is one possibility:\ If the comparison function looks like this: <\code> for (p = 0 up to number of pieces the assembly) { \ \ if (rotation of piece p in assembly 1 \ rotation of piece p in assembly 2) \ \ \ \ return assembly 1 is smaller \ \ elseif (rotation of piece p in assembly 1 \ rotation of piece p in assembly 2) \ \ \ \ return assembly 2 is smaller \ \ elseif (pos x of piece p in assembly 1 \ pos x of piece p in assembly2) \ \ \ \ return assembly 1 is smaller \ \ and so on } For this function an assembly with a piece 1 with a smaller rotation number is always smaller that one with a bigger rotation number. So if we chose a rotation avoiding technique that always selects piece one as pivod piece and always removed the bigger rotation number, we should be on the save side. I will describe the only the basics for the original dancing link algorithm. For further information read the document available on Mr. Knuths web page (). The algorithm represents the puzzle as a matrix. In this matrix the first columns represent the pieces and the last columns represent one voxel of the result shape each. Each line of the matrix corresponds to one possible placement of one piece inside the result. The column of the piece and the columns the represent the places inside the solution that the piece occupies with the placement are 1 inside the matrix. All the other cells are 0. The search itself runs on this matrix. It searches for a set so that all the lines in this set taken together contain exactly one 1 in each column. This means that each piece must be used and each cube in the result must be filled. The algorithm does 2 operations on the matrix: <\enumerate-numeric> Cover column n and uncover column n. This means that the column is removed from the matrix and no longer taken into account for the search. When a column is removed all the rows that contain a 1 in this column will also be removed. Cover and uncover row n. This means that we select this row for the set of rows that we search. The row covering also removes and re-includes all the columns that contain a 1 in this row. On these columns operation 1 is performed. The 2nd operation can be interpreted as. Taking one piece and putting it inside the result at one possible place. This results in the fact that a few cubes of the result don't need to be observed any longer and all placements of all other pieces that collide with this placement don't need to be checked further. The cover and uncover operations are the inversion of one another. If we first cover something and then uncover it again the matrix is in exactly the same state. The algorithm is now recursively trying all possibilities. It selects one column and then tries covers all rows that contain a 1 in this columns and then calls itself. It finished when there are either no more columns left. Then we have found a solution or there is one column with no rows. Then we have found a dead end and backtrack. This algorithm is per se not dependent on square cubes it is not dependent on any shape. You only need to transfer your puzzle into the matrix. Even William Waites<\footnote> see puzzles should be possible. But as the square and cubes are most common I have for now only implemented this transformation. Now to the changes that I have done to this basic algorithm. There is first the matter with the 2 types of cubes. This is easily solved by removing the columns of the cubes that from the list of columns that need to be covered. They are still in the matrix, they just don't to be covered to find a solution. The 2nd problem was much harder. How handle multiple identical pieces? The solution that I finally implemented is to enforce an order. All pieces get a number and all the placements get a number. If we now have 2 identical pieces and with b> I force that the placement of , is also smaller than the placement of so p(b)>. This is done by always placing all identical pieces in one go. The moment the algorithm decides to place one of the pieces that occur multiple times it will also place all the others and always check that these have larger placement numbers. The disassembly algorithm is a breadth first tree search. In this tree every node represents one possible relative position of the pieces. To find out what can be moved in this node the algorithm Bill Cutler used for his 6 Piece Burr analysis is used. His algorithm anaylzes for 2 pieces how far the first piece piece can be moved in the positive direction of each of the 3 axis if the other piece is fixed. This results in 3 matrixes each square with as many rows and columns as there are pieces. The values for negative directions can be taken from transposed matrixes. To make these matrixes useful they need to contain not pairwise information but for the whole state. To get this information the following property is used: <\quote-env> If piece A can be moved x units when B is fixed and piece C can be moved y units whan piece C is fixed then piece C can not be moved more than x+y units when B is fixed. With this property the 3 matrixes are treated again and again until all values have reached a stable value. The resulting values tell you exactly how far each piece can be moved when some other pieces are fixed. Now all possible new states are generated with the aid of these calculated values. This worked nice but it has been quite slow. Slower than at least. So I started to optimize. The slowest part has been te pairwise analysis of all piece pairs. Initially I implemented more and more complicated schemes that were supposed to speed up thing. But the code got more and more complicated and due to the usage of preprocessor macors utterly undebuggable. And it was still slower than . Finally I came up with a new scheme that solved the speed issues: a cache. This cache contains the values calculated for the movement possibilities of 2 pieces. Once they are calculated they are put into the cache and used from there later on. The cache contains the 3 calculated values. The key is calculated from the piece numbers, their relative positions and their transformations. The incorporation of the transformations made it possible to used the cache over the whole process of a puzzle analysis and not to restart it for each assembly. This has a mayor impact: the number of cache hits is for some puzzles way over 90%. This cache also has another nice property. It is possible to remove information for a certain piece from it. This comes in handy when burrgrowing is used, as the information for changed pieces can be removed from the cache but the rest is still intact and useful information. There is currently one useful thing besides the normal improvements that might be added to the library: Other puzzle types. The assembly algorithms is so abstract that it can cope with many different types of assembly puzzles, as long as they have some kind of pattern. Currently the assembler only supports puzzles made out of cubes but there is nothing that prevents solving puzzle where the base unit is a hexagon. Of course the disassembler can not do work with this kind of puzzles. To add other geometries the assembler is split into 2 parts. The dancing link algorithm and the algorithm that prepares the matrix for the dancing link algorithm. This preparation part is called the front end. \; <\with|par-mode|right> comes with some examples that illustrate the capabilities and functions of the program. We'd like to thank the designers for allowing us to include their designs in the package. <\description-compact> Ronald Kint-Bruynseels, 2003, Belgium. This puzzle shows how to properly make packing puzzles. You always should include the box as a piece so that the program can also check if the pieces can be moved into or out of the box. You can also see how to handle multipieces. When looking at the solution it is useful to display the box as a wire frame. This can be done by clicking at the blue rectangle at the lower end of the tools. The rectangle with the S1 in it. <\description-compact> Mineyuki Uyematsu, 2002, Japan. This file contains MINE's CUBE in CAGE 333, cube g. This puzzle demonstrates how to use the grouping capabilities. The puzzle contains 3 interlocked pieces that construct a cage. These pieces move but can not be taken apart. It needs to be told to the program that this is intentional. So here you have an example of how to do that. <\description-compact> Ronald Kint-Bruynseels, 2003, Belgium. This puzzle demonstrates the use of colour contraints. Halve of the result must be red and the other halve black. You can see the colours if you enable the checkbox in the status line at the bottom right. <\description-compact> Dic Sonneveld, 2000, The Netherlands. This is a high level burr. It takes 98 moves to get the first piece out of the box. This is just a demonstration of what is possible. <\initial> <\collection>