<\body> |<\doc-author-data|> \; >> <\table-of-contents|toc> <\with|par-mode|right> \ <\with|par-mode|right> \; \; What are ? consists of 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 creating and editing puzzle definitions, solving the puzzle, and the display and animation of the solutions found. This is probably the most interesting part for most people. On the other hand there is also 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 what the graphical interface does (and more). The first part of this document describes the graphical program. It contains descriptions of all concepts and explains how to use them in the GUI program. The second section contains a description of the library and some internals. Also, some of the algorithms used are explained. This section is probably interesting only 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 similar to 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 complex research or design tasks, 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 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 responsible 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 crucial to the further development of the program. All this work has taken many years to reach the current state, I hope it was worth it and that 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. Terms may be briefly repeated at several places in the text. 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 operating 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 download either 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 installer is probably the best option. To use on a platform you have to download the files and compile the program on your system (see installation guidelines below). An OSX package is provided. If you downloaded the , just extract the file into the directory of your choice and the GUI is ready to be used. If 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. 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 libraries 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 uses 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 occurs 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 by 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. The last library, , can be hard to find, so here is 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 are 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 supports cubic voxels, triangular prisms and tightly packed spheres. Each voxel has one of the following three states: , () and (>). Additionally 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. The spacegrid defines the shape and orientation and arrangement of the voxels. Right now there are 3 space grids available in : cubes, prisms with a equilateral triangle as base, and tightly packed spheres. Spacegrids are always fixed and periodic. That means that a voxel in a certain position will always have the same shape and orientation. So a spacegrid defining, for example, all Penrose patterns is not possible because these are neither a fixed nor a periodic patterns. 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. The prefix is already unique. It is a letter followed by a number. The letter is different for all items that required identifiers, e.g. it is S for shapes, P for problems and C for colours. An assembly is a physically possible arrangement of pieces (meaning the pieces do not overlap in space) 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 separate instruction how to assemble the pieces. It suffices to know where the pieces are in the assembly. Other puzzles require detailed instructions how to move the pieces to assemble the final shape. That is why the task of finding the assemblies and creating assembly/disassembly instructions are separated from one another. 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 assemblies 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 variable state in the result shape. Right now the variable state can only be used in result shapes and the solver will pop up an error message whenever it encounters a variable state in a normal piece.Later on variable voxels might be used in piece shapes as well to define voxels in the shape that the program might alter to create interesting puzzles. 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 special: it always makes a color match. Voxels in a piece that are in the default colour fit everywhere and default coloured voxels in the result shape can accommodate any piece voxel, independent of its custom colour. Currently the assigned colour is interpreted as 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, by now has diverged quite a bit from that. We strongly advise you to read this user guide since there are some features in that work somewhat differently to 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. But knowing which cubes be filled speeds 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 it will find nearly 40,000,000 times as many solutions as there really 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 won't stop and complain 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. supports another gridspace besides the cube space supported by . This allows the design and analysis of completely new puzzles knows piece ranges, which enables you to search for puzzles and not just solve them. files> 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. There are 2 possibilities for the holes. Depending on whether the option ``Fill outer Cubes'' is enabled or not when you solve the puzzle with , you must either make the inner cubes of the result shape or the whole shape variable if you want to get the same results with . This can be done with the tools described in section . With these tools you can make a shapes inner or outer cubes variable. The duplicate pieces are handled automatically. adds all shapes to the new puzzle but does not add duplicates to the problem instead the counter for the original is increased. The unused shapes are marked as unused and can be deleted if they are not required. <\with|par-mode|right> When BurrTools is started for the very first time the GUI will look like Figure<\float|float|tb> |The main window on start-up> 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. 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 (>). >Contains a submenu with 2 entries. One allows you to export the contents of the 3-D viewer that can be used to create high quality solution sheets (>). The other allows you to create STL files for 3-D printers (>) >This menu entry will allow you to change parameters for the currently used space grid. These parameters include things like scaling of axes or skew. Not all space grids support parameters. >This opens up a window containing lots of possibly useful information about the shapes of the puzzles (>). >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 don't need 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. The first thing that happens when you start a new puzzle is that you will be asked which spacegrid to use. When is started it defaults to using the cubes spacegrid, so if you want to use another grid you need to use this menu. >Opens a file. A notification will pop up when a solved design is loaded. Short cut: . >This entry opens a traditional file dialogue 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 duplicated 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 should preferably be deleted from the list (>) but certainly from the list (>), otherwise will find way too many solutions (as it will distinguish all 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. Short cut: . >Allows you to save any changes to a new file, 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<\float|float|hftb> |The configuration window> ) 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. <\description-compact> >This option affects the way pieces that from the rest are depicted. Hence, the effects are visible only 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, whereas 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 of the objects. >By default shows tooltips for most of its controls, but to the more experienced user these soon become very annoying. This option allows you to switch these tooltips off. The status bar has two parts. On the left is given information about the task at hand, and on the right are some tools to alter the 3-D view. Currently you can select there the 3-D view shows the shapes. You have the choice between the normal view where each piece is drawn with its default colour, or a view where each piece is drawn with its colour constraint colour (if it has one assigned>). The third option is an anaglyph called mode (see figure<\float|float|tbh> |Disassembler in Anaglyph Mode> ). In this mode the pieces are drawn using the red-cyan method to display real 3-D. You can view these with a red-green, red-blue, or red-cyan glasses. The ed glass must be in front of your ight eye. 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 might can be thought of by analogy with real people in the world of mechanical puzzles. First there is the tab, which can be seen as the craftsman who different but is not concerned with their 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 produced by 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 whether this is caused by the sweet smell of success, 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 for convenience 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 mouse pointer 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<\float|float|tbh> |Resize handles> ). The separators that allow resizing are easily recognised by a little beveled square on their right end. Hover your mouse pointer 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. Note that each section has a minimum size. It is not possible to make it smaller than that minimum size. D Viewer> 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 assemblies found and/or show an animation of the moves involved 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 attached to each other by only 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. All functions and tools for creating and editing shapes - once the grid type is set - are located on the > tab which has - from top to bottom - three main sections (Figure<\float|float|tbh> |Creating shapes on the Entities tab> ): 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 handles cubic grids, grids that use prisms with a base shape that is an equilateral triangle, and tightly packed spheres. The spacegrid is used for all shapes within a puzzle, so you cannot have one shape made out of cubes together with one using another grid. The spacegrid needs to be set you start with the puzzle. It cannot be changed later on. The gridtype is selected when you use the > option. Some gridtypes support setting some parameters of the grid, like scaling or skew. These parameters can be used to suppress certain orientations for shapes but, not to create new puzzle shapes. Same for cubes: there might be a parameter that scales the cubes in y-direction. If that values differs from the x-direction value it will be possible to turn the cubes only by 180 when rotated around the x-axis. The very first step is to draw 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 shape with an empty grid, while > allows you to edit a previously entered shape without destroying the first. Obsolete and redundant shapes can be discarded 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 be referred to only 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 their prefix to change 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. Finally, the shapes have an additional parameter: the weight. This value is used when constructing the disassembly animations. When the disassembler has found 2 groups of pieces that can be moved against each other it needs to decide which group to actually move and which to keep where it is. This decision can be influenced by the weight. The program searches the maximum weight in both groups and the one group that has the bigger maximum weight will be kept in place and the other group will be moved. If both groups have the same maximum weight the group with the smaller number of pieces will be used. 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 feasible subspace to work with. This, and some more advanced scalings of the shapes, can be accomplished with the functions on the > subtab (Figure<\float|float|tbh> |Grid and scaling functions> ) of the > panel. Note that the tab might look slightly different for different gridtypes. For example the sphere grid doesn't have the shape buttons as those are useless with that grid. 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 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 increase 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 centring 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 the right side of the subtab. The first set of three will affect only the grid and/or the position of the shape in the grid, the other procedures however will have an impact on the shape itself by scaling it up or down. Below is an overview of these functions, explaining precisely what they do and with an indication of the reason they were introduced into . 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 centres 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 true centring. 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 put 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 long time. So, These tools make sense only for spacegrids where a group of voxels can be grouped to make an upscaled shape that looks like a voxel of the grid, e.g. a group of 2x2x2 cubes looks like a bigger cube. As this doesn't work with spheres, these tools are not available there. \; |||||||>|> -> 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 of 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 a group of 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 built in to prevent accidental destruction of shapes. Manually reducing any grid dimension will still be performed only 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 . This prevents 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 in which it can be built 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<\float|float|bhft> |Toolbar and 2-D grid> ). 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 drawn by clicking in or dragging over the cells in the 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 place almost exclusively in the 2-D grid, to which the 3-D viewport acts only 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 ticks 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.<\float|float|tbhf> \ \ \ \ |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 default 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 affects only the position of the 3-D viewport for the tab. The basic drawing tools affect the presence and/or the state of a particular voxel in the shape. In fact, together with the brush tool (>) they are 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 short cut. \; ||||||||||||>| 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 short cut: .>>|>| 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 allowed only in result shapes, and the solver will give a warning whenever it encounters any variable voxels in a shape used as a piece. Short cut: .>>|>| 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. Short cut: .>>>>> 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, 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. But releasing the mouse button outside the actual grid will make the whole operation void and can serve as a sort of 'undo'. This style is useful not only for drawing rectangular shapes or parts, but also 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 shut down 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. Note that these tools always function along the 3 orthogonal axes, so they are very useful for cubes but might need a bit of getting used to for the other spaces as they might behave differently along the 3 axes. The triangular prisms for example are stacked along the z-axis, side by side along the x-axis and tip by tip along the y-axis. \; ||||||||>| For every voxel drawn, erased, or coloured its symmetrically placed counterpart (with respect to the centre 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 centre of the grid and (temporarily) setting the extents 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.>>>>> It is also possible to do some editing using the 3- Add a normal voxel by pressing and clicking onto a face. The neighbour is added. Add a variable voxel by pressing and clicking onto a face. Again the neighbour is added. Remove a voxel by pressing and clicking onto a voxel. This removes the voxel. As spheres do not really have touching faces the 3- There are basically two reasons for using colours in your puzzle designs. The first is merely : colours are used only 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 or prevent certain positions 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 aesthetic and constraining goals at the same time. Figure<\float|float|tbf> |A shape with custom colours> 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 used only to make them look nice. Even when no 'special' colours at all are used, the program assigns each shape its own different nominal color. This is the so-called and is there only to the shapes from one another. These default 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 default colour doesn't even exist, as all appearances of it are fully interchangeable. So any voxel in the pieces that has only the default colour can go into any voxel of the result shape, and every voxel in the result that has no other colour than the default can accommodate any voxel of the pieces, independent of its colour. Independent from their default colour, voxels can have customised colours as extra attributes. To avoid confusion, it's recommended to make these colours well distinguishable from the default colours in use, since a custom colour that is identical to one of the default colours will have a completely different effect on the way the solver behaves. Almost without exception 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 be edited. The >> button allows you to create a custom colour. A dialogue 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 dialogue. This dialogue also shows the currently selected colour for comparison (unless the default colour is selected, which makes the dialogue to show the default medium grey). Note that the default colour can be neither removed nor changed. It's important to realise that the engine discriminates custom colours only 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. So, it's strongly advised to introduce only colours whose 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 default colour. When you add a colour, automatically adds a constraint rule that pieces of this colour can be placed into result voxels of this colour. This is done by default because it is the way colours are most often used. If you don't want this constraint you have to explicitly remove the rules (see >). Also, when a new problem is created automatically adds one such rule for each existing colour. 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 be either fixed or variable, and each of these can come with or without an additional custom colour. In all of these cases have their own specific representations in the 2-D grid as well as in the 3-D viewport. Figure<\float|float|tbh> <\big-figure> \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Representations in 2-D and 3-D> shows an overview of these possibilities. In this picture the default colour is red (= shape S3) and the custom colour is green (RGB = 0.600, 0.753, 0). Fixed voxels always fill the cell completely in the 2-D grid as well as in the 3-D grid. In all the pictures of Figure the voxels on the left are fixed voxels. Variable voxels only partially fill the cell in 2-D and have a black inset in 3-D (the voxels on the right in Figure ). Voxels that have a custom colour added (the yellow voxels 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 default colour). Note that in both grids the default colours also have a slightly checkered pattern which can assist navigating in space (except for the spheres, which have no checkering). Editing complex shapes can be very cumbersome and often requires 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<\float|float|tb> <\big-figure> Transformation tools> ). The first thing to see is that the transform tab looks quite different for all 3 available gridtypes. At the top of the figure you see the tab for cubes, below for triangles, and at the bottom for spheres. \; |||||||>| These 'three' functions are merely , 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 grid and parallel to the YZ-plane). The others perform the same task, but along the y-axis (XZ-plane) or the z-axis (XY-plane) respectively. Note that each button can 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 save time if the shape needs further editing.>>|and more>|These functions provide (along the x-axis, y-axis or z-axis for the cubes, or along different axes for other gridtypes) 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-axis 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 be rotated as well.The triangle space has only one rotation button for the x and y-axis because it is possible to rotate only by 180 around these axes.>>>>> The > subtab (Figure<\float|float|tbf> |Extra editing tools> ) offers extra editing tools. Currently only some constraint related tools are available. These tools are tools that 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 be halpful in a lot of design situations (e.g. adding extensions to the pieces). Clicking both buttons will make the shape completely built 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 replace them with the default 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 relevant only to the overall appearance of the puzzle. >>>>> Currently the shapes can only be rearranged with the left and right arrow buttons of the section, but more advanced management procedures will be added in the future. When using the main menu entry > a window (Figure<\float|float|tb> |The Status window> ) like the one above opens and displays all kinds of information about all the shapes available inside the puzzle. The table columns have the following meanings: <\description-compact> Contains the number of voxels inside the shape that have the state fixed. Contains the number of voxel inside the shape that have the state variable. Contains the number of voxels inside the shape that are either fixed or variable. If the shape is identical to another shape with smaller number, the first such number is displayed; so if shape 3, 4, and 5 are identical, shape 4 and 5 will point to shape 3 but shape 3 will show no indication. A previous shape is cited, if the shapes can somehow be transformed into the other including the mirror transformation. A previous shape is cited, if the shapes are identical without mirroring.\ In this case shapes must be completely identical including colours and not only the appearance of the shape. This part of the table shows if the shape is completely connected, i.e. doesn't contain any separate voxels. This part is marked with an X when all parts of the shape are connected via the faces of the voxels. A face is a surface of a voxel. Cubes have 6 such faces, the triangular voxels have 5, and spheres have 12 faces. This part is marked with an X when all parts of the shape are connected via an edge or a face of the voxel. An edge is the connection between 2 corners of a voxel. A cube has 12 edges and the triangular voxel have 9. Spheres have no edges. This part is marked with an X when all parts of the shape are connected via a corner, an edge, or a face. A corner is the end of an edge. Cubes have 8 corners, the triangular voxel have 6 corners, and spheres have none. This part of the table contains information about possible holes inside the shapes. A 2D hole is a hole in a 2-dimensional shape. So the o-octomino has a 2D hole. A 3D hole is a completely surrounded region inside a shape. This is a column that is mainly there for my help. needs to know about all kinds of symmetries a shape can have. If a shape turns up that has a kind of symmetry yet unknown to the program it cannot solve puzzles with this shape. So here is a tool to check beforehand and without the need to create a problem. If you ever see a coloured mark in the last column send me the shapes where it turns up. As long as this last column contains only numbers without a coloured mark everything is fine. Because calculating all this information can take a considerable amount of time, pops up a window when it is working on accumulating this table. The window contains a progress bar to guess how much longer it will take. There is also a > button at the bottom that lets you abort this calculation and view the results already gathered. 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 workarounds 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 future update of this document. <\description-compact> The greater the proportion of variable voxels in the result shape, the slower the solver will run. Also, the number of pieces has an impact on the solving time. Hence, replacing variable voxels with empty spaces for known holes in the puzzle is to be considered. Also, leaving out a piece in complex packing puzzles (and making its position empty in the result) can reduce the solving time considerably. The size of the shapes has an effect on the solving speed, since bigger shapes inevitably lead to more possibilities: 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 used solely for aesthetic reasons, make sure that the shape has only the default colour. This will prevent having to set a lot of constraint conditions. Polyominoes can be made one-sided by having them two layers thick and adding different constraint colours to the two 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 in the result shape: one for the exterior and one for the voxels on the inside and one for those on the outside. Also colour the piece that must be hidden with the '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 allowed to go only into the 'inside' colour, while the other pieces may go into either colour. It is possible to emulate spacegrids different from cubes by just using cubes. This way can solve different kind of puzzles. This section will give hints on how to such things. It will not contain obvious emulation possibilities like hexagons with 6 triangles or x by y rectangles using several squares, but rather some of the more complicated possibilities. The chapter cannot be complete but rather it wants to suggest what can be done and give you some initial ideas. If you come up with a cool idea you are welcome to send it to me and I will include it here. Generally this emulation requires using cubes for one basic unit. This will probably result in a slowdown of the solving process, but the slowdown is not always that grave. knows how to merge voxels that are always occupied by the same piece into one, so if there is for example a puzzle that uses hexagonal pieces made out of the triangular prisms and these hexagons are always aligned on a hexagonal grid, will merge the 6 triangles together and work with the resulting shapes. This takes some time only at the initialisation phase. On the other hand, there might be many placements of pieces that fit the underlying cube to triangle grid that are not proper placements and that need to be sorted out first. This can take a long time. by Kevin Holmes for example has a lot of illegal placements for pieces that need to be sorted out. That takes a very long time, but once that is done the solving is actually very fast. <\float|float|tbhf> |Emulate 2 Sided Piece> If you have pieces that have a top and a bottom, there are several possibilities to model that in . One possibility is to use colours. Make the piece and the result 2 layers thick. The bottom layer of both will get a special colour. Another possibility is to add an additional layer that has voxels only in certain places as seen in the picture. The additional voxel prevents the rotation of the shape. But you have to make sure that the allowed rotations are still possible, e.g. if you place the notches in different places rotation around the z-axis is also no longer possible. An example can be seen in Figure Cubes can be cut in many different ways, to approximate shapes such as given in Figure<\float|float|tbh> |Diagonally cut cube> use the 2x2x2 cube displayed there. It is, of course, also possible to simulate diagonally cut squares this way. The squares need to be 2 layers thick. Cairos are pentagons but luckily they have only 4 rotations, so it is possible to emulate them using squares. Figure<\float|float|tbh> |Emulation of Cairos using squares> demonstrates how that can be done. To be done. Sometimes it is possible to emulate edge matching problems by using notches and dents at the outside of the shapes. There are many other shapes that can be emulated. As one example I will show 2 ways to emulate William Waites (see Figure<\float|float|tbh> |The Knit Pagoda> ). Besides their shape the pieces have a top side and a bottom. Figure<\float|float|tbh> |Emulation for one of the Pieces> shows 2 possible ways to emulate these pieces. Both shapes emulate the T-shaped piece seen on the bottom right. It is quite easy to see how the pink shape works. It is constructed starting with a 3x3x1 square, and for each side adding a cube at the centre at the centre to represent eachside that bulged outward, and removing one cube for each side that bulges inward. Finally add a cube atop the centre of the 3x3 square to make it unflippable. The second is quite a bit more complicated to understand. Here the starting point is a 2x2 square. A cube is added or removed for the bulges just as in the other case but those cubes cannot be in the middle. They are at one side so that the cube from an outer bulge can go into a gap created by an inner bulge. The resulting shape for one unit contains 4 cubes along a zig-zag line. You can see it by looking for the lighter cubes in the cyan shape above. This way has the additional advantage of avoiding flips because when the piece is flipped over the orientation of the bulges changes and the cubes do not mesh. <\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<\float|float|tb> |Defining problems on the Puzzle tab> ) provides all the tools needed to build a variety of puzzle problems that are suited for the . 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 disassembled) with these pieces (Figure ). Bear in mind that a simple problem also implies 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 as 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 original. 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. Until now we dealt with shapes as rather abstract concepts. Only by these shapes to the pieces or the goal of a puzzle do 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 necessary that all shapes be used in a single problem or in any problem at all. <\float|float|tb> |A simple puzzle problem with multipieces> 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 (in parentheses) 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 removes only a single instance and needs to be repeated for removing multipieces. Most of the time it is necessary to add one instance of all defined shapes to the puzzle. If there are a lot of them this can take while. This is what the > button is for. It increases the piece counter for each shape (except the one assigned for the result) by one. Or it adds a first instance of the shape to the problem. The > button removes all pieces from the problem. Since it doesn't make sense for any shape to be both the result and a 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 if one or more pieces contain any variable voxels. is capable of handling piece ranges instead of a fixed number of pieces. This feature is useful when you want to search for puzzles instead of solving a given one. If there is a range defined for one or more pieces then finds all ways to assemble the defined result using a number of pieces within the given range. As an example let's take Ronald Kint-Bruynseels Clarissa-Burr (see ). This puzzle consists of 2 different shapes. When Ronald defined this puzzle he had to try all possible combinations of the 2 pieces, beginning with 6 pieces of shape A and zero of shape B, over 5 times A and one B up to 6 times B. This can now be done way more easily with piece ranges. Simply tell that the result should be made out of 0-6 pieces of shape A and 0-6 pieces of shape B, or if you want to ensure that at least one of each shape is used, use ranges 1-6. Then solve. Piece ranges can be easily defined using the > button. This will set the minimum of the piece range for the current shape to zero. With that you can define the range by first adding pieces (meaning the difference between the maximum and the minimum number of pieces), then set the minimum to zero and then add the missing pieces. This should cover the most used usage cases. For example: suppose you want to add a piece that you want to use 3, 4, 5 or 6 times in your puzzle. The piece range is 3--6. To enter those values you first add pieces. Then you press the > button getting a piece range 0--3. Now you add another 3 pieces and you get the range you want. Except for the > button, all other buttons always change the minimum and the maximum of the piece range. If this calculation is too hard for you, you can use the problem detail dialogue (see section ) to enter the ranges directly without the need for calculations. 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 attempts 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 pieces involved 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 cannot 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 necessary to place all the pieces into their own group when you want the puzzle to completely disassemble. 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 it 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 in which the grouped pieces are treated as a single piece. But it is 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 This technique can also be used for pieces that may be entangled, in case one is searching for possible designs. If these pieces are indeed inseparable 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 specify 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 pieces involved -- 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. 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. 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 cannot, 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 has run 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 in practice 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. All settings that cannot be set directly on the main problem tab can be set within the > window (Figure<\float|float|tbh> |The Problem Details Editor> ) which opens by clicking the > button. This window allows you to define groups and to define piece ranges without having to subtract values. The window also contains rarely-used parameters. Let's first see how piece groups are defined using this window. Although the above section may sound complicated, implementing piece groups is actually very simple. All actions take place in the >. 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 and third ( and ) show the instances range of each. 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 default colour of the corresponding shape, cells with zero are grey 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 . Now to the piece ranges. It is possible to enter the values directly into the min and max columns of the table. You just have to keep in mind, that min has to be less than or equal to max. This is enforced by the program, so that max will change, if you enter a value in min that is larger than the current maximum. The same holds true for the minimum, when changing the value in the max column. You also need to keep in mind that the table contains entries only for shapes that are already used in the current problem. You cannot (yet) add another shape to the problem using this dialogue, but you can remove a shape by setting the minimum and the maximum to zero. Finally, this window also contains an entry field called > (empty variable cubes). This value is used by the program, when piece ranges are used, in which case it is not possible for the program to determine many holes there will be in the final solution. Because this missing information results in a huge slowdown as many more possibilities have to be tried, it is possible to use this field to specify the maximum number of holes allowed. If the number of holes should not be limited, the field should be left empty. automatically adds the most probable rules for colour constraint when you add a new colour or when a new problem is created, namely that each colour can be mapped into itself, i.e. a piece voxel with colour C can go into a result voxel of colour C. If you don't want that or if you need additional placement possibilities, you can change the colour constraint rules in the colour assignment section. The > panel (Figure<\float|float|tbf> \ \ \ \ |Colour assignment> ) 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 which colour(s) in the pieces. By allowing certain combinations (which is in fact prohibiting all other combinations), constraints are imposed on the 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 sorted either by the piece colours or by the result colours. The buttons > and > switch between these two views. 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 at 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 relationships, 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 \ be rearranged only with the left and right arrow buttons of the section, but more advanced management procedures may be added in the future. <\description-compact> Keep this value as small as possible, because the more holes a puzzle contains the longer the solving will take. Normally the value is undefined, meaning the number of holes is limited. So if you know the number of holes you want, or you want to limit them, or the solving takes too long, use this field. 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 even if the > tab (Figure<\float|float|tbf> |Solving puzzles> ) has quite 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 on 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 to the solutions in detail, and to organize the solutions that have been found. 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 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 the following options for the solver. All deal with the kind of information the solver will report. <\description-compact> >When checked, the solver will try to disassemble any 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. >When checked, the solver will only count the number of solutions; it will drop the solutions right after they are found. Check this option if you're interested only in the number of solutions and not in the solutions themselves.\ >When checked, the program functions the same as with enabled, except that the disassembly is stored, only the assemblies and some information the disassemblies (like their level). This is useful if you have a problem that has many solutions and you want to find the most interesting solutions. Disassemblies take up a lot of memory within the computer so it is useful to just save some information while solving the puzzle and then later on, when everything is finished, recalculate the disassemblies for the interesting solutions. When this box is checked, the program will not remove mirror solutions. Two solutions are mirror solutions are solutions when one solution is a real mirror of the other. This can happen only, when either all pieces are self mirroring (note that all flat pieces are self mirroring) or they have a mirror pair in the piece set. Sometimes it is possible to create the mirror solution by flipping the solution over. These are mirror solutions to and are still removed. This option is useful when using piece ranges, as the mirror removal would remove too many solutions, like solutions with different piece sets. >This option lets you choose the order in which the solutions are presented while the solver runs. There are 3 possibilities: <\enumerate-numeric> unsorted: The solutions are sorted in the order in which they were found. by level: The solutions are sorted by the level. First by the number of moves to remove the first piece, if that is identical then by the moves for the second piece, and so on. by number of moves to disassemble: The solutions are sorted by the sum of all moves required to completely disassemble the puzzle. >If a puzzle has very many solutions, it might not be necessary or even possible to save all of them. E.g for polyomino-like puzzles it might be nice to keep just every 1000th of the millions of solutions, so as to have a profile of the possible solutions. Here you can specify every how many-th solution you want to keep. A 1 means you keep every solution, a 100 means you keep the first and the 101st and the 201st and so on. >Limits the number of solutions to be saved. There will never be more than the specified number of solutions in the list. When the list is full the program has 2 choices:\ <\enumerate-numeric> Solutions are sorted: The programs throws away the solutions at the end. So low level solutions are removed. Solutions are unsorted: The program starts to throw away every 2nd solution. So if you started with a drop-value of one and the list is full, the program starts to drop every 2nd solution it finds, and only adds every 2nd solution to the list. But for each added solution it also removes every 2nd solution that was already added to the list. After a while the list contains only every 2nd solution then the program only adds every 4th solution and removes again every 2nd solution that had been on the list, and so on. This sounds complicated but what is does is ensure you have an nice crossection of all the solutions, and not just the first or last N found. Next to the solver options are some buttons to direct the solving process. Problems can be solved either in an automatic way or (manually) step-by-step. An automatic search will proceed until 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 is of course omitted when the option is left unchecked. The automatic solving process can 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 that the saving of the internal state of the solver is very version dependent. So it is likely that a new version of cannot resume solving a puzzle saved with an older version. So it is good practice to finish solving jobs with one version of before updating to the next. When the solver is running it provides a lot of information about 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<\float|float|tbh> |The solver information> ). Keep in mind that the estimated time to finish can be off by a very big amount. It happens often that the figure starts with ages and millennia and then the solving is finished within a few seconds, so be careful not to give up too soon. 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 spent on the search and an estimate of the time still needed to finish the solving process. Note that these 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 (>). Probably most important is the > and result information provided by the solver. The line tells you not only what the solver is currently doing, but 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 attempts 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. >In this second stage of the preparation, the placements for each piece are tested for plausibility. Some placements are just nonsense in 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 being tested for disasembability. A search was started and interrupted. The search has been completed, all the solutions found, ordered by the set up sorting criterium, can 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 before halting. Something is wrong with the puzzle and an error message, providing more specific information on the error, is usually displayed. Finally, the solver gives information about the > found thus far (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 reported (and in fact tested) only if 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 solutions it finds 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 useful only 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<\float|float|tbh> |Placement browser> ) 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, those positions of piece S will be visible in the list. If you want to see every placement tried, you have to either initialise a manual search (click the button), stop the assembler before is starts to do anything (click while in preparation or optimisation stage), or wait until the assembler has finished its work. The > window (Figure ) has a very simple layout and consist mainly of a 3-D viewer and some additional scrollbars. This 3-D viewport, which shows the outline of the result shape and therein the shape for which the possible positions are to be analysed, behaves similar to the viewport in 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 (including each instance of a multipiece) can be selected with the scrollbar 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 can get sorted by the total number of moves (in case disassembly was requested) after the search is completed. All solutions that have been found can be inspected at any time, this does not interfere with the ongoing solving process. But completing the search and resetting the scrollbar for browsing the solutions may be needed to show the solutions properly ordered. This panel has four components: <\itemize-dot> a scrollbar (>) to browse the different solutions, a second scrollbar (>) to view the moves involved in the disassembly, an array of buttons with very short labels to organize the solution list, and a list of all instances of the pieces in the puzzle problem, which allows you to alter their visibility 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 text box left of the it. Above the scrollbar there is an indication of the total number of solutions in the list. When the scrollbar is active it can also be controlled by the and cursor keys. Keep in mind that the number of solutions in the list may be different from the real number of solutions. The correct number of solutions for the problem is shown in the solver progress section. The second scrollbar (>) also has a text box 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 disassembly, 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 is shown the number of moves required for the disassembly, followed by the level(s) of the selected solution. Note that this scrollbar is visible only for solutions that have disassembly instructions available. 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. Below the scrollbar are 2 fields that show you 2 numbers associated with the currently selected solution. The first is the assembly number and the second is the solution number. Both numbers define when a solution was found. The first assembly found gets assembly number one. But for example that one might not be disassembable so it gets thrown away. The second assembly found gets assembly number two, and if it is also disassembable it gets solution number 1. So you will see assembly 2 and solution 1 in these 2 fields for the given example. The big button group below the Solution selector and animator lets you modify the solutions. They are activated only when no solver is running. With the buttons in the first row you can re-sort the solutions by the same criteria as you can select for the solver. You can sort them in the order they were found (unsorted) or by level or by sum of moves to completely disassemble and additionally be the pieces that are used in the solution. The second row of buttons allows the deletion of certain solutions from the list. <\description-compact> >removes all solutions >removes all solution before the currently selected solution. The selected solution is the first one in the list that is not removed >removes the currently selected solution >removes all solutions behind the currently selected one. The selected on is the last one that is kept >remove all solutions that have no disassembly The last row of buttons allow the addition or removal of disassemblies to the list of puzzles. <\description-compact> >deletes the disassembly of the currently selected solution. The disassembly is replaced by data containing only information the disassembly, so you can still sort the solutions >deletes all disassemblies >adds the disassembly to the currently selected solution >add the disassembly to all solutions. Already existing disassemblies are thrown away >add the disassembly to all solutions that do not have one. Solutions that already have a disassembly are left unchanged 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 default 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 visibility states remain invariant in selecting solutions. Additionally it is possible to set the visibility state of a piece to invisible by pressing and then clicking onto the piece in the 3-D viewer. This is handy when using custom colours and the default colour is not visible or when there are many pieces and the distinction by colour becomes hard. 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). As not all pieces are used in all solutions, the list of pieces shows only the names of those pieces that are really used in the currently selected assembly. All other boxes become very small and contain no name. This should help to quickly find out which pieces are used and which piece on screen corresponds to what item in the piece visibility selector. <\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 of comming attractions. 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 such as the name of the designer, or a 'to do' list for your own designs. The > entry on the menu opens a window that allows you to export a portion of the current puzzle to (a list of) images (see Figure<\float|float|tbf> |The image export window> ). On the right the window has a 3D view, and on the left it has input elements that control what is being created. 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 (a shape that was made on the entities tab) 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. The first assembly of that problem 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. What to export is the first thing that you have to select. Naturally only the choices are available for which the puzzle has data. So if you have not run the solver on the current puzzle, it is impossible to export solutions or assemblies. Above these selectors 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 the program. The file name is just a prefix, so if you keep 'test' as file name you get files of the form 'test000.png', 'test001.png', >. ( creates only PNG image files) 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 being, it will be used later on. Above these input elements you find the last section that defines your output. Here 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 choose whether you want to use the constraint colours for the output or rather the default colour of the shapes. The checkbox makes draw pieces that are not involved in the current move in a lighter colour, so that the pieces actually moving 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. There are 2 choices: either define the pixel size directly, or define the size of the image in millimetres 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 trimmed. 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 accommodate the horizontal spread of the pieces. When you have finished with all settings, press . You will see a flurry of images in the 3-D 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 beside 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 facilities are far from what we want them to be, many important features are missing, so you can expect some progress in later versions of . STL, which stands for Standard Triangulation Language or Standard Tesselation Language is a file format used by stereolithography software. STL-Files describe the surface of 3-dimensional objects. can export single shapes into STL files so that 3D printers can quickly fabricate prototypes of them. The main menu entry > opens the window seen in Figure<\float|float|tb> |The STL-Export window> . The window has shape selector, a 3-D view of the selected shape and some parameters that control the shapes created. > and > control the name and position of the generated file. > controls the base length of the created cubes. > controls the size of the bevel and > allows a gap between the pieces, so that it is actually possible to assemble them. If the shapes were made to correct sizes they would touch, making movement impossible. The STL-Export right now works only for cubes. Triangles and spheres are not working. Also the shapes to export must not contain any variable voxels. <\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 more different space grids, add parameters to some grids (lengths and angles). Add rotation checks to the disassembler. Add a shape generator: create all piece shapes that fulfil certain rules (shape, colours, 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 in parallel on several computers and then the solutions are back together in one file. Improve multi-threading so that multi-core CPUs are better used. Better tool for colourization of a piece. E.g. checkering, but it needs to be more general than just checkering. 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. ''Unificator'' a tool that makes it easy to check the results of adding color constraints. For example: suppose you have designed a puzzle with one interesting solution and many uninteresting ones and you want now, by adding color constrains, make that one solution unique. It can be a labor intensive task to do that. The unificator would help here by quickly showing the results of adding color here or making a piece that color, ... exploded view 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 approach 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 possibilities 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 instead of doing a full analysis. So what do the possibilities mean. <\description-compact> a shape containing no variable cubes. This shape is directly used a shape containing 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 fulfil 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 would 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 machine 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 colours are just a number (up to 2 digits) that are simply written as a decimal number and are appended to the voxel state. If the colour number is 0 (which is the default colour) 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 default 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 text ``S1-Box'' in it. <\description-compact> This file uses the piece range feature and the solutions contains all solid 6-piece burrs. This is done by having all notchable pieces in the problem and having a 0-6 range for all of them. Now each of the pieces may be between 0 and 6 times in the solutions. If you want to get the well known 314 solutions you have to include the mirror solutions. <\description-compact> Stewart Coffin, #197-A, USA This puzzle shows off the sphere gridspace. It also demonstrates that is is possible and useful to include more than one problem within one file. <\description-compact> Bill Cutler, 1992, USA This puzzle demonstrates the triangle space grid. You can see that you can stack many layers on top of each other. <\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>