polycube: A polyomino and polycube puzzle solver. Copyright 2011 Matthew T. Busche. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . _______________________________________________________________________________ COMPILING THE SOFTWARE If you're on a windows machine, you can skip the compilation process and just use the provided windows executable. The C++ software makes use of two third-party support packages: boost and the Mersenne Twister random number generator. To make it as easy as possible to build this software, I've included those portions of those libraries sufficent to build the solver. (In an effort to keep the download size small, I've kept only those source files I use and the copyright information. It is conceivable I've mistakenly stripped boost headers that are conditionally included for specific build environments. If you get file-not-found errors during the build I recommend you download the full boost library and wholly replace the boost directory structure in the polycube download.) The first (and only) time I tried to build the boost library it blew up in my face. Clearly I did something wrong, but hadn't the patience to figure it out. Instead I just added the handful of needed source files from the boost package to my compile line. To build the solver you need only execute this single compile line: > cd src > g++ -O3 -o polycube.exe -DDSFMT_MEXP=19937 -DNOSIGNALS -I . -I boost_1_46_1 -I dSFMT_2.1 -lstdc++ *.cpp dSFMT_2.1/dSFMT.c boost_1_46_1/libs/program_options/src/*.cpp The command line options for other compilers should be about the same. If you compile with -Wall (to get all warnings) you'll see quite a bit of warning noise produced from the boost libraries. I use these warning options when I compile to avoid these problems: -Wall -Wno-missing-braces -Wno-parentheses -Wno-sign-compare -Wno-strict-aliasing -Wno-unused-local-typedefs If you're on a Unix box, drop the ".exe" from the filename of the generated executable; and also drop the -DNOSIGNALS from the compile line -- this will allow you to send signals 10 or 12 to the process to cause it to (respectively) asynchronously display status or a puzzle trace. If you don't have a compiler, you can get the GNU compiler collection (GCC) for many platforms for free. For windows you can get g++ either by installing Cygnus or MinGW. I've tried out both and I recommend MinGW for the following reasons: 1) The applications you build with the Cygnus version of g++ have dependencies on the Cygnus DLL, so you have to have Cygnus installed on your machine in order to run the application, making it difficult to share your apps with your friends. Apps built with the MinGW version of g++ depend only on standard Windows libs. 2) The default installation selections for Cygnus do not include the g++ compiler so you have to be sure to click off the development package during installation. In contrast, the whole purpose of MinGW is GCC and the GNU binutils and so there's no such installation selection step. 3) If all you want to do is build the polycube app, then Cygnus is overkill as it includes worlds of stuff you don't need. MinGW is a comparatively miniscule download that includes only GCC and GNU binutils. _______________________________________________________________________________ PUZZLE DEFINITION FILES Polycube requires at least one puzzle definition file as input. Puzzle definition files are fairly straightforward and you can probably learn everything you need to know by looking at a couple of provided samples in the def directory. Nevertheless, a somewhat formal description of these files is here provided. A puzzle definition file is line oriented. Blank lines are ignored (unless they are in the middle of a layout directive). A pound character begins a comment that runs to end of line. There are three types of directives that can appear in a puzzle definition: D - Definition C - Coordinate L - Layout While a coordinate directive is written on a single line, definition and layout directives span multiple lines, but the first line for all directives share a common format: N[:attribute1=setting1[:attribute2=setting2[:...]]] where N is the single character name of the directive (D, C or L), and the rest of the line is a colon-separated list of attribute settings. D - DEFINITION DIRECTIVE A definition directive defines a puzzle. The directive begins with a line having the following format: D:xDim=:yDim=:zDim=[:oneSide[=1]] The directive ends with the definition terminator which must appear on a line by itself: ~D Nested between these two lines will be L and/or C directives which define the pieces of the puzzle. The user defined parameters XDIM, YDIM and ZDIM must all be strictly positive integers. For 2-D polyomino puzzles, set zDim=1. The optional parameter oneSide is to declare a one-sided polyomino puzzle. Declaring a oneSided puzzle requires zDim to be set to 1. Because oneSide is a boolean valued attribute the assignment of the value 1 is implied and no explicit assignment is required. Note that all puzzles have the shape of a cuboid: a 6-sided object with rectangular sides. To solve puzzles with other shapes, define a cuboid large enough to encompass your puzzle and define a stationary piece to fill in the unwanted space. C - COORDINATE DIRECTIVE A coordinate directive specifies a single puzzle piece by the (x,y,z) coordinates of it's constituent cubes. The directive has this form: C:name=:[type=M|S:]layout= [, [, ...]] is an arbitrary string name used in solution output. Although there is no limitation on the permitted length of names, short names (1 or 2 characters) make for better text-based graphics output. The names "." and "#" are reserved. A piece's type may be set to either M (mobile) or S (stationary). A stationary piece is loaded into the puzzle at the exact coordinates given in the layout field. A mobile piece is free to be rotated and translated to fit any open space in the puzzle. If a type is not specified the piece defaults to type M. As noted above, you can use stationary pieces to define puzzle spaces that go beyond simple rectangular boxes; but you can also use them to simply force certain pieces into particular positions in the puzzle if that suits your fancy. The layout attribute is a series of (x y z) coordinates with each triplet separated by a comma. The x, y and z scalars within each coordinate triplet are separated by white-space (not commas). Here is a sample coordinate directive for a mobile piece named V in coordinate format: C:name=V:type=M:layout=0 0 0, 1 0 0, 2 0 0, 2 1 0, 2 2 0 L - LAYOUT DIRECTIVE A layout directive is a multi-line directive allowing you to define one or more pieces with simple text-based graphics. The directive has the following form: L[:stationary=S1[ S2[ ...]]] ~L The stationary setting is white-space separated list of names of pieces that appear in the layout that should be loaded in exactly the positions shown in the . (By default, the pieces defined in are mobile.) The is just a text-graphics based representation of one or more puzzle pieces. Here is a layout directive defining two of the twelve pentominoes pieces: L Z Z . Z . Z Z W W W . W W ~L The lines between the L and ~L are your drawing area which can be as large as needed to define all your pieces. Horizontal white space is ignored so you must use the special character "." to indicate an unoccupied cell. The line immediately following the directive has a y coordinate value of YDIM-1 and each subsequent line decrements the y coordinate value. This is important if you are defining stationary pieces. Here is a layout directive that will fill the center squares of an 8x8 puzzle with a stationary piece named '*': L:stationary=* . . . . . . . . . . . . . . . . . . . . . . . . . . . * * . . . . . . * * . . . . . . . . . . . . . . . . . . . . . . . . . . . ~L For three dimensional puzzles, the layout depicts horizontal slices of the puzzle box like the layers of a cake. Each layer on each line is separated by a comma. The first slice (on the left) shows the bottom layer of the box (Z=0); the next slice is the second layer of the box (Z=1); etc. Note that if you happen to have a solution to the puzzle you are solving you can just copy that solution into the layout directive to define the entire puzzle in one go. For example, here is a layout-based definition for the Tetris Cube puzzle: D:xDim=4:yDim=4:zDim=4 L F F D D, D D D C, K K C C, H H H H F F J G, K F I I, K C C I, K E H B A L J G, A L J J, A A A I, E E E B A G G G, L L L J, E L B I, E B B B ~L ~D _______________________________________________________________________________ RUNNING THE SOFTWARE Move the compiled executable to someplace in your PATH or to the directory where you want to run it. Polycube reads puzzle definitions from either a user provided file list or from standard input and prints solutions to those puzzles to standard output. For example: > polycube def/pentominoes_10x6_def.txt def/tetriscube_def.txt or > cat def/tetriscube_def.txt | polycube By design, every command line option can take an argument, but not all of them require an argument. For example, the -r option is used to enable the rotational redundancy image filter. If you include an argument to the -r option, it is taken to be the name of the piece you want to constrain to attempt to eliminate rotationally redundant solutions from the search. If you don't pass an argument, then the argument defaults to the value '#' which is interpreted as a wild-card and causes the solver to make a good pick for the piece to constrain. Now, if you try to execute the command line: > polycube -r mypuzzle.txt You'll find that the program just sits there and does nothing! The problem is that it's interpreting mypuzzle.txt as a piece name argument to the -r option and then having no puzzle definition file, it's trying to read a definition from standard input! For this reason it's a good idea to get in the habit of adding the end-of-option indicator (--) to your command lines between your last program option and your first puzzle definition file name: > polycube -r -- mypuzzle.txt Although I'm generally big on having software exhibit good default behaviors, polycube was written firstly as a tool to analyze the tradeoffs of different puzzle solving techniques and so defaults to the simplest of behaviors: using DLX with a min-fit heuristic. But you can usually get much better performance by turning on various backtrack triggers and/or image filters. Here are a few suggestions: 1. Use the -r option if you're trying to find all solutions to a puzzle. This enables the rotational redundancy filter and can give huge performance benefits if your puzzle has rotational symmetries. 2. Use the -p option. This turns on parity backtrack triggering. It has very little overhead and so can do very little harm to your performance, but can somtimes (depending on the puzzle) give a significant performance kick. 3. Use the -V option for 2D puzzles. This performs a one-shot volume constraint filter of all piece images to eliminate images that can't possibly lead to solutions. This is almost always beneficial and is sometimes very beneficial indeed. 4. The -i option provides lots of interesting information about your puzzle, and various statistics about the search performed. The solver currently has available 4 different puzzle solving algorithms: 1. DLX 2. MCH 3. EMCH 4. de Bruijn By default DLX is used, but you can activate the other algorithms by configuring an enabling threshold for the algorithm. When the number of remaining pieces reaches this threshold the algorithm is activated; and when the number of remaining pieces increases beyond this threshold, the algorithm is again deactivated. You can only specify one enabling threshold for each algorithm. So you can't, for example, use DLX to place the first piece. MCH to place the next; and DLX again to place the third. Furthermore the algorithm list above defines a pecking order among the algorithms. This means, for example, you can't set the enabling threshold for EMCH above the enabling threshold for MCH. Here is a valid algorithm configuration to solve the Tetris Cube (which performs very well): > polycube -i -r -p -m11 -e6 -b4 def/tetriscube_def.txt The de Bruijn, MCH and EMCH algorithms model the occupancy state of the puzzle with a single 64 bit integer so these algorithms cannot be activated until the volume of the puzzle is reduced to 64 or fewer units. If you use an enabling threshold that would violate this constraint, the algorithms are simply activated as soon as the puzzle volume reaches 64 units. The following synopsis is generated by running polycube with the help option: > polycube --help Takes a list of polycube puzzle definition files and outputs all solutions to them. If no puzzle definition files are provided, puzzle definitions are read from standard input. Common configuration options are: -b [ --bruijn ] arg Sets the number of remaining pieces when the EMCH tiling algorithm is turned off and de Bruijn's algorithm is turned on. A bruijn setting of zero turns de Bruijn's algorithm off. The default value is 0. -e [ --emch ] arg Sets the number of remaining pieces when the MCH algorithm is turned off and the Estimated-MCH algorithm is turned on. Setting emch to zero or to any value less than or equal to the bruijn setting disables Estimated-MCH altogether. The default value is 0. -f [ --format ] arg Selects the format of solution and trace output. The configuration argument may be up to two characters. The overall format of each solution or trace output is specified by one character: B - Brief (default) F - Full S - Sub-puzzle Brief output only displays placed pieces. Full output is in the form of complete puzzle definitions which may be reapplied as input. Sub-puzzle output is like full output, but placed pieces are encoded as stationary, which is useful when combined with the -g and -R options to break one large puzzle into smaller subpuzzles. The output format of pieces is specfied by one character: L - Layout (default) C - Coordinate These two output formats are identical to the puzzle piece input formats of the layout (L) and coordinate (C) directives. -F [ --fitFilter ] [=arg(=-1)] Set the minimum number of remaining pieces for the invocation of fit-based filtering of puzzle piece images. A fit filter operation examines each remaining row in the DLX matrix to see if using that row would result in a puzzle configuration where some hole can no longer be filled or some piece can no longer be placed. If this occurs, the row is temporarily removed. Setting fitFilter to the special fixed value -1 is equivalent to setting to the number of pieces in the puzzle and results in fit-based filtering to be applied just once before the search begins. A setting of 0 disables fit-based filtering altogether. Note that filtering is implemented on the DLX matrix and so decreasing the setting below the maximum of the mch, emch and bruijn settings has no affect. The default setting is 0. -g [ --goal ] arg Each time the number of remaining pieces equals the goal, a solution is declared and processed, and a backtrack is forced (even if additional pieces could be placed). The default setting is 0. Setting the goal to non-zero values is useful for breaking down a large puzzle into many smaller puzzles. See also the -f and -R options. -i [ --info ] [=arg(=1)] If set to true, input configuration, puzzle properties, and search statistics are output. By default this feature is off. -m [ --mch ] arg Sets the number of remaining pieces when the DLX algorithm is turned off and the MCH algorithm is turned on. Setting mch to zero or to any value less than or equal to the emch setting disables MCH altogether. The default value is 0. -o [ --order ] arg Configure DLX ordering heuristics used to pick which hole to fill or piece to place at each step of the DLX algorithm. Different heuristics may be specified for use when there are different numbers of pieces left to place in the puzzle box. The ordering specification (arg) has the following format: N1[@A1][=R1][:N2[@A2]=R2[:...]] where N1, N2, ... are names of available heuristics; A1, A2, ... are arguments which, depending on the heuristic, may or may not be required; and R1, R2, ... are the number of remaining pieces causing the heuristic to be enabled (replacing the previously enabled heuristic). One heuristic may be specified without an R setting which causes it to be the first heuristic enabled. There are currently five heuristics to choose from: f, l, a, A and R. All of these heuristics will pick a column with zero or one fits over any other column (with a zero fit column taking precedence over a one fit column). Assuming all columns have more than one fits, then the heuristics have these behaviors: f: Picks the DLX column (hole or piece) with minimum fits. This heuristic takes no arguments. l@a,b,c: Picks the GridPoint that minimizes the linear sum a*x + b*y + c*z. a[@i[,xc,yc]]: Picks the GridPoint with minimum angle from origin (xc, yc) in the X-Y plane relative to the reference angle i (which should be given in degrees -- not radians). The default values for (xc, yc) are the mid point of the puzzle. The default value for i is zero. A[@i[,xc,yc]]: Identical to a, but maximizes the angle instead. R[@xc,yc,zc]: Picks the GridPoint with maximum distance from (xc, yc, zc). The default value for (xc, yc, zc) is the center of the puzzle. In addition, these shorthand notations are available: x: Equivalent to l@1,0,0 y: Equivalent to l@0,1,0 z: Equivalent to l@0,0,1 X: Equivalent to l@-1,0,0 Y: Equivalent to l@0,-1,0 Z: Equivalent to l@0,0,-1 xyz: Equivalent to l@1,1,1 The default heuristic is f. -p [ --parityBacktrack ] [=arg(=1)] If set, parity constraint violations are checked after each piece placement. If the check fails, the algorithm will immediately backtrack. These checks are implemented in all three basic algorithms: dlx, mch and debruijn. Unlike parity filtering, a parity backtrack check is extremely fast and adds little processing overhead to the algorithms. If the puzzle was parity filtered immediately prior to placing the subject piece, then this parity check cannot fail (since all images causing a parity check failure would have already been filtered from the DLX matrix. By default this feature is off. -P [ --parityFilter ] [=arg(=-1)] Set the minimum number of remaining pieces for the invocation of parity-based filtering of puzzle piece images. A parity filter operation examines each remaining row in the DLX matrix to see if using that row would result in a parity violation for the puzzle as a whole. If a violation would occur, the row is temporarily removed. Setting parityFilter to the special fixed value -1 is equivalent setting it to the number of pieces in the puzzle and results in parity-based filtering to be applied just once before the search begins. A setting of 0 disables parity-based filtering altogether. Note that filtering is implemented on the DLX matrix and so decreasing the setting below the maximum of the mch, emch and bruijn settings has no affect. The default setting is 0. -q [ --quiet ] [=arg(=1)] If set to true, solutions are not displayed. This is useful if you're only interested in the run time or statistical information output by the info option. By default this feature is off. -r [ --redundancyFilter ] [=arg(=#)] Set the name of the piece the Solver limits rotations and/or translations to reduce or potentially eliminate rotationally redundant solutions without loss of unique solutions. The special value '#' causes the solver to pick a piece for you. The special value '.' turns this feature off. The redundancyFilter piece must have a shape that is unique from other pieces in the puzzle. The default value is '.'. -R [ --redundancyFilterFirst ] [=arg(=1)] If set to true, the DLX column corresponding to the piece selected for rotational redundancy filtering is forcibly selected to be processed first. This option is meaningless if not combined with the -r option. This option is useful when also combined the -f, and -g options to try to make a set of generated puzzle subproblems rotationally unique. By default this feature is off. -s [ --sample ] arg Enables Monte Carlo sampling of the search space. The configuration argument is of the form T,R,S where T is the number of trials to perform, R is the number of remaining pieces that triggers the start and end of a trial, and S is the 64 bit seed value for the Mersenne Twister 19937 random number generator. When enabled, prior to the execution of any backtracking algorithm, but after initial application of requested image filters, the nodes under each DLX column are reordered randomly so that the order of the search executed by DLX will be randomized. The first time a piece is removed from the puzzle when exactly R pieces remain (prior to the removal) the Monte Carlo trial is ended. DLX then completely unwinds and the matrix is randomly ordered again to start the next trial. Statistics output at the end of the program will be for all trials, so you must divide by T to get per trial statistics. The conditionals to terminate a trial are only implemented in the DLX algorithm, so R must be greater than or equal to the enabling threshold of the MCH, EMCH and de Bruijn algorithms. (See mch, emch and bruijn.) -t [ --trace ] [=arg(=1)] If trace is set to some positive number K, then after each piece placement, if there are at least K-1 pieces remaining to be placed, then the state of the puzzle is displayed. Also, after each piece removal if there are at least K pieces remaining to be placed, then the state of the puzzle is displayed again. If K is negative, then the state of the puzzle is displayed only after a piece is placed and only if there are exactly -(K-1) pieces left to place. If K is zero, then trace output is disabled. The default value is 0. -u [ --unique ] [=arg(=1)] If enabled only rotationally unique solutions are output. Activating this option enables a solution filter that compares each solution found to all rotations of all previously discovered solutions (via binary search). If the new solution is found to be identical to some rotation of some previously discovered solution, then the solution will still increment the total solution counter, but is otherwise discarded. If the solution is found to be unique, then all rotations of that solution are calculated and added to the list of solutions filtered against. This filter is forcibly disabled if the puzzle has no symmetric rotations, or if the redundancyFilter is enabled and it successfully expunges redundant solutions from the search space. By default this feature is off. Note: The filter uses 1 byte per GridPoint in the puzzle cuboid per unique soltuion per symmetric rotation, plus additional memory for STL vector overhead. So if a puzzle has hundreds of millions of unique solutions, use of this filter may cause you trouble. -v [ --volumeBacktrack ] arg After placing a piece, if the number of remaining pieces equals at least the volumeBacktrack setting, then the remaining puzzle space is examined for volume constraint violations. If an isolated sub-space is found that cannot possibly be filled by the remaining pieces (because no combination of those pieces gives a total volume that matches the volume of the sub-space), then the search algorithm immediately backtracks. Unlike volume filtering, volume backtracks do not require the use of DLX. A setting of 0 disables volume-based backtrack altogether. The default setting is 0. WARNING: the memory required by the internal volume monitor grows geometrically with the number of different piece sizes. -V [ --volumeFilter ] [=arg(=-1)] Set the minimum number of remaining pieces for the invocation of volume-based filtering of puzzle piece images. A volume filter operation examines each remaining row in the DLX matrix to see if using that row would result in the parititioning of the remaining puzzle space with one of these new subspaces having a volume that cannot possibly be filled with the remaining pieces of the puzzle. If this occurs, the row is temporarily removed. Setting volumeFilter to the special fixed value -1 is equivalent to setting to the number of pieces in the puzzle and results in volume-based filtering to be applied just once before the search begins. A setting of 0 disables volume-based filtering altogether. Note that filtering is implemented on the DLX matrix and so decreasing the setting below the maximum of the mch, emch and bruijn settings has no affect. The default setting is 0. WARNING: the memory required by the internal volume monitor grows geometrically with the number of different piece sizes. Command line only options: --conf arg Set configuration file name. --help [=arg(=1)] Print program synopsis and exit. --version [=arg(=1)] Print version information and exit. _______________________________________________________________________________ SOLUTION OUTPUT Solution output is sent to standard out (i.e., to the console). Solution and trace output format is controlled by the -f (format) option. The format has two single character settings. First, the puzzle format which is one of: B - Brief (default) F - Full S - Sub-puzzle Second, the piece format which is one of: L - Layout (default) C - Coordinate Here is a sample Tetris Cube solution output with default output format settings: # --- SOLUTION 1 --- D E E C, D L E C, D H K K, H H H H E E C C, L L B K, D L L K, D G J K A E C F, A L B F, A A A J, I G J J A B F F, B B B F, I I I J, I G G G In this layout piece format, the occupancy of horizontal slices of the puzzle box are depicted like the layers of a cake. The first slice (on the left) shows the bottom layer of the box (Z=0); the next slice is the second layer of the box (Z=1); etc. This output format is the same as the field of a layout directive described above. If you switch to Full puzzle output (-fF), you get a full puzzle definition: # --- SOLUTION 1 --- D:xDim=4:yDim=4:zDim=4 L D E E C, D L E C, D H K K, H H H H E E C C, L L B K, D L L K, D G J K A E C F, A L B F, A A A J, I G J J A B F F, B B B F, I I I J, I G G G ~L ~D Here is a sample of full puzzle format with coordinate piece format (-fFC): # --- SOLUTION 1 --- D:xDim=4:yDim=4:zDim=4 C:name=A:type=M:layout=0 0 0,0 1 0,0 1 1,0 1 2,1 1 2,2 1 2 C:name=B:type=M:layout=0 0 1,1 0 0,1 0 1,2 0 1,2 1 1,2 2 1 C:name=I:type=M:layout=0 0 2,0 0 3,0 1 3,1 0 2,2 0 2 C:name=G:type=M:layout=1 0 3,1 1 3,1 2 3,2 0 3,3 0 3 C:name=J:type=M:layout=2 1 3,2 2 3,3 0 2,3 1 2,3 1 3 C:name=F:type=M:layout=2 0 0,3 0 0,3 0 1,3 1 0,3 1 1 C:name=C:type=M:layout=2 1 0,2 2 0,3 2 0,3 3 0,3 3 1 C:name=K:type=M:layout=2 3 2,3 2 1,3 2 2,3 2 3,3 3 2 C:name=E:type=M:layout=0 2 0,1 1 0,1 2 0,1 3 0,2 3 0,2 3 1 C:name=D:type=M:layout=0 2 2,0 2 3,0 3 0,0 3 1,0 3 2 C:name=L:type=M:layout=0 2 1,1 1 1,1 2 1,1 2 2,1 3 1,2 2 2 C:name=H:type=M:layout=0 3 3,1 3 2,1 3 3,2 3 3,3 3 3 ~D When breaking up a large puzzle with the -g (goal) option, the pieces placed are better listed as stationary so that a subsequent invocation of polycube on the sub-puzzle definition will not move the placed pieces. This is the purpose of the -fS (sub-puzzle) output format. As an example, here is how you can break up the pentominoes 10x6 puzzle into 7 sub-puzzles. o Use -g11 to force solution output when there are 11 pieces left to place (i.e., after just one piece has been placed). o Use -r to get polycube to select and constrain a piece to eliminate rotational redundancies among solutions found. o Use -R to force that constrained piece into the puzzle box first. (Turns out this is not necessary as DLX would have made this decision anyway, but this makes sure it gets done.) o Use -fS for sub-puzzle output which causes placed pieces to be displayed as stationary in solution output. (Note that the X piece is listed as stationary in the output below.) o Use -V just because it's a wonderful. In this case it eliminates the solution where the X piece is jammed into the corner of the solution box. Here is the result: > ./polycube -r -R -V -g11 -fS -- def/pentominoes_10x6_def.txt # --- SOLUTION 1 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . . . . . . . . . . . . . . ~L ~D # --- SOLUTION 2 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . . . ~L ~D # --- SOLUTION 3 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . . . . . . . . . . . . . ~L ~D # --- SOLUTION 4 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . . ~L ~D # --- SOLUTION 5 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . . . . . . . . . . . . ~L ~D # --- SOLUTION 6 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . ~L ~D # --- SOLUTION 7 --- D:xDim=10:yDim=6:zDim=1 C:name=F:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0 C:name=I:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0 C:name=L:type=M:layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0 C:name=N:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0 C:name=P:type=M:layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0 C:name=T:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0 C:name=U:type=M:layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0 C:name=V:type=M:layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0 C:name=W:type=M:layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0 C:name=Y:type=M:layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0 C:name=Z:type=M:layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0 L:stationary=X . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . X X X . . . . . . . . X . . . . . . . . . . . . . . . ~L ~D _______________________________________________________________________________ TRACE OUTPUT For purposes of debugging, understanding, or progress monitoring you can dump the state of the puzzle solution space using the trace option. See the trace option description above for the configuration settings available. Here is some sample output: TRACE 1: . . . ., . . . ., . . . ., . . . . . . . ., . . . ., . . . ., . . . . A . . ., A . . ., A A A ., . . . . A . . ., . . . ., . . . ., . . . . END TRACE TRACE 2: . . . ., . . . ., . . . ., . . . . . . . ., . . B ., . . . ., . . . . A . . ., A . B ., A A A ., . . . . A B . ., B B B ., . . . ., . . . . END TRACE TRACE 3: . . . ., . . . ., . . . ., . . . . . . . ., . . B ., . . . ., . . . . A . . ., A . B ., A A A ., . . C . A B . ., B B B ., C C . ., . C C . END TRACE TRACE 4: . . . ., . . . ., . . . ., . . . . . . . ., . . B E, . . . ., . . . . A . . E, A . B E, A A A E, . . C . A B . ., B B B ., C C E E, . C C . END TRACE TRACE 5: . . . ., . . . ., . . . ., . . . . . . I ., . . B E, . . . ., . . . . A . I E, A . B E, A A A E, . . C . A B I I, B B B I, C C E E, . C C . END TRACE _______________________________________________________________________________ INFORMATIONAL OUTPUT With the --info option activated, before the search begins, polycube prints out various information about optimization settings, puzzle properties, etc; and after the search is complete, it prints out various statistics (like the number of solutions found, number of solutions filtered due to rotational symmetry, and run time.) This should all be self explanatory. Here is sample informational output: # Solver configuration settings bruijn=11 emch=0 outputFormat=BL fitFilter=0 goal=0 info=1 mch=0 orderingHeuristicConfig= parityBacktrack=0 parityFilter=0 quiet=0 redundancyFilter=# redundancyFilterFirst=0 sample=0,0,0 trace=0 unique=0 volumeBacktrack=0 volumeFilter=-1 # Puzzle file PUZZLE_FILE=def/pentominoes_10x6_def.txt # Puzzle size: DIMENSION=10x6x1 # Shape list: SHAPE[0]=layout=0 1 0,0 2 0,1 0 0,1 1 0,2 1 0:parity=1:numRow=256:count=1:id=0:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=256:pieceList={F} SHAPE[1]=layout=0 0 0,1 0 0,2 0 0,3 0 0,4 0 0:parity=-1:numRow=56:count=1:id=1:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=56:pieceList={I} SHAPE[2]=layout=0 0 0,1 0 0,2 0 0,3 0 0,3 1 0:parity=-1:numRow=248:count=1:id=2:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=248:pieceList={L} SHAPE[3]=layout=0 0 0,1 0 0,2 0 0,2 1 0,3 1 0:parity=-1:numRow=248:count=1:id=3:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=248:pieceList={N} SHAPE[4]=layout=0 0 0,0 1 0,1 0 0,1 1 0,2 0 0:parity=-1:numRow=304:count=1:id=4:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=304:pieceList={P} SHAPE[5]=layout=0 0 0,1 0 0,1 1 0,1 2 0,2 0 0:parity=-1:numRow=128:count=1:id=5:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=128:pieceList={T} SHAPE[6]=layout=0 0 0,0 1 0,1 0 0,2 0 0,2 1 0:parity=1:numRow=152:count=1:id=6:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=152:pieceList={U} SHAPE[7]=layout=0 0 0,0 1 0,0 2 0,1 0 0,2 0 0:parity=-1:numRow=128:count=1:id=7:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=128:pieceList={V} SHAPE[8]=layout=0 1 0,0 2 0,1 0 0,1 1 0,2 0 0:parity=-1:numRow=128:count=1:id=8:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=128:pieceList={W} SHAPE[9]=layout=0 1 0,1 0 0,1 1 0,1 2 0,2 1 0:parity=3:numRow=8:count=1:id=9:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=8:pieceList={X} SHAPE[10]=layout=0 0 0,1 0 0,2 0 0,2 1 0,3 0 0:parity=1:numRow=248:count=1:id=10:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=248:pieceList={Y} SHAPE[11]=layout=0 0 0,1 0 0,1 1 0,1 2 0,2 2 0:parity=-1:numRow=128:count=1:id=11:numCopies=1:numStationary=0:numMobile=1:numStationaryImages=0:numMobileImages=128:pieceList={Z} # One sided polyomino constraint: ONE_SIDE=OFF # Redundancy filter piece name: REDUNDANCY_FILTER=X # Piece rotations and translations that fit in the solution space: BOUNDED=2032 # Piece rotations and translations that don't fit in the solution space: UNBOUNDED=9128 # Are solutions guaranteed to be rotationally unique without filtering? ROTATIONALLY_UNIQUE=true # --- SOLUTION 1 --- V V V Y I I I I I T V Y Y Y Y W W T T T V X Z Z P P W W F T X X X Z P P P W F F U X U Z Z N N F F L U U U N N N L L L L # --- SOLUTION 2 --- V V V Y I I I I I T V Y Y Y Y W W T T T V X Z Z W W P P F T X X X Z W P P P F F U X U Z Z N N F F L U U U N N N L L L L # --- SOLUTION 3 --- V V V Y I I I I I W V Y Y Y Y N N N W W V X Z Z N N F W W T X X X Z F F F T T T U X U Z Z F L P P T U U U L L L L P P P ... ... # --- SOLUTION 2339 --- N N N W W Z Z U U U I T N N W W Z U Y U I T T T X W Z Z Y Y I T F X X X P P Y V I F F F X L P P Y V I F L L L L P V V V # Number of solutions found: SOLUTIONS=2339 # Number of solutions found per second: SOLUTIONS_PER_SEC=3846.50805 # Number of rotationally unique solutions found: UNIQUE=2339 # Number of rotationally unique solutions found per second: UNIQUE_PER_SEC=3846.50805 # Number of rotationally redundant solutions found but filtered out: REDUNDANT=0 # Number of backtracks due to parity constraint: PARITY_BACKTRACK_TOTAL=0 # Number of backtracks due to volume constraint: VOLUME_BACKTRACK_TOTAL=0 # Number of rows filtered due to fit constraint: FIT_FILTER_TOTAL=0 # Number of rows filtered due to parity constraint: PARITY_FILTER_TOTAL=0 # Number of rows filtered due to volume constraint: VOLUME_FILTER_TOTAL=125 # Number of times pieces were attempted to be placed: ATTEMPTS_TOTAL=15198004 # Number of times pieces fit: FITS_TOTAL=2091215 # Number of backtracks due to parity constraint when N pieces were left to be placed: PARITY_BACKTRACK[ 1]= 0 PARITY_BACKTRACK[ 2]= 0 PARITY_BACKTRACK[ 3]= 0 PARITY_BACKTRACK[ 4]= 0 PARITY_BACKTRACK[ 5]= 0 PARITY_BACKTRACK[ 6]= 0 PARITY_BACKTRACK[ 7]= 0 PARITY_BACKTRACK[ 8]= 0 PARITY_BACKTRACK[ 9]= 0 PARITY_BACKTRACK[10]= 0 PARITY_BACKTRACK[11]= 0 PARITY_BACKTRACK[12]= 0 # Number of backtracks due to volume constraint when N pieces were left to be placed: VOLUME_BACKTRACK[ 1]= 0 VOLUME_BACKTRACK[ 2]= 0 VOLUME_BACKTRACK[ 3]= 0 VOLUME_BACKTRACK[ 4]= 0 VOLUME_BACKTRACK[ 5]= 0 VOLUME_BACKTRACK[ 6]= 0 VOLUME_BACKTRACK[ 7]= 0 VOLUME_BACKTRACK[ 8]= 0 VOLUME_BACKTRACK[ 9]= 0 VOLUME_BACKTRACK[10]= 0 VOLUME_BACKTRACK[11]= 0 VOLUME_BACKTRACK[12]= 0 # Number of filters due to parity constraint when N pieces were left to be placed: PARITY_FILTER[ 1]= 0 PARITY_FILTER[ 2]= 0 PARITY_FILTER[ 3]= 0 PARITY_FILTER[ 4]= 0 PARITY_FILTER[ 5]= 0 PARITY_FILTER[ 6]= 0 PARITY_FILTER[ 7]= 0 PARITY_FILTER[ 8]= 0 PARITY_FILTER[ 9]= 0 PARITY_FILTER[10]= 0 PARITY_FILTER[11]= 0 PARITY_FILTER[12]= 0 # Number of filters due to fit constraint when N pieces were left to be placed: FIT_FILTER[ 1]= 0 FIT_FILTER[ 2]= 0 FIT_FILTER[ 3]= 0 FIT_FILTER[ 4]= 0 FIT_FILTER[ 5]= 0 FIT_FILTER[ 6]= 0 FIT_FILTER[ 7]= 0 FIT_FILTER[ 8]= 0 FIT_FILTER[ 9]= 0 FIT_FILTER[10]= 0 FIT_FILTER[11]= 0 FIT_FILTER[12]= 0 # Number of filters due to volume constraint when N pieces were left to be placed: VOLUME_FILTER[ 1]= 0 VOLUME_FILTER[ 2]= 0 VOLUME_FILTER[ 3]= 0 VOLUME_FILTER[ 4]= 0 VOLUME_FILTER[ 5]= 0 VOLUME_FILTER[ 6]= 0 VOLUME_FILTER[ 7]= 0 VOLUME_FILTER[ 8]= 0 VOLUME_FILTER[ 9]= 0 VOLUME_FILTER[10]= 0 VOLUME_FILTER[11]= 0 VOLUME_FILTER[12]= 125 # Number of placement attempts when N pieces were left to be placed: ATTEMPTS[ 1]= 301677 ATTEMPTS[ 2]= 3478035 ATTEMPTS[ 3]= 5722296 ATTEMPTS[ 4]= 3665538 ATTEMPTS[ 5]= 1284992 ATTEMPTS[ 6]= 386776 ATTEMPTS[ 7]= 200366 ATTEMPTS[ 8]= 126819 ATTEMPTS[ 9]= 28279 ATTEMPTS[10]= 3088 ATTEMPTS[11]= 131 ATTEMPTS[12]= 7 # Number of fits when N pieces were left to be placed: FITS[ 1]= 2339 FITS[ 2]= 302256 FITS[ 3]= 760374 FITS[ 4]= 617667 FITS[ 5]= 272072 FITS[ 6]= 82406 FITS[ 7]= 26950 FITS[ 8]= 17275 FITS[ 9]= 7994 FITS[10]= 1744 FITS[11]= 131 FITS[12]= 7 NAME : TOTAL TIME : PERCENTAGE : NUM EVENTS : AVG TIME _______________________________________________________________________________________________________________________________ all : 0.609732 : * : 1: 0.610 parsing : 0.001081 : 0.177% : 1: 0.001 puzzle-init : 0.000846 : 0.139% : 1: 0.001 solve : 0.606998 : 99.552% : 1: 0.607 solve-init : 0.021409 : 3.527% : 1: 0.021 genImageLists : 0.019115 : 89.285% : 1: 0.019 dlxLoad : 0.001788 : 8.352% : 1: 0.002 solve-algo : 0.584656 : 96.319% : 1: 0.585 solve-filter : 0.004629 : 0.792% : 1: 0.005 initTile : 0.003440 : 0.588% : 7: 0.000 solve-cleanup : 0.000874 : 0.144% : 1: 0.001 puzzle-cleanup : 0.000763 : 0.125% : 1: 0.001 _______________________________________________________________________________ BUGS There are no known bugs. Please send bug reports to my email address given below. _______________________________________________________________________________ AUTHOR: Matthew T Busche EMAIL: mtbusche AT gmail.com ADDRESS: 8813 W Iliff Ave Lakewood, CO 80227 USA