{"id":26,"date":"2011-03-23T19:05:24","date_gmt":"2011-03-23T19:05:24","guid":{"rendered":"https:\/\/www.mattbusche.org\/blog\/?p=26"},"modified":"2023-10-25T02:21:48","modified_gmt":"2023-10-25T02:21:48","slug":"polycube","status":"publish","type":"post","link":"https:\/\/www.mattbusche.org\/blog\/article\/polycube\/","title":{"rendered":"Solving Polyomino and Polycube Puzzles<span class=\"h1sub\"> Algorithms, Software, and Solutions<\/span>"},"content":{"rendered":"<p><script type=\"text\/javascript\" src=\"\/js\/loadCSS.js\"><\/script><br \/>\n<script type=\"text\/javascript\">\n   loadCSS(\"\/css\/wordpress\/article\/polycube.css\");\n<\/script><br \/>\n<script type=\"text\/javascript\" src=\"\/js\/wordpress\/article\/polycube.js\"><\/script><br \/>\n<script type=\"text\/javascript\" src=\"\/js\/wordpress\/article\/PolyPlayer.js\"><\/script><\/p>\n<p><img decoding=\"async\" src=\"\/images\/polycube\/tetriscube.png\" class=\"graphic\"\nalt=\"Povray image of a solution to the Tetris Cube.\"\/><\/p>\n<div class=\"righted\" style=\"font-size:8pt;\">Image by Matt Busche<\/div>\n<p>I&#8217;ve implemented a set of backtrack algorithms to find solutions to various<br \/>\npolyomino and polycube puzzles (2-D and 3-D puzzles where you have to fit<br \/>\npieces composed of little squares or cubes into a confined space).  Examples<br \/>\nof such puzzles include the Tetris Cube, the Bedlam Cube, the Soma Cube, and<br \/>\nPentominoes.  My approach to the problem is perhaps unusual in that I&#8217;ve<br \/>\nimplemented many different algorithmic techniques simultaneously into a single<br \/>\npuzzle solving software application.  I&#8217;ve found that the best algorithm to<br \/>\nuse for a problem can depend on the size, and dimensionality of the puzzle.<br \/>\nTo take advantage of this, when the number of remaining pieces reaches<br \/>\nconfigurable transition thresholds my software can turn off one algorithm and<br \/>\nturn on another.  Three different algorithms are implemented: de Bruijn&#8217;s<br \/>\nalgorithm, Knuth&#8217;s DLX, and my own algorithm which I call most-constrained-hole<br \/>\n(MCH).  DLX is most commonly used with an ordering heuristic that picks the<br \/>\nhole or piece with fewest fit choices; but other simple ordering heuristics are shown<br \/>\nto improve performance for some puzzles.<\/p>\n<p>In addition to these three core algorithms, a set of constraints are woven<br \/>\ninto the algorithms giving great performance benefits.  These include<br \/>\nconstraints on the volumes of isolated subspaces, parity (or coloring)<br \/>\nconstraints, fit constraints, and constraints to take advantage of rotational<br \/>\nsymmetries.<\/p>\n<p>In this (rather long) blog entry I present the algorithms and techniques I&#8217;ve<br \/>\nimplemented and share my insights into where each works well, and where they<br \/>\ndon&#8217;t.  You can also download my software source, an executable version of the<br \/>\nsolver, and the solutions to various well known puzzles.<\/p>\n<p><!--more--><\/p>\n<h2><span class=\"h2\">Contents<\/span><\/h2>\n<div class=\"outline\">\n<div class=\"i2\"><span class=\"h2\"><a href=\"#motivation\">Motivation<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#algorithm\">Backtrack Algorithms<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#complexity\">Puzzle Complexity<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#bruijn\">De Bruijn&#8217;s Algorithm<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#dlx\">Dancing Links (DLX) Algorithm<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#dlxdescription\">DLX Description<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#orderingheuristics\">Ordering Heuristics<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#mch\">Most Constrained Hole (MCH) Algorithm<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#combine\">Combining the Algorithms<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#softopt\">Software Optimizations<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#bitfields\">Bit Fields<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#earlyexit\">Early MCH Fit Count Exit<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#permutation\">Fast Permutation Algorithm<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#constraints\">Constraints<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#backtrack\">Backtrack Triggers<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#paritybacktrack\">Parity Constraint Violations<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#volumebacktrack\">Volume Constraint Violations<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#imagefilter\">Image Filters<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#boundsfilter\">Puzzle Bounds Constraint Violations<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#redundancyfilter\">Rotational Redundancy Constraint Violations<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#parityfilter\">Parity Constraint Violations<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#volumefilter\">Volume Constraint Violations<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#fitfilter\">Fit Constraint Violations<\/a><\/span><\/div>\n<div class=\"i4\"><span class=\"h4\"><a href=\"#filterperformance\">Image Filter Performance (or lack thereof)<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#performance\">Performance Comparisons<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#performanceP\">Test Case P:  Pentominoes in a 10&#215;6 Box<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#performanceOP\">Test Case OP:  One-sided Pentominoes in a 30&#215;3 Box<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#performanceTC\">Test Case TC:  Tetris Cube<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#performanceHP\">Test Case HP:  Hexominoes in a 15&#215;14 Parallelogram<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#performanceHBD\">Test Case HBD:  Hexominoes Box-in-a-Diamond<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#software\">Software<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#softwareDownload\">Download<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#softwareRun\">Running the Software<\/a><\/span><\/div>\n<div class=\"i3\"><span class=\"h3\"><a href=\"#softwareFeature\">Planned Features<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#solutions\">Solutions<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#conclusions\">Conclusions<\/a><\/span><\/div>\n<div class=\"i2\"><span class=\"h2\"><a href=\"#references\">References<\/a><\/span><\/div>\n<\/div>\n<div style=\"width:900px;\">\n<a name=\"motivation\"><\/a><\/p>\n<h2><span class=\"h2\">Motivation<\/span><\/h2>\n<p>My original impetus for writing this software was an annoyingly difficult<br \/>\nlittle puzzle called the Tetris Cube.  The Tetris Cube consists of the twelve<br \/>\noddly-shaped plastic pieces shown in Figure&nbsp;1 which you have to try to<br \/>\nfit into a cube-shaped box.  Each piece has a shape you could make yourself by<br \/>\nsticking together little cubes of fixed size.  You would need 64 cubes to make<br \/>\nthem all and accordingly, the puzzle box measures 4x4x4 &mdash; just big<br \/>\nenough to hold them all.  (This is an example of a <i>polycube<\/i> puzzle: a<br \/>\n3-D puzzle where all the pieces are formed from little cubes.  We&#8217;ll also be<br \/>\nlooking at <i>polyomino<\/i> puzzles:  2-D puzzles where all the pieces are<br \/>\nformed from little squares.)<\/p>\n<p><a name=\"figure1\"><img loading=\"lazy\" decoding=\"async\" src=\"\/images\/polycube\/tetris-cube-pieces.png\" width=\"900\" height=\"558\"\nalt=\"POV-Ray image of the 12 pieces of the Tetris Cube labeled A through L.\"\/><\/a><\/p>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;1.  POV-Ray image of the 12 pieces of the Tetris<br \/>\nCube puzzle.<\/span>  Each piece is given a single character label used by the<br \/>\nsoftware to output solutions.\n<\/div>\n<p>The appeal of the Tetris Cube to me is three-fold.  First, it&#8217;s intriguing<br \/>\n(and surprising to most folks) that a puzzle with only twelve pieces could be<br \/>\nso wicked hard.  I had spent much time in my youth looking for solutions to<br \/>\nthe far simpler (but still quite challenging) two-dimensional Pentominoes<br \/>\npuzzle, so when I first saw the Tetris Cube in a gaming store about three<br \/>\nyears ago, I knew that with the introduction of the third dimension that the<br \/>\nTetris Cube was an abomination straight from Hell.  I had to buy it.  Since<br \/>\nthen I&#8217;ve spent many an hour trying to solve it, but I&#8217;ve never found<br \/>\neven one of its nearly 10,000 solutions manually.<\/p>\n<p>Second, I enjoy the challenge of visualizing ways of fitting the remaining<br \/>\npieces into the spaces I have left, and enjoy the logic you can apply to<br \/>\nidentify doomed partial assemblies.<\/p>\n<p>Third, I think working any such puzzle provides a certain amount of<br \/>\ntactile pleasure.  I should really buy the wooden version of this thing.<\/p>\n<p>But alas, I think that short of having an Einstein-like parietal lobe<br \/>\nmutation, you will need both persistence and a fair amount of luck to find<br \/>\neven one solution.  If I ever found a solution, I think I&#8217;d feel not so much<br \/>\nproud as lucky; or maybe just embarrassed that I wasted all that time looking<br \/>\nfor the solution.  In this sense, I think perhaps the puzzle is flawed.  But<br \/>\nfor those of you up for a serious challenge, you should really go buy the<br \/>\ncursed thing!  But do yourself a favor and make a sketch of the initial<br \/>\nsolution and keep it in the box so you can put it away as needed.<\/p>\n<p>Having some modest programming skill, I decided to kick the proverbial butt<br \/>\nof this vexing puzzle back into the fiery chasm from whence it came.  My<br \/>\ninitial program, written in January 2010, made use of only my own algorithmic<br \/>\nideas.  But during my debugging, I came across<br \/>\n<a href=\"http:\/\/scottkurowski.com\/tetriscube\/\">Scott Kurowski&#8217;s web page<\/a><br \/>\ndescribing the software he wrote to solve this very same puzzle.  I really<br \/>\nenjoyed the page and it motivated me to share my own puzzle solving algorithm<br \/>\nand also to read up on the techniques others have devised for solving these<br \/>\ntypes of puzzles.  In my zeal to make the software run as fast as possible,<br \/>\nover the next couple of weeks I incorporated several of these techniques as<br \/>\nwell as a few more of my own ideas.  Then I stumbled upon Donald Knuth&#8217;s Dancing<br \/>\nLinks (DLX) algorithm which I thought simply beautiful.  But DLX caused me two<br \/>\nproblems:  first it used a radically different data model and would not be at<br \/>\nall easy to add to my existing software; second it was so elegant, I<br \/>\nquestioned whether there was any real value in the continued pursuit of this<br \/>\npet project.<\/p>\n<p>Still I wasn&#8217;t sure how DLX would compare to and possibly work together<br \/>\nwith the other approaches I had implemented.  The following November,<br \/>\ncuriosity finally got the better of me and I began to lie awake at night<br \/>\nthinking about how to to integrate DLX into my polycube solver software<br \/>\napplication.<\/p>\n<p><a name=\"algorithm\"><\/a><\/p>\n<h2><span class=\"h2\">Backtrack Algorithms<\/span><\/h2>\n<p>The popular algorithms used to solve these types of problems are all<br \/>\nrecursive backtracking algorithms.  With one algorithm that falls in this<br \/>\ncategory you sequentially consider all the ways of placing the first piece;<br \/>\nfor each successful placement of that piece, you examine all the ways of<br \/>\nplacing the second piece.  You continue placing pieces in this way until you<br \/>\nfind yourself in a situation where the next piece simply won&#8217;t fit in the box,<br \/>\nat which point you back up one step (backtrack) and try the next possible<br \/>\nplacement of the previously placed piece.  Following this algorithm to its<br \/>\ncompletion will examine all possible permutations of piece placements<br \/>\nincluding those placements that happen to be solutions to the puzzle.  This<br \/>\napproach typically performs horribly.  Another similar approach is to instead<br \/>\nconsider all the ways you can fill a single target open space (hole) in the<br \/>\npuzzle; for each possible piece placement that fills the hole, pick another<br \/>\nhole and consider all the ways to fill it; etc.  This approach can also behave<br \/>\nquite badly if you choose your holes willy-nilly, but if you make <i>good<\/i><br \/>\nchoices about which hole to fill at each step, it performs much better.  But<br \/>\nin general you can mix these two basic approaches so that at each step of your<br \/>\nalgorithm you can either consider all ways to fill a particular hole, or<br \/>\nconsider all ways to place a particular piece.  Donald Knuth gives a nice<br \/>\nabstraction of this general approach that he dubbed Algorithm X.<\/p>\n<p><a name=\"complexity\"><\/a><\/p>\n<h3><span class=\"h3\">Puzzle Complexity<\/span><\/h3>\n<p>To appreciate the true complexity of these types of problems it is perhaps<br \/>\nuseful to examine the Tetris Cube more closely.  First note that most of the<br \/>\npieces have 24 different ways you can orient (rotate) them.  (To see where the<br \/>\nnumber 24 comes from, hold a piece in your hand and see that you have 6<br \/>\ndifferent choices for which side faces up.  After picking a side to face up,<br \/>\nyou still have 4 more choices for how to spin the piece about the vertical<br \/>\naxis while leaving the same side up.)  Two of the pieces, however, have<br \/>\nsymmetries that reduce their number of uniquely shaped orientations to just<br \/>\n12.  For each orientation of a piece, there can be many ways to translate<br \/>\nthe piece in that orientation within the confines of the box.  I call a<br \/>\nparticular translation of a particular orientation of a particular piece an<br \/>\n<i>image<\/i>.<\/p>\n<p>If we stick with the algorithmic approach of recursively filling empty<br \/>\nholes to look for solutions, then we&#8217;ll start by picking just one of the 64<br \/>\nholes in the puzzle cube (call the hole Z<sub>1<\/sub>); and then one-by-one<br \/>\ntry to fit each of the pieces in that hole.  For each piece, all unique<br \/>\norientations are examined; and for each orientation, an attempt is made to<br \/>\nplace each of the piece&#8217;s constituent cubes in Z<sub>1<\/sub>.  The size<br \/>\nof a piece multiplied by its number of unique orientations I loosely call the<br \/>\ncomplexity of a piece, which gives the total number of images of a piece that<br \/>\ncan possibly fill a hole.  If, for example, a piece has 6 cubes and has 24<br \/>\nunique orientations, then 144 different images of that piece could be used to<br \/>\nfill any particular hole.  The complexity of the twelve Tetris Cube pieces are<br \/>\nshown in Table&nbsp;1.  Each time a piece is successfully fitted into<br \/>\nZ<sub>1<\/sub>, our processing of Z<sub>1<\/sub> is temporarily interrupted<br \/>\nwhile the whole algorithm is recursively repeated with the remaining pieces on<br \/>\nsome new target hole, Z<sub>2<\/sub>.  And so on, and so on.  Each time we<br \/>\nsuccessfully place the last piece, we&#8217;ve found a solution.<\/p>\n<table align=\"center\" class=\"data\">\n<caption>Table 1.  Piece Complexity<\/caption>\n<tr>\n<th>Piece Name<\/th>\n<th>Size<\/th>\n<th>Unique Orientations<\/th>\n<th>Complexity<\/th>\n<\/tr>\n<tr style=\"background-color:#8080FF\">\n<td>A<\/td>\n<td>6<\/td>\n<td>24<\/td>\n<td>144<\/td>\n<\/tr>\n<tr style=\"background-color:#8080FF\">\n<td>B<\/td>\n<td>6<\/td>\n<td>24<\/td>\n<td>144<\/td>\n<\/tr>\n<tr style=\"background-color:#8080FF\">\n<td>C<\/td>\n<td>5<\/td>\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>\n<tr style=\"background-color:#8080FF\">\n<td>D<\/td>\n<td>5<\/td>\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>\n<tr style=\"background-color:red\">\n<td>E<\/td>\n<td>6<\/td>\n<td>24<\/td>\n<td>144<\/td>\n<\/tr>\n<tr style=\"background-color:red\">\n<td>F<\/td>\n<td>5<\/td>\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>\n<tr style=\"background-color:red\">\n<td>G<\/td>\n<td>5<\/td>\n<td>12<\/td>\n<td> 60<\/td>\n<\/tr>\n<tr style=\"background-color:red\">\n<td>H<\/td>\n<td>5<\/td>\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>\n<tr style=\"background-color:yellow\">\n<td>I<\/td>\n<td>5<\/td>\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>\n<tr style=\"background-color:yellow\">\n<td>J<\/td>\n<td>5<\/td>\n<td>12<\/td>\n<td> 60<\/td>\n<\/tr>\n<tr style=\"background-color:yellow\">\n<td>K<\/td>\n<td>5<\/td>\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>\n<tr style=\"background-color:yellow\">\n<td>L<\/td>\n<td>6<\/td>\n<td>24<\/td>\n<td>144<\/td>\n<\/tr>\n<\/table>\n<p>The number of steps in such an algorithm cannot be determined without<br \/>\nactually running it since the number of successful fits at each step is<br \/>\nimpossible to predict and varies wildly with which hole you choose to fill.<br \/>\nIt is useful however (or at least mildly entertaining) to consider<br \/>\nhow many steps you&#8217;d have if you didn&#8217;t backup when a piece didn&#8217;t fit, but<br \/>\ninstead let pieces hang outside the box, or even let two pieces happily occupy<br \/>\nthe same space (perhaps slipping one piece into Buckaroo Banzai&#8217;s eighth<br \/>\ndimension) and blindly forging ahead until all twelve pieces were positioned.<br \/>\nIn this case, the total number of ways to place pieces is easily written down.<br \/>\nThere are 12 &#215; 11 &#215; 10 . . . &#215; 1 = 12!  possible orderings of<br \/>\nthe pieces.  And for each such ordering, each piece can be placed a number of<br \/>\ntimes given by its complexity.  So the total number of distinct permutations<br \/>\nof pieces that differ either in the order the pieces are placed, or in the<br \/>\ntranslation or orientation of those pieces is:<\/p>\n<div class=\"equation\">\n12! &#215; 144<sup>4<\/sup> &#215; 120<sup>6<\/sup> &#215; 60<sup>2<\/sup> = 2,213,996,395,638,416,883,056,640,000,000,000\n<\/div>\n<p>That&#8217;s 2.2 decillion.  The total number of algorithm steps would be a<br \/>\nmore than double that (since each piece placed also has to be removed).<br \/>\nBut this is just silliness:  any backtracking algorithm worth its salt<br \/>\n(and none of them are very salty) will reduce the number of steps to<br \/>\nwell below a quadrillion, and a good one can get the number of steps<br \/>\ndown to the tens of millions.  I now examine some specific algorithms<br \/>\nand explain how they work.<\/p>\n<p><a name=\"bruijn\"><\/a><\/p>\n<h3><span class=\"h3\">De Bruijn&#8217;s Algorithm<\/span><\/h3>\n<p>The first algorithm examined was first formulated independently by John<br \/>\nG Fletcher and N.G. de Bruijn.  I first stumbled upon the algorithm when<br \/>\nreading <a href=\"http:\/\/scottkurowski.com\/tetriscube\/\">Scott Kurowski&#8217;s<br \/>\nsource code for solving the Tetris Cube<\/a>.  To read Fletcher&#8217;s work you&#8217;ll<br \/>\neither need to find a library with old copies of the Communications of the ACM<br \/>\nor drop $200.00 for online access.  (I&#8217;ve yet to do either.)  De Bruijn&#8217;s work<br \/>\ncan be viewed online for free, but you&#8217;ll need to learn Dutch to read it.<br \/>\n(It&#8217;s on my to-do list.)  Despite my ignorance of the two original publications<br \/>\non the algorithm, I&#8217;ll take a shot at explaining it here.  With no intended<br \/>\nsleight to Fletcher, from here on, I simply refer to the algorithm as de<br \/>\nBruijn&#8217;s algorithm.  (I feel slightly less foolish calling it de Bruijn&#8217;s<br \/>\nalgorithm since I have at least examined and understood the diagrams in his<br \/>\npaper.)<\/p>\n<p>De Bruijn&#8217;s algorithm takes the tack of picking holes to fill.  Now<br \/>\nI previously said that when filling a hole, that for each orientation of each<br \/>\npiece, an attempt must be made to place each of the piece&#8217;s constituent cubes<br \/>\nin that hole; but with de Bruijn&#8217;s technique, only one of the cubes must be<br \/>\nattempted.  This saves a lot of piece fitting attempts.  To understand how<br \/>\nthis works, first assume the puzzle is partially filled with pieces.  De<br \/>\nBruijn&#8217;s algorithm requires you pick a particular hole to fill next.  A simple<br \/>\nset of nested for loops will find the correct hole.  The code could look like<br \/>\nthis:<\/p>\n<pre>\r\n        GridPoint* Puzzle::getNextBruijnHole()\r\n        {\r\n            for(int z = 0; z &lt; zDim; ++z)\r\n                for(int y = 0; y &lt; yDim; ++y)\r\n                    for(int x = 0; x &lt; xDim; ++x)\r\n                        if(grid[x][y][z]-&gt;occupied == false)\r\n                            return grid[x][y][z];\r\n            return NULL;\r\n        }\r\n<\/pre>\n<p>This search order is also shown visually on the left hand side of Figure&nbsp;2.<\/p>\n<p><a name=\"figure2\"><img decoding=\"async\" src=\"\/images\/polycube\/tiling.png\" class=\"graphic\"\nalt=\"3-part diagram showing a) the search pattern used to find the tiling hole, b) an arbitrary piece with its root tiling node highlighted, and c) that piece fitting in the tiling hole.\"\/><\/a><\/p>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;2.  Diagram showing de Bruijn&#8217;s tiling technique.<\/span><br \/>\nThe puzzle is scanned in x, y, z order until a hole is found.  Only the root<br \/>\nnode of an oriented piece must be tested for fit.  No other cube in the piece<br \/>\nwhile held in that orientation can possibly fit at the target hole.\n<\/div>\n<p>Because of the search order there can be no holes in the puzzle with a lesser<br \/>\nz value than the target hole.  Similarly, there can be no holes with the same<br \/>\nz value as the target hole having a lesser y value.  And finally, there can be<br \/>\nno hole with the same y and z values as the target hole having a lesser x<br \/>\nvalue.<\/p>\n<p>Now consider a particular orientation of an arbitrary piece like the one<br \/>\nshown in the center of Figure&nbsp;2.  Because there can be no holes with a<br \/>\nlesser z value than the target hole, it would be pointless to attempt to place<br \/>\neither of its two top cubes in the hole.  That would only force the lower<br \/>\ncubes of the piece into necessarily occupied<br \/>\n<span class=\"code\">GridPoint<\/span>s of the puzzle.  So only those cubes at<br \/>\nthe bottom of the piece could possibly fit in the target hole.  But of those<br \/>\nthree bottom cubes, the one with the greater y value (in the foreground of the<br \/>\ngraphic) can&#8217;t possibly fit in the hole because it would force the other two<br \/>\nbottom tier pieces into occupied puzzle <span class=\"code\">GridPoint<\/span>s<br \/>\nat the same height as the hole but with lesser y value.  Applying the same<br \/>\nargument along the x axis leads to the conclusion that for any orientation of<br \/>\na puzzle piece, only the single cube with minimum coordinate values in z, y, x<br \/>\npriority order (which I call the root tiling node of the piece) can possibly<br \/>\nfit the hole.  This cube is highlighted pink in Figure&nbsp;2.<\/p>\n<p>So with de Bruijn&#8217;s algorithm, a piece with 6 cubes and 24 orientations<br \/>\nwould only require 24 fit attempts instead of 144 at a given target hole.<br \/>\nThis allows the algorithm to fly through piece permutations in a hurry.<\/p>\n<p><a name=\"figure3\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar pentominoColor = {\n    F:'#700',\n    I:'#C00',\n    L:'#070',\n    N:'#0C0',\n    P:'#007',\n    T:'#00C',\n    U:'#7CC',\n    V:'#C0C',\n    W:'#FA0',\n    X:'#F77',\n    Y:'yellow',\n    Z:'#6000AC',\n    B:'#00ACFF',\n    G:'#7070C0',\n    J:'#B06000',\n    M:'#B0B000',\n    Q:'#B0FF00',\n    S:'#FFBCFF'\n};\n\npentominoColor['.'] = \"#CCC\";\npentominoColor['*'] = \"#FFF\";\npentominoColor['@'] = \"#000\";\n\nvar pentominoPieces = '* * * * * * I * * * * * * * * * * * * * * *\\n' +\n                      '* * * * * * I * L * * * N * * * * * * * * *\\n' +\n                      '* * * F F * I * L * * * N * P P * T T T * *\\n' +\n                      '* * F F * * I * L * * N N * P P * * T * * *\\n' +\n                      '* * * F * * I * L L * N * * P * * * T * * *\\n' +\n                      '* * * *:F * * *:I * *:L:2 * * *:N:2 * * *:P:2 * * * *:T * * *\\n' +\n                      '* * * * * * * * * * * * * * * * * Y * * * *\\n' +\n                      '* * * * V * * * W * * * * X * * Y Y * Z Z *\\n' +\n                      'U * U * V * * * W W * * X X X * * Y * * Z *\\n' +\n                      'U U U * V V V * * W W * * X * * * Y * * Z Z\\n' +\n                      '* *:U * * * *:V * * * *:W * * * *:X * * *:Y:2 * * * *:Z *';\n\ndocument.write(puzzleToHtmlTable(pentominoPieces, pentominoColor, false, {}, 'big'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"centered puzzle\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\nvar pentominoSolution = 'V V V W W N N N T I\\n' +\n                        'V Y W W N N T T T I\\n' +\n                        'V Y W X L L L L T I\\n' +\n                        'Y Y X X X Z Z L F I\\n' +\n                        'U Y U X P P Z F F I\\n' +\n                        'U U U P P P Z Z F F';\n\ndocument.write(puzzleToHtmlTable(pentominoSolution, pentominoColor, false, {}, 'big'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;3.  The twelve pentomino pieces with their single<br \/>\ncharacter names and a solution to the 10&#215;6 pentomino puzzle.<\/span>\n<\/div>\n<p>De Bruijn&#8217;s paper focused on the 10&#215;6 pentomino puzzle, perhaps the most<br \/>\nfamous of all polyomino and polycube puzzles.  The puzzle pieces in this<br \/>\nproblem consist of all the ways you can possibly stick 5 squares together to<br \/>\nform rotationally unique shapes.  There are 12 such pieces in all and each<br \/>\nis given a standard single character name.  Figure&nbsp;3 shows the twelve<br \/>\npieces with their names as well as one of the 2339 ways you can fit these<br \/>\npieces into a 10&#215;6 box.  To be accurate, de Bruijn only used the algorithmic<br \/>\nsteps described above to place the last 11 pieces in this puzzle.  He forced<br \/>\nthe X piece to be placed first in each of seven possible positions in the<br \/>\nlower left quadrant of the box.  This was done to eliminate rotationally<br \/>\nredundant solutions from the search, and significantly sped up processing.<br \/>\nBut where possible I&#8217;d like to avoid optimization techniques that require<br \/>\nprocessing by University professors.  So when I speak of the de Bruijn<br \/>\nalgorithm, I do not include this special case processing.  This restriction<br \/>\nsignificantly weakens the algorithm.  (I found it to take ten times longer to<br \/>\nfind all solutions to the 10&#215;6 pentomino puzzle without this trick.)  As I<br \/>\nexplain later, I&#8217;ve implemented an image filter that can constrain a piece to<br \/>\neliminate rotationally redundant solutions from the search.  Applying this<br \/>\nfilter to the 10&#215;6 pentomino puzzle algorithmically reproduces de Bruijn&#8217;s<br \/>\nconstraint on the X piece.<\/p>\n<p><a name=\"figure4\"><\/a><br \/>\n<script type=\"text\/javascript\">\n    var debruijnTrouble = new PolyPlayer({\n            file       : '\/projects\/polycube\/debruijnTrouble.txt',\n            interval   : 800,\n            counterFmt : 'Step {}.',\n            color      : pentominoColor\n        });\n<\/script><\/p>\n<div class=\"caption\" style=\"margin-top:10px;\">\n<span class=\"heading\">Figure&nbsp;4.  The de Bruijn algorithm stumbling<br \/>\nover a hole that can&#8217;t be filled.<\/span>  The troublesome hole is created in<br \/>\nstep 2, but is not cleared until step 195.\n<\/div>\n<p>In Figure&nbsp;4, I&#8217;ve captured an excerpt of de Bruijn&#8217;s algorithm working on<br \/>\nthe 10&#215;6 pentomino puzzle at a point where it&#8217;s behaving particularly badly.<br \/>\nIt reveals an interesting weakness of the algorithm:  it can be slow to<br \/>\nrecognize a position in the puzzle that&#8217;s clearly impossible to fill.  The<br \/>\nalgorithm doesn&#8217;t recognize this problem until it selects the troublesome hole<br \/>\nas a fill target, but even then it won&#8217;t back up all the way to the point<br \/>\nwhere the hole is freed from its confinement:  it only backs up one step.<br \/>\nSo depending on how far away the isolated hole is in the hole selection<br \/>\nsequence at the time the hole appeared, it may get stuck trying to fill<br \/>\nthe hole many many times.  Because pentominoes pieces are all fairly small, and<br \/>\nbecause the algorithm uses a strict packing order from bottom to top and from<br \/>\nleft to right, such troublesome holes can never be that far away from the<br \/>\ncurrent fill target and are thus usually discovered fairly quickly.  The<br \/>\nexample I&#8217;ve given may be among the most troublesome to the algorithm, but<br \/>\nthings can get worse if you are working with larger pieces, or if you are<br \/>\nworking in 3 dimensions instead of 2.  In either case, unfillable holes can<br \/>\nappear further down the hole selection sequence and the algorithm can stumble<br \/>\nover them many more times before the piece that created the problem is finally<br \/>\nremoved.<\/p>\n<p>The next algorithm examined does not suffer from this weakness.<\/p>\n<p><a name=\"dlx\"><\/a><\/p>\n<h3><span class=\"h3\">Dancing Links (DLX) Algorithm<\/span><\/h3>\n<p>Dancing Links (DLX) is Donald Knuth&#8217;s algorithm for solving these types of<br \/>\npuzzles.  The DLX data model provides a view of each remaining hole and<br \/>\neach remaining piece and can pick either a hole to fill or a piece to place<br \/>\ndepending on which (among them all) is deemed most advantageous.<\/p>\n<p><a name=\"dlxdescription\"><\/a><\/p>\n<h4><span class=\"h4\">DLX Description<\/span><\/h4>\n<p><a href=\"http:\/\/arxiv.org\/abs\/cs\/0011047\">Knuth&#8217;s own paper on DLX<\/a><br \/>\nis quite easy to understand, but I&#8217;ll attempt<br \/>\nto summarize the algorithm here.  Create a matrix that has one column for each<br \/>\nhole in the puzzle and one column for each puzzle piece.  So for the case of<br \/>\nthe Tetris Cube the matrix will have 64 hole columns + 12 piece columns = 76<br \/>\ncolumns in all.  We can label the columns for the holes 1 through 64, and the<br \/>\ncolumns for the pieces A through L.  The matrix has one row for each unique<br \/>\nimage.  (Only images that fit wholly inside the puzzle box are included.)  If<br \/>\nyou look at one row that represents, say, a particular image of piece B, it<br \/>\nwill have a 1 in column B and a 1 in each of the columns corresponding to the<br \/>\nholes it fills.  All other columns for that row will have a 0.  (Those are the<br \/>\nonly numbers that ever appear in the matrix:  ones and zeros.)  Now, if you<br \/>\nselect a subset of rows that correspond to piece placements that actually<br \/>\nsolve the puzzle, you&#8217;ll notice something interesting:  the twelve selected<br \/>\nrows together will have a single 1 in every column.  And so the problem of<br \/>\nsolving the puzzle is abstracted to the problem of finding a set of rows that<br \/>\ncover (with a 1) all the columns in the matrix.  This is the exact cover<br \/>\nproblem:  finding a set of rows that together have exactly one 1 in every<br \/>\ncolumn.  With Knuth&#8217;s abstraction there is no distinction between filling a<br \/>\nparticular hole, or placing a particular piece; and that is truly<br \/>\nbeautiful.<\/p>\n<p>In each iteration of the algorithm, DLX first picks a column to process.<br \/>\nThis decision is rather important and I discuss it at length below.  Once a<br \/>\ncolumn is selected, DLX will in turn place each image having a 1 in that<br \/>\ncolumn.  For each such placement, DLX reduces the matrix removing every column<br \/>\ncovered by the image just placed, and removing every row for every image that<br \/>\nconflicts with the image just placed.  In other words, after this matrix<br \/>\nreduction, the only rows that remain are for those images that still fit in<br \/>\nthe puzzle, and the only columns that remain are for those holes that are<br \/>\nstill open and for those pieces that have yet to be placed.  Knuth uses some<br \/>\nnifty linked list constructions to perform this manipulation, which you<br \/>\ncan read about in his paper if interested.<\/p>\n<p>DLX maintains the total number of ones in each column as state information.<br \/>\nIf the number of ones remaining in any column hits zero, then the puzzle is<br \/>\nunsolvable with the current piece configuration and so the algorithm<br \/>\nbacktracks.  The situation in Figure&nbsp;3 that gave the de Bruijn algorithm<br \/>\nso much trouble gives DLX no trouble at all:  it immediately recognizes that<br \/>\nthe matrix column corresponding to the hole that can&#8217;t be filled has no rows<br \/>\nwith a one and backtracks, removing the piece that isolated the hole<br \/>\nimmediately after it was placed.<\/p>\n<p>Some benefits of DLX are:<\/p>\n<ol>\n<li>the elimination of all processing associated with &#8220;checking&#8221; to see if a<br \/>\nparticular image fits (which is where the de Bruijn algorithm spends most of<br \/>\nits time);<\/li>\n<li>tracking of the number of fit options for each hole and piece (which is<br \/>\nused to trigger backtracks and can also be used to make good decisions about<br \/>\nwhich hole to fill or piece to place next as discussed below);<\/li>\n<li>radically reducing the processing complexity of sub-branches of the new<br \/>\npuzzle configuration; and<\/li>\n<li>a data model that is well suited to other types of puzzle processing.  (See<br \/>\nimage filters below.)\n<\/ol>\n<p><a name=\"orderingheuristics\"><\/a><\/p>\n<h4><span class=\"h4\">Ordering Heuristics<\/span><\/h4>\n<p>As noted above, the first step in each iteration of the algorithm is<br \/>\nto pick a column to process.  If the column selected is a hole column, then<br \/>\nthe algorithm will one-by-one place all images that fill that hole.  If the<br \/>\ncolumn selected is a piece column, then the algorithm will one-by-one place<br \/>\nall the images of that piece that fit anywhere in the puzzle.  There are any<br \/>\nnumber of ways to determine this column selection order, which Knuth refers to<br \/>\nas <i>ordering heuristics<\/i>.  Knuth found that the minimum fit heuristic<br \/>\n(simply picking the column that has the fewest number of ones) does well.<br \/>\nUsing this selection criteria, DLX will always pick the more constrained of<br \/>\n<i>either<\/i> the hole that&#8217;s hardest to fill <i>or<\/i> the piece that&#8217;s<br \/>\nhardest to place.  By reducing the number of choices that have to be explored<br \/>\nat each algorithmic step, the total number of steps to execute the entire<br \/>\nalgorithm is greatly reduced.  In the case of the Tetris Cube with one piece<br \/>\nrotationally constrained (to eliminate rotationally redundant solutions), the<br \/>\nde Bruijn algorithm places pieces in the box almost 8 billion times, whereas<br \/>\nDLX running with the min-fit heuristic places pieces only 68 million times:  a<br \/>\nreduction in the number of algorithmic steps by two orders of magnitude.<br \/>\n(Remember though that each DLX step requires much more processing and DLX was<br \/>\nactually only twice as fast as de Bruijn for this problem.)<\/p>\n<p>Knuth stated in the conclusions of his paper, &#8220;On large cases [DLX] appears<br \/>\nto run even faster than those special-purpose algorithms, because of its<br \/>\n[min-fit] ordering heuristic.&#8221;  But I don&#8217;t think things are quite this<br \/>\nsimple.  I have found that for larger puzzles, the min-fit heuristic is<br \/>\noften only beneficial for placing the last N pieces of the puzzle where the<br \/>\nnumber N depends upon both the complexity of the pieces and upon the<br \/>\ngeometries of the puzzle.  I also believe that using the min-fit heuristic for<br \/>\nmore than N pieces can actually negatively impact performance relative to<br \/>\nother simpler ordering heuristics.<\/p>\n<p><a name=\"figure5\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar hexomino = '* * * * * * * * * * * A * * * * * * * * * * * * * * * * * * * * * * * * * * *\\n' +\n               '* * * * * * * * * * * A * B B * C * * D * * * E * * F * * * * * * * * * * * *\\n' +\n               '* * * * * * * * * * * A * B * * C C * D * * E E * * F * * * * * * * * * * * *\\n' +\n               '* * * * * * * * * * * A * B * * C * * D D * E * * F F * * * * * * * * * * * *\\n' +\n               '* * * * * * * * * * * A * B * * C * * D * * E * * F * * * * * * * * * * * * *\\n' +\n               '* * * * * * * * * * * A * B * * C * * D * * E * * F * * * * * * * * * * * * *\\n' +\n               '* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\\n' +\n               '* G G * H H * I I * J * * K * * * L * M M M * N * * * O * * * P * * * Q * * *\\n' +\n               '* G G * H * * I * * J J * K K * L L * M * * * N N N * O * * * P * * * Q * * *\\n' +\n               '* G * * H H * I * * J J * K K * L * * M * * * N * * * O O O * P P * * Q Q Q *\\n' +\n               '* G * * H * * I I * J * * * K * L L * M * * * N * * * * O * * * P P * * * Q *\\n' +\n               '* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\\n' +\n               'R * * * S * * * T * * * U U U * V V * * W W * * X X * * * Y * * * Z * * 1 * *\\n' +\n               'R R R * S S * * T T * * * U * * * V V * * W * * * X * * Y Y Y * Z Z * * 1 1 *\\n' +\n               '* R * * * S S * * T * * * U * * * V * * * W W * * X * * * Y * * * Z Z * * 1 1\\n' +\n               '* R * * * S * * * T T * * U * * * V * * * W * * * X X * * Y * * * Z * * * * 1\\n' +\n               '* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\\n' +\n               '* * * * * 2 2 * 3 * * * 4 * * * 5 * * * 6 * * * 7 7 * * 8 8 * * 9 9 * * * * *\\n' +\n               '* * * * * 2 2 * 3 3 3 * 4 4 * * 5 5 5 * 6 * 6 * 7 7 7 * 8 8 * * * 9 9 * * * *\\n' +\n               '* * * * * 2 2 * 3 3 * * 4 4 4 * 5 * 5 * 6 6 6 * * 7 * * * 8 8 * 9 9 * * * * *';\n\n\nvar hexominoColor = {};\nhexominoColor['A'] = '#600000';\nhexominoColor['B'] = '#B00000';\nhexominoColor['C'] = '#FF0000';\nhexominoColor['c'] = '#FF0000';\nhexominoColor['D'] = '#00FF00';\nhexominoColor['E'] = '#00B000';\nhexominoColor['F'] = '#006030';\nhexominoColor['G'] = '#3333FF';\nhexominoColor['H'] = '#FF6000';\nhexominoColor['h'] = '#FF6000';\nhexominoColor['I'] = '#0000AC';\nhexominoColor['J'] = '#FFB000';\nhexominoColor['K'] = '#FFFF00';\nhexominoColor['k'] = '#FFFF00';\nhexominoColor['L'] = '#B06000';\nhexominoColor['M'] = '#B0B000';\nhexominoColor['N'] = '#B0FF00';\nhexominoColor['O'] = '#B0FFAC';\nhexominoColor['o'] = '#B0FFAC';\nhexominoColor['P'] = '#606000';\nhexominoColor['Q'] = '#B060AC';\nhexominoColor['R'] = '#6060AC';\nhexominoColor['S'] = '#60B0AC';\nhexominoColor['s'] = '#60B0AC';\nhexominoColor['T'] = '#6000AC';\nhexominoColor['U'] = '#FF00AC';\nhexominoColor['u'] = '#FF00AC';\nhexominoColor['V'] = '#00DDFF';\nhexominoColor['W'] = '#60FFAA';\nhexominoColor['w'] = '#60FFAA';\nhexominoColor['X'] = '#ACFFFF';\nhexominoColor['Y'] = '#FF60FF';\nhexominoColor['y'] = '#FF60FF';\nhexominoColor['Z'] = '#00ACFF';\nhexominoColor['1'] = '#0060A0';\nhexominoColor['2'] = '#FFBCFF';\nhexominoColor['3'] = '#888888';\nhexominoColor['4'] = '#ACACFF';\nhexominoColor['$'] = '#ACACFF';\nhexominoColor['5'] = '#FFD880';\nhexominoColor['%'] = '#FFD880';\nhexominoColor['6'] = '#3E0068';\nhexominoColor['7'] = '#D1E1FF';\nhexominoColor['&#038;'] = '#D1E1FF';\nhexominoColor['8'] = '#203D00';\nhexominoColor['9'] = '#FFE500';\nhexominoColor['*'] = 'white';\nhexominoColor['.'] = '#CCC';\nhexominoColor['@'] = 'black';\n\nvar hexominoLabel = {};\nhexominoLabel['c'] = '&#038;#9632';\nhexominoLabel['h'] = '&#038;#9632';\nhexominoLabel['k'] = '&#038;#9632';\nhexominoLabel['o'] = '&#038;#9632';\nhexominoLabel['s'] = '&#038;#9632';\nhexominoLabel['u'] = '&#038;#9632';\nhexominoLabel['w'] = '&#038;#9632';\nhexominoLabel['y'] = '&#038;#9632';\nhexominoLabel['$'] = '&#038;#9632';\nhexominoLabel['%'] = '&#038;#9632';\nhexominoLabel['&#038;'] = '&#038;#9632';\n\ndocument.write(puzzleToHtmlTable(hexomino, hexominoColor, true, hexominoLabel, 'small'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;5.  The 35 free hexominoes.<\/span>\n<\/div>\n<p>To see the problem, we need a larger puzzle:  let&#8217;s up the ante from<br \/>\npentominoes to hexominoes.  There are 35 uniquely shaped free hexominoes shown<br \/>\nin Figure&nbsp;5.  Each piece has area 6 so the total area of any shape<br \/>\nconstructed from the pieces is 210 &mdash; 3.5 times the area of a pentomino<br \/>\npuzzle.<\/p>\n<p><a name=\"figure6\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\nvar parallelogram = '* * * * * * * * * * * * * 4 T 8 8 N N N N G G B B B B B\\n' +\n                    '* * * * * * * * * * * * 4 4 T T 8 8 N G G G G B K K K *\\n' +\n                    '* * * * * * * * * * * 4 4 4 U T 8 8 N F F F D K K K * *\\n' +\n                    '* * * * * * * * * * 7 U U U U T T F F F D D D D D * * *\\n' +\n                    '* * * * * * * * * 7 7 7 2 2 U 6 6 6 M M M M S S * * * *\\n' +\n                    '* * * * * * * * J J 7 7 2 2 W 6 R 6 M 3 S S S * * * * *\\n' +\n                    '* * * * * * * J J J J Z 2 2 W W R 6 M 3 3 S * * * * * *\\n' +\n                    '* * * * * * I I I I Z Z Z Z W R R R 3 3 3 * * * * * * *\\n' +\n                    '* * * * * H I H Y I V V Z W W O L R L L * * * * * * * *\\n' +\n                    '* * * * H H H H Y V V X X 9 O O L L L * * * * * * * * *\\n' +\n                    '* * * E E E E Y Y Y V X 9 9 9 O O O * * * * * * * * * *\\n' +\n                    '* * E E C Q Q 5 Y 5 V X 9 P 9 1 1 * * * * * * * * * * *\\n' +\n                    '* C C C C C Q 5 5 5 X X P P 1 1 * * * * * * * * * * * *\\n' +\n                    'A A A A A A Q Q Q 5 P P P 1 1 * * * * * * * * * * * * *';\n\ndocument.write(puzzleToHtmlTable(parallelogram, hexominoColor, true, hexominoLabel, 'small'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;6.  The 35 hexominoes placed into<br \/>\nthe shape of a 15&#215;14 parallelogram.<\/span>\n<\/div>\n<p>Consider first a hexomino puzzle shaped like a parallelogram consisting of<br \/>\n14 rows of 15 squares each stacked in a sloping stair-step pattern.<br \/>\nFigure&nbsp;6 shows one solution to this puzzle.  (As I explain in a later<br \/>\nsection, you can&#8217;t actually pack hexominoes in a rectangular box, so the<br \/>\nparallelogram is one of the simplest feasible hexomino constructions.)  The<br \/>\nfirst time I ran DLX on this puzzle I used a one-time application of a volume<br \/>\nconstraint filter which throws out a bunch of images up front that can&#8217;t possibly<br \/>\nbe part of a solution (see below).  It ran for quite some time without finding a<br \/>\nsingle solution.  A trace revealed that DLX had placed the first few pieces<br \/>\ninto the rather unfortunate construction shown in Figure&nbsp;7.  Note the<br \/>\nsmall area at the lower left that has almost been enclosed.  Every square in<br \/>\nthat area has many ways to cover it, so the min-fit heuristic didn&#8217;t consider<br \/>\nthis pocket very constrained and ignored it.  There is actually no way to fill all the<br \/>\nsquares:  the only piece that could fill it has already been placed on the<br \/>\nboard.  DLX didn&#8217;t recognize the problem and so continued to try to solve the<br \/>\npuzzle.  I call such a well concealed spot in the puzzle that can&#8217;t be filled<br \/>\na <i>landmine<\/i>.<\/p>\n<p><a name=\"figure7\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\nvar landmine =\n\n               '* * * * * * * * * * * * * . . . . . . . . . . C C C C C\\n' +\n               '* * * * * * * * * * * * . . . . . . . . . . . . C 1 1 *\\n' +\n               '* * * * * * * * * * * . . . . . . . . . . . . . 1 1 * *\\n' +\n               '* * * * * * * * * * . . . . . . . . . . . . . 1 1 * * *\\n' +\n               '* * * * * * * * * . . . . . . . . . . . . . S S * * * *\\n' +\n               '* * * * * * * * . . . . . . . . . . . . S S S * * * * *\\n' +\n               '* * * * * * * . . . . . . . . . . . . . . S * * * * * *\\n' +\n               '* * * * * * M M M M . . . . . . . . . . . * * * * * * *\\n' +\n               '* * * * * 8 8 . . M . . . . . . . . . . * * * * * * * *\\n' +\n               '* * * * 8 8 . . . M . . . . . . . . . * * * * * * * * *\\n' +\n               '* * * Z 8 8 . . . . . . . . . . . . * * * * * * * * * *\\n' +\n               '* * Z Z Z Z P 5 5 . . . . . . . . * * * * * * * * * * *\\n' +\n               '* K K K Z P P 5 . . . . . . . . * * * * * * * * * * * *\\n' +\n               'K K K P P P 5 5 5 . . . . . . * * * * * * * * * * * * *';\n\ndocument.write(puzzleToHtmlTable(landmine, hexominoColor, true, hexominoLabel, 'small'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;7.  DLX plants a landmine.<\/span>  There is<br \/>\nno way to fill the almost enclosed area at the lower left, but DLX can&#8217;t see<br \/>\nthe problem and continues to fill in the rest of the puzzle, stumbling over<br \/>\nthis landmine many times before dismantling it.\n<\/div>\n<p>This behavior is exactly similar to the problem the de Bruijn algorithm<br \/>\nexhibited in Figure&nbsp;4:  DLX can also create spaces in the puzzle that<br \/>\ncan&#8217;t possibly be filled, not immediately see them, and stumble upon them many<br \/>\ntimes before dismantling the problem.  It is interesting that the de Bruijn<br \/>\nalgorithm is actually less susceptible to this particular pitfall.  Although de<br \/>\nBruijn&#8217;s algorithm can also create landmines, it can&#8217;t wander all over the<br \/>\npuzzle before discovering them.  DLX running with the min-fit heuristic is<br \/>\nable to wander far-and-wide filling in holes it thinks more constrained than<br \/>\nthe landmine; finally step on it; get stuck; back up a little and wander off<br \/>\nin some other direction.  And because the landmine created in Figure&nbsp;7<br \/>\nwas created so early in the piece placement sequence, there were many ways for<br \/>\nDLX to go astray:  it took almost two million steps for DLX to dismantle this<br \/>\nlandmine.  (I decided not to make a movie of this one.)<\/p>\n<p>As a second example, consider the box-in-a-diamond hexomino puzzle of<br \/>\nFigure&nbsp;8.  Due to the center rectangle, DLX frequently partitions the<br \/>\nopen space into two isolated regions as shown.  Each time the open space is<br \/>\ndivided, there&#8217;s only 1 chance in 6 that the two areas will have a volume that<br \/>\ncan possibly be filled.  Out of 1000 runs of the solver each using a different<br \/>\nrandom ordering of the nodes in each DLX column, 842 runs resulted in a<br \/>\npartitioning of the open space into two (or more) large unfillable regions<br \/>\nbefore the eleventh-to-last piece was placed.  When such a partition is<br \/>\ncreated, DLX examines every possible permutation of pieces that fails to fill<br \/>\n(at least one of) the isolated regions.<\/p>\n<p><a name=\"figure8\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar partition = '* * * * * * * * * * * E * * * * * * * * * * *\\n' +\n                '* * * * * * * * * * 1 E A * * * * * * * * * *\\n' +\n                '* * * * * * * * * 1 1 E A 4 * * * * * * * * *\\n' +\n                '* * * * * * * * 1 1 E E A 4 4 * * * * * * * *\\n' +\n                '* * * * * * * . 1 . E B A 4 4 4 * * * * * * *\\n' +\n                '* * * * * * . . . . . B A . . . . * * * * * *\\n' +\n                '* * * * * . . . . . . B A . . . . . * * * * *\\n' +\n                '* * * * . . . . . . . B . . . . . . . * * * *\\n' +\n                '* * * . . . . . . . B B . . . . . . . . * * *\\n' +\n                '* * . . . . * * * * * * * * * * * . . . . * *\\n' +\n                '* O . . . . * * * * * * * * * * * . . . . . *\\n' +\n                'O O . . . . * * * * * * * * * * * . . . . . .\\n' +\n                '* O O O S S * * * * * * * * * * * . . . . . *\\n' +\n                '* * S S S 8 * * * * * * * * * * * . . . . * *\\n' +\n                '* * * S P 8 8 8 . . . . . . . . . . . . * * *\\n' +\n                '* * * * P P 8 8 . . . . . . . . . . . * * * *\\n' +\n                '* * * * * P P P 3 . . . . . . . . . * * * * *\\n' +\n                '* * * * * * 3 3 3 . . . . . . . . * * * * * *\\n' +\n                '* * * * * * * 3 3 . . . . . . . * * * * * * *\\n' +\n                '* * * * * * * * J J J J . . . * * * * * * * *\\n' +\n                '* * * * * * * * * J J 7 7 . * * * * * * * * *\\n' +\n                '* * * * * * * * * * 7 7 7 * * * * * * * * * *\\n' +\n                '* * * * * * * * * * * 7 * * * * * * * * * * *';\n\ndocument.write(puzzleToHtmlTable(partition, hexominoColor, true, hexominoLabel, 'small'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;8.  DLX partitioning the box-in-a-diamond<br \/>\nhexomino puzzle.<\/span>  The area of the smaller open region is 39 which is<br \/>\nunfillable by pieces of size 6.  DLX doesn&#8217;t recognize the problem and gets<br \/>\nstuck on this configuration for many algorithmic steps before removing enough<br \/>\npieces to join the two isolated regions back together.\n<\/div>\n<p>So here again, the min-fit ordering heuristic has lead to the creation of a<br \/>\ntopology that can&#8217;t possibly be filled.  And again, DLX can&#8217;t see the problem,<br \/>\nand wastes time exhaustively exploring fruitless branches of the search tree.<br \/>\nDe Bruijn&#8217;s algorithm can also be made to foolishly partition the open space of<br \/>\npuzzles: if you ask the de Bruijn algorithm to, say, start at the bottom of a<br \/>\nU-shaped puzzle and fill upwards, it will inevitably partition the open space<br \/>\ninto the left and right columns of the U.  But aside from such cruel<br \/>\nconstructions, de Bruijn&#8217;s algorithm is relatively immune to this pitfall.<\/p>\n<p>When I first saw these troubles, my faith in the min-fit heuristic was<br \/>\nunshaken:  the extreme reduction in the number of algorithmic steps seen for<br \/>\nthe Tetris Cube and other small puzzles had me convinced it was the way to go.<br \/>\nSo I built landmine sweepers and volume checkers to provide protection against<br \/>\nthese pitfalls.  These worked pretty well, but as I thought about what was<br \/>\nhappening more, I began to doubt the approach.  As you pursue the most<br \/>\nconstrained hole or piece, you end up wandering around the puzzle space<br \/>\nhaphazardly leaving a complex topology in your wake.  This strikes me as the<br \/>\nwrong way to go:  it&#8217;s certainly not the way I&#8217;d work a puzzle manually.  When<br \/>\nyou finally get down to the last few pieces you are likely to have many nooks<br \/>\nand crannies that simply can&#8217;t all be filled with the pieces that are left.<br \/>\nAnd I think that is ultimately the most important thing with these kinds of<br \/>\npuzzles:  you want to fill the puzzle in such a way that when you near<br \/>\ncompletion you have simple geometries that have a higher probability of<br \/>\nproducing solutions.<\/p>\n<p>One could argue that wandering around the board spoiling the landscape<br \/>\nis a good thing!  Won&#8217;t that make it more likely to find a hole or a piece<br \/>\nwith very few fit options; reducing the number of choices that have to be<br \/>\nexamined for the next algorithmic step and ultimately reducing the run time of<br \/>\nthe entire algorithm?  I used to have such thoughts in my head, but I now<br \/>\nthink these ideas flawed.  When solving the puzzle, your current construction<br \/>\neither leads to solutions or it doesn&#8217;t.  <span class=\"important\">You want to<br \/>\nminimize how much time you spend exploring constructions that have no<br \/>\nsolutions.<\/span>  (The day after I wrote this down,<br \/>\n<a href=\"http:\/\/www.xs4all.nl\/~gp\/PolyominoSolver\/Polyomino.html\">Gerard<\/a><br \/>\nsent me an email saying exactly the same thing&#8230;so I decided it was worth<br \/>\nputting in bold.)  The real advantage of picking the min-fit column is<br \/>\n<i>not<\/i> that it has fewer cases to examine, but rather that there&#8217;s a<br \/>\nbetter chance that all the fit choices lead quickly to a dead end.  In other<br \/>\nwords, by using the min-fit heuristic DLX tends to more quickly identify<br \/>\nproblems with the current construction that preclude solutions, and more<br \/>\nquickly backtrack to a construction that does have solutions.  The problem<br \/>\nwith this approach is that as it wanders about examining the most constrained<br \/>\nelements, it can create more difficulties than it resolves.<\/p>\n<p>For large puzzles, instead of looking for individual holes or pieces that<br \/>\nare likely to have problems, I think it is better to look at the overall<br \/>\ntopology of the puzzle and fill in regions that appear most confined (a macro<br \/>\nview instead of a micro view).  By strategically placing pieces so that at the<br \/>\nend you have a single simply shaped opening, you will find solutions with a<br \/>\nhigher probability.  This is just another way of saying that there is a high<br \/>\nprobability that you are still in a construction that has solutions &mdash;<br \/>\nwhich is your ultimate goal.<\/p>\n<p>So if the puzzle is shaped like a rectangle, start at one narrow side<br \/>\nand work your way across to the other narrow side.  If the puzzle is shaped<br \/>\nlike a U, then fill it in the way you&#8217;d draw the U with a pencil:  down<br \/>\none side, around the bottom and up the other side.  If the puzzle is a five<br \/>\npointed star, fill in the points of the star first, and leave the open space<br \/>\nin the middle of the star for last.  (Hmmm, or maybe it would be better to<br \/>\nfinish heading out one point?  I&#8217;m not sure.)<\/p>\n<p>So if what I say is true, then why does the min-fit heuristic work so well<br \/>\nfor the Tetris Cube?  I think the min-fit heuristic works well once the<br \/>\nnumber of pieces remaining in a puzzle drops to some threshold which depends<br \/>\non the complexity of the pieces and the geometries of the puzzle.  Because<br \/>\nTetris Cube pieces are rather complicated, and because the geometry of the puzzle<br \/>\nis small relative to the size of these pieces, the min-fit heuristic works well<br \/>\nfor that puzzle from the start.<\/p>\n<p>Knuth explored the possibility of using the min-fit heuristic for the first<br \/>\npieces placed, but then simply choosing holes in a predefined order for the<br \/>\nlast pieces placed.  The thinking was that for the last few pieces, picking<br \/>\nthe most constrained hole or piece doesn&#8217;t buy you much and you&#8217;re better off<br \/>\njust trying permutations as fast as you can and skipping the search for the<br \/>\nmost constrained element (and skipping the maintenance of the column counts<br \/>\nthat support this search).  Knuth was not able get any significant gains with<br \/>\nthis technique.  I propose the opposite approach:  initially,<br \/>\ndeterministically fill in <i>regions<\/i> of the puzzle that are most confined,<br \/>\nthen when you&#8217;ve worked your way down to a smaller area (and placement options<br \/>\nare more limited) start using the min-fit heuristic.<\/p>\n<p>To explore this idea, my solver supports a few alternative ordering<br \/>\nheuristics.  You can turn off one heuristic and enable another when the number<br \/>\nof remaining pieces hits some configured threshold.  One available heuristic<br \/>\n(named heuristic x) has these behaviors:<\/p>\n<ol>\n<li>If there exists a DLX column with no ones in it, then this column<br \/>\nis selected;<\/li>\n<li>else, if there exists a DLX column with exactly one 1 in it, then<br \/>\nthis column is selected;<\/p>\n<li>otherwise, the hole column with the minimum x coordinate value is selected.<br \/>\nIn the case of a tie, the column with fewest ones (i.e., the hole with fewest<br \/>\nfits) is selected.\n<\/ol>\n<p>So I ran the solver against the 15&#215;14 parallelogram initially applying the x<br \/>\nheuristic, but switching to the min-fit heuristic when the number of remaining<br \/>\npieces hit some configured number.  Unfortunately, an exhaustive examination<br \/>\nof the search tree for this puzzle is not feasible.  Instead, I used<br \/>\nMonte-Carlo techniques to estimate the best time to stop using the x heuristic<br \/>\nand start using the min-fit heuristic.  Each data point shown in Figure&nbsp;9<br \/>\nshows the average number of solutions found per second over 10,000 runs of the<br \/>\nsolver each initialized with a different random ordering of the nodes in<br \/>\neach column of the DLX matrix.  Each run was terminated the first time the<br \/>\n16th-to-last piece was <i>removed<\/i> from the puzzle.  (In other words, once<br \/>\nthe 16th-to-last piece is placed, the solver examined all possible ways to<br \/>\nplace the last 15 pieces, but then terminates that run.)  Solutions to this<br \/>\npuzzle tend to appear in great bursts, and even at 10,000 runs I think there<br \/>\nis quite a bit of uncertainty in these solution rates.  It should also be<br \/>\nnoted that the DLX processing load for the early piece placements is enormous<br \/>\ncompared to the latter pieces.  Terminating algorithm processing each time the<br \/>\n16th-to-last piece is removed means the great efforts expended to reduce the<br \/>\nmatrix were largely wasted.  This results in reduced average performance.<\/p>\n<p>Despite these weaknesses the analysis offers evidence that when there<br \/>\nare more than approximately 20 pieces left to be placed in this puzzle,<br \/>\nthere is no real benefit to using the min-fit heuristic.  In fact, using the<br \/>\nmin-fit heuristic beyond 20 pieces seems to show some slight degradation in<br \/>\nperformance; although the last data point (where the min-fit heuristic is used<br \/>\nfor the last 34 pieces placed) seems to again offer a performance increase.<br \/>\nThis could be a statistical fluke, but I rather suspect there is some<br \/>\nsignificant benefit to filling the two opposite acute corners of the puzzle<br \/>\nearly.  The x-heuristic simply ignores the tight corner at the opposite side<br \/>\nof the puzzle.  It is my suspicion that as puzzle sizes increase application<br \/>\nof the min-fit heuristic across the entire puzzle will result in ever worsening<br \/>\nperformance relative to heuristics that (at least initially) pack confined<br \/>\nregions of the puzzle first; but larger puzzles are exceedingly difficult to<br \/>\nanalyze even with Monte-Carlo techniques.<\/p>\n<p><a name=\"figure9\"><img decoding=\"async\" src=\"\/images\/polycube\/hexominorate.png\" class=\"graphic\"\nalt=\"Graph showing DLX solution rates for the 15x14 hexomino parallelogram as\na function of the number of pieces placed using the min-fit ordering heuristic.\"\/><\/a><\/p>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;9.  DLX solution rates for the<br \/>\n15&#215;14 hexomino parallelogram.<\/span>  The chart shows DLX solution rates for<br \/>\nthe 15&#215;14 hexomino parallelogram when pieces are initially packed from left to<br \/>\nright (using the x ordering heuristic), but when the number of remaining<br \/>\npieces is at or below a configured threshold (shown on the x-axis of the<br \/>\nchart), the min-fit heuristic is used.  Each data point on the chart<br \/>\nrepresents the average solution rates over 10,000 runs of the solver where for<br \/>\neach run the nodes in each column of the DLX matrix were randomly ordered, and<br \/>\neach run was terminated the first time the 16th-to-last piece is removed from<br \/>\nthe puzzle.\n<\/div>\n<p>Depending on the geometry of the puzzle, it can be even more important to<br \/>\nfollow your intuition.  <a href=\"http:\/\/www.xs4all.nl\/~gp\/PolyominoSolver\/Polyomino.html\"><br \/>\nGerard&#8217;s Polyomino Solution Page<\/a> includes a puzzle similar to the one shown in<br \/>\nFigure&nbsp;10.  This puzzle, however, is 2 squares longer and somewhat more<br \/>\ndifficult to solve.  I was unable to find any solutions to this puzzle through<br \/>\nexclusive use of the min-fit heuristic even after hours of execution time; but<br \/>\nby initially picking the holes farthest from the geometric center of the<br \/>\npuzzle (my &#8220;R&#8221; heuristic) and then switching to min-fit heuristic once the<br \/>\nless-confined central cavity was reached I averaged about 9 solutions per minute<br \/>\nover 6 hours of run time.<\/p>\n<p><a name=\"figure10\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar skew = '* * * * * * * * * * * * * * * * * * * * * V Q O O O L L 5 5 5 9 9 Y H H H H J J J J M M M M X B B B B B 6 6 3 3\\n' +\n           '* * * * * * * * * * * * * * * * * * * * * V Q Q Q O O L R 5 9 9 Y Y Y H W H I J J I M X X X X C K K K B 6 3 3 3\\n' +\n           '* * * * * * * * * * * * * * * * * * * * * V V U Q O L L R 5 5 9 9 Y W W W W I I I I M X C C C C C K K K 6 6 6 3\\n' +\n           '2 2 4 1 1 S S G G G G F F F D D D D D Z V V P U Q 7 L R R R T N 8 Y W * * * * * * * * * * * * * * * * * * * * *\\n' +\n           '2 2 4 4 1 1 S S S G G E E F F F D Z Z Z Z P P U 7 7 7 R T T T N 8 8 8 * * * * * * * * * * * * * * * * * * * * *\\n' +\n           '2 2 4 4 4 1 1 S E E E E A A A A A A Z P P P U U U 7 7 T T N N N N 8 8 * * * * * * * * * * * * * * * * * * * * *';\n\ndocument.write(puzzleToHtmlTable(skew, hexominoColor, true, hexominoLabel, 'tiny'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;10.  A hexomino puzzle shaped like a<br \/>\nrifle.<\/span>  Exclusive use of the min-fit heuristic on this puzzle performs<br \/>\nvery badly.  Packing the long skinny channels first and switching to the<br \/>\nmin-fit heuristic once the central cavity is reached yields solutions at a<br \/>\nmuch higher rate.<\/div>\n<p><a name=\"mch\"><\/a><\/p>\n<h3><span class=\"h3\">Most Constrained Hole (MCH) Algorithm<\/span><\/h3>\n<p>DLX is quite crafty, but all the linked list operations can be overly<br \/>\nburdensome for small to medium sized puzzles.  In a head-to-head match up, my<br \/>\nimplementation of de Bruijn&#8217;s algorithm runs more than 6 times faster than<br \/>\nDLX for the 10&#215;6 pentomino puzzle (and remember &mdash; that&#8217;s without the<br \/>\nde Bruijn algorithm using the trick of placing the X piece first.)  For the<br \/>\nmore complex three dimensional Tetris Cube puzzle, DLX fairs much better, but<br \/>\nstill takes more than twice as long to run as de Bruijn&#8217;s algorithm.<\/p>\n<p>The Most Constrained Hole (MCH) algorithm attempts to reap at least some of<br \/>\nthe benefits of DLX without incurring the high cost of its matrix<br \/>\nmanipulations.<\/p>\n<p>I present this algorithm third, because the story flows better that way,<br \/>\nbut it is actually the first polycube solving algorithm I implemented and is<br \/>\nof my own design.  I make no claims of originality:  it is a simple idea and<br \/>\nothers have independently devised similar algorithms.  I first implemented<br \/>\na variant of this technique to solve pentomino puzzles one afternoon in the<br \/>\nsummer of 1997 whilst at a TCL\/TK training class in San Jose,<br \/>\nCA.<\/p>\n<p>MCH simply chooses the hole that has the fewest number of fit possibilities<br \/>\nas the next fill target.  Therefore DLX (when using the min fit ordering<br \/>\nheuristic) and MCH only deviate in their decision making process in those<br \/>\nsituations where a piece turns out to be more constrained than any hole.  To<br \/>\nfind the MCH, the software examines each remaining hole in the puzzle, and for<br \/>\neach of those holes it counts the number of ways the remaining pieces can be<br \/>\nplaced to fill that hole.  The MCH is then taken to be the hole with the<br \/>\nfewest fits.<\/p>\n<p>Although DLX will sometimes choose a piece to place next rather than a hole<br \/>\nto fill, the biggest difference between MCH and DLX is not in the step-by-step<br \/>\nbehavior of the two algorithms, but rather in their implementation.  My<br \/>\npolycube solving software has as one of its fundamental data structures an<br \/>\nobject called a <span class=\"code\">GridPoint<\/span>.  During Puzzle<br \/>\ninitialization I create an array of <span class=\"code\">GridPoint<\/span><br \/>\nobjects with the same dimensions as the Puzzle.  So for the Tetris Cube I<br \/>\ncreate a 4x4x4 matrix of <span class=\"code\">GridPoint<\/span>s.  To support<br \/>\nMCH, at each <span class=\"code\">GridPoint<\/span> I create an array of 12 lists<br \/>\n&mdash; one list for each of the twelve puzzle pieces.  The list for piece B<br \/>\nat <span class=\"code\">GridPoint<\/span> (3, 1, 2) contains all the images of<br \/>\npiece B that fill the hole at grid coordinates (3, 1, 2).  To count the total<br \/>\nnumber of fits at (3, 1, 2) I traverse the image lists for all the pieces that<br \/>\nhave not yet been placed in the puzzle and count the total number that fit.<br \/>\nTo find the most constrained hole, I perform this operation at every open hole<br \/>\nin the puzzle and take the hole with the minimum fit count.<\/p>\n<p>Recall that for the de Bruijn algorithm a piece of size 6 with 24 unique<br \/>\nrotations only requires 24 fit attempts, but that only works because the<br \/>\nalgorithm restricts itself to filling the hole with minimum coordinate values<br \/>\nin z, y, x priority order.  For MCH the image lists must contain all the images<br \/>\nof a piece that fill a hole.  So a piece with 6 cubelets and 24 unique<br \/>\nrotations would have nominally 144 entries in the list.  (I actually throw out<br \/>\nimages that don&#8217;t fit inside the puzzle box as discussed in the section on<br \/>\nimage filters below.)  So these lists can be rather long, and many lists at<br \/>\nmany holes have to be checked to find the MCH.<\/p>\n<p>The whole idea sounds loopy I know, but for the case of the 10&#215;6 pentomino<br \/>\npuzzle, MCH runs 25% faster than DLX (which still makes it almost 5 times<br \/>\nslower than de Bruijn).  For the case of the Tetris Cube, MCH is the fastest<br \/>\nof the three algorithms running about 2.5 times faster than DLX and about<br \/>\n10% faster than de Bruijn.<\/p>\n<p>The solver also includes a variant of MCH that only considers those holes<br \/>\nwith the fewest number of neighboring holes.  I call this estimated MCH<br \/>\n(EMCH).  This approach sometimes gets the true MCH wrong, but overall seems to<br \/>\nperform better &mdash; about 25% faster for 10&#215;6 Pentominoes and more than a<br \/>\nthird faster for the Tetris Cube.<\/p>\n<p>I think for larger puzzles, when the number of images at each grid point<br \/>\nstarts to increase by orders of magnitude, this approach of explicit fit<br \/>\ncounting will break down.  There are other ways you can estimate the MCH: I<br \/>\nhad one MCH variant that didn&#8217;t count fits at all, but rather looked purely at<br \/>\nthe geometry of the open spaces near a hole to gauge how difficult it was<br \/>\ngoing to be to fill.  In any case, I only apply MCH on smaller 3-D puzzles<br \/>\nbecause this is where I&#8217;ve found it to outpace the other two algorithms.<\/p>\n<p><a name=\"combine\"><\/a><\/p>\n<h3><span class=\"h3\">Combining the Algorithms<\/span><\/h3>\n<p>Each of the three algorithms examined had different strengths.  When there<br \/>\nare very few pieces, the simple de Bruijn algorithm had best performance.  For<br \/>\nmedium sized 3-D puzzles, EMCH performed best.  Only DLX can choose to iterate<br \/>\nover all placements of a piece which can provide huge performance benefits in<br \/>\nthe right situation.  (See, for example, the section on rotational redundancy<br \/>\nconstraint violations.)  Also the ability to define different ordering<br \/>\nheuristics makes DLX quite useful for large puzzles with non-trivial<br \/>\ntopologies.<\/p>\n<p>To allow the best algorithm to be applied at the right time to the<br \/>\nright problem, I&#8217;ve implemented all three algorithms into a single puzzle<br \/>\nsolving application with the capability to turn off one algorithm and turn on<br \/>\nanother when the number of remaining pieces reaches configured thresholds.<br \/>\nAs you shall see, this combined algorithmic approach gives much improved<br \/>\nperformance for many puzzles.<\/p>\n<p><a name=\"softopt\"><\/a><\/p>\n<h2><span class=\"h2\">Software Optimizations<\/span><\/h2>\n<p>I still have the broad topic of constraints to discuss, but I first want to<br \/>\nshare some software optimizations I&#8217;ve made on the de Bruijn and MCH<br \/>\nalgorithms.  Together these software optimizations reduced the time to find<br \/>\nall Tetris Cube solutions with these algorithms by about a factor of five.<br \/>\n(This probably just means my initial implementation was really bad, but I<br \/>\nthink the optimizations are still worth discussing.)<\/p>\n<p><a name=\"bitfields\"><\/a><\/p>\n<h3><span class=\"h3\">Bit Fields<\/span><\/h3>\n<p>I was originally tracking the occupancy state of the puzzle via a flag<br \/>\nnamed <span class=\"code\">occupied<\/span> in each<br \/>\n<span class=\"code\">GridPoint<\/span> object.  To determine if an image fit in<br \/>\nthe puzzle, this flag was examined for each<br \/>\n<span class=\"code\">GridPoint<\/span> used by the image.  Most of the popular<br \/>\npolyomino (e.g., Pentominoes) and polycube puzzles (e.g., Soma, Bedlam,<br \/>\nTetris) have an area or volume of not more than 64.  This is rather convenient<br \/>\nas it allows one to model the occupancy state of any of these puzzles with a<br \/>\n64-bit field.  So I ditched all the <span class=\"code\">occupied<\/span> flags<br \/>\nin the <span class=\"code\">GridPoint<\/span> array and replaced them all with a<br \/>\nsingle 64 bit integer variable (named<br \/>\n<span class=\"code\">occupancyState<\/span>) bound to the Puzzle as a whole.<br \/>\nEach image object was similarly modified to store a 64-bit<br \/>\n<span class=\"code\">layoutMask<\/span> identifying the<br \/>\n<span class=\"code\">GridPoint<\/span>s it occupies.  To see if a particular<br \/>\nimage fits in the puzzle you now need only perform a binary-and of the<br \/>\npuzzle&#8217;s <span class=\"code\">occupancyState<\/span> with the image&#8217;s<br \/>\n<span class=\"code\">layoutMask<\/span> and check for a zero result.  To place<br \/>\nthe piece, you need only perform the binary-or of the puzzle&#8217;s<br \/>\n<span class=\"code\">occupancyState<\/span> with the image&#8217;s<br \/>\n<span class=\"code\">layoutMask<\/span> and store that result as the new<br \/>\n<span class=\"code\">occupancyState<\/span>.  This is really greasy fast and<br \/>\ncut the run times by more than a factor of two.<\/p>\n<p>The only down-side to this approach is that it prevents you from solving<br \/>\npuzzles that are larger than the size of the bit field.  You could increase<br \/>\nthe size of the field, but this quickly starts to wipe out the benefit.  But<br \/>\nyou can still take advantage of the performance benefit of bit masks for<br \/>\npuzzles that are bigger than size 64 by simply using DLX until the total<br \/>\nvolume of remaining pieces is 64 or less.  Then you can morph the data model<br \/>\ninto a bit-oriented form and use the MCH or de Bruijn algorithms to place the<br \/>\nlast several pieces (which is the only time speed really matters).  For very<br \/>\nlarge puzzles (e.g., a heptominoes puzzle) I think this approach will break<br \/>\ndown: by the time you get down to an area of size 64 the search tree is<br \/>\ncollapsing and it&#8217;s probably too late for a data model morph to pay off.<\/p>\n<p><a name=\"earlyexit\"><\/a><\/p>\n<h3><span class=\"h3\">Early MCH Fit Count Exit<\/span><\/h3>\n<p>The MCH routine examines different holes remaining in the puzzle<br \/>\nand finds the number of possible fits for each of them.  I modified the<br \/>\nprocedure that counts fits to simply return early once the number of fits<br \/>\nsurpasses the number of fits of the most constrained hole found so far.  This<br \/>\ntrivial change sped the software up 20% for the Tetris Cube.<\/p>\n<p><a name=\"permutation\"><\/a><\/p>\n<h3><span class=\"h3\">Fast Permutation Algorithm<\/span><\/h3>\n<p>In my original implementation of both MCH and de Bruijn&#8217;s algorithm,<br \/>\nI was lazily using an STL set (sorted binary tree) to store the index numbers<br \/>\nof the remaining pieces.  (Some of you are rudely laughing at me.  Stop that.)<br \/>\nOnly the pieces in this set should be used to fill the next target hole.<br \/>\nThe index of the piece being processed is removed from the set.  If the piece<br \/>\nfits, the procedure recurses on itself starting with the now smaller set.<br \/>\nOnce all attempts to place a piece are exhausted, the piece is added back to<br \/>\nthe set, and the next entry in the set is removed and processed.  This worked<br \/>\nfine, but STL sets are not the fastest thing in the galaxy.  As you might<br \/>\nimagine there&#8217;s been lots of research on fast permutation algorithms (dating<br \/>\nback to the 17th century).  I settled on an approach that was quite similar to<br \/>\nwhat I was already doing, but the store for the list of free index numbers is<br \/>\na simple integer array instead of a binary tree.  An index is &#8220;removed&#8221; from the<br \/>\narray by swapping its position with the entry at the end of the array.  So my<br \/>\nSTL set erase and insert operations were replaced with a pair of integer<br \/>\nswaps.  This change improved the fastest run times by about another 20%.<\/p>\n<p><a name=\"constraints\"><\/a><\/p>\n<h2><span class=\"h2\">Constraints<\/span><\/h2>\n<p>The algorithms above observe the constraint that when a hole can&#8217;t be<br \/>\nfitted, or (in the case of DLX) a piece can&#8217;t be fit they back up.  But other<br \/>\nconstraints (beyond this obvious fit constraint) exist for polycube and<br \/>\npolyomino puzzles which if violated prohibit solutions.  My solver can take<br \/>\nadvantage of these constraints in two different ways.  First I&#8217;ve implemented<br \/>\nmonitors that watch a particular constraint and when a violation is detected<br \/>\nan immediate backtrack is triggered.  Second, I&#8217;ve implemented a set<br \/>\nof image filters that remove images that would violate constraints<br \/>\nif used.<\/p>\n<p><a name=\"backtrack\"><\/a><\/p>\n<h3><span class=\"h3\">Backtrack Triggers<\/span><\/h3>\n<p>Let&#8217;s first look at the technique of monitoring constraints during<br \/>\nalgorithm execution and triggering a backtrack when the constraint is<br \/>\nviolated.<\/p>\n<p><a name=\"paritybacktrack\"><\/a><\/p>\n<h4><span class=\"h4\">Parity Constraint Violations<\/span><\/h4>\n<p>I first read about the notion of parity at <a\nhref=\"http:\/\/www.fam-bundgaard.dk\/SOMA\/SOMA.HTM\">Thorleif&#8217;s SOMA page<\/a><br \/>\nwhere in one of his Soma newsletters he references <a\nhref=\"http:\/\/www.fam-bundgaard.dk\/SOMA\/NEWS\/N001203.HTM\">Jotun&#8217;s proof<\/a>.<br \/>\nIt&#8217;s a simple idea:  color each cube in the solution space either black or<br \/>\nwhite in a three dimensional checkerboard pattern and then define the<br \/>\n<i>parity<\/i> of the solution space to be the number of black cubes minus the<br \/>\nnumber of white cubes.  When you place a piece in the solution space, the<br \/>\nnumber of black cubes it fills less the number of white cubes it fills is the<br \/>\nparity of that image.  Suppose that the parity for some image of a piece is 2.<br \/>\nIf you move that piece one position in any ordinal direction, all of its<br \/>\nconstituent cubes flip color and the parity of the piece will become -2.  But<br \/>\nthose would be the only possible parities you could achieve with that piece:<br \/>\neither 2 or -2.  So the magnitude of the parity of a piece is defined by its<br \/>\nshape, but depending where you place the piece, it could be either positive or<br \/>\nnegative.<\/p>\n<p>As you place pieces, the total parity of all placed pieces takes a random<br \/>\nwalk away from an initial parity of zero, but to achieve a solution the random<br \/>\nwalk must end exactly at the parity of the solution space.  It is possible for<br \/>\nthe random walk to get so far from the destination parity that it is no longer<br \/>\npossible to walk back before you run out of pieces.  More generally, you can<br \/>\nget yourself in situations where it&#8217;s just not possible to use the remaining<br \/>\npieces to walk back to exactly the right parity.<\/p>\n<p>It is possible to show that some puzzles can&#8217;t possibly be solved because<br \/>\nthe provided pieces have parities that just can&#8217;t add up to the parity of the<br \/>\nsolution.  As an example, consider again the 35 hexominoes shown in<br \/>\nFigure&nbsp;5.  The total area of these pieces is 35&#215;6 = 210.  It is quite<br \/>\ntempting to try to fit these pieces in a rectangular box.  You could try boxes<br \/>\nmeasuring 14&#215;15, 10&#215;21, 7&#215;30, 6&#215;35, 5&#215;42 or even 3&#215;70.  The parity of all of<br \/>\nthese boxes is 0, so our random parity walk must end at 0.  Of the 35<br \/>\nhexominoes 24 have parity 0 and the other 11 have parity magnitude 2.  Because<br \/>\nthere is no way to take 11 steps of size 2 along a number line and end up back<br \/>\nat 0, there is no way to fit the 35 hexominoes into any rectangular box.<\/p>\n<p>Knowing that certain puzzles can&#8217;t be solved without ever having to try to<br \/>\nsolve them is quite useful, but how can we make more general use of the parity<br \/>\nconstraints to speed up the search for solutions in puzzles?<\/p>\n<p>Knuth attempted to enhance the performance of DLX though the use of parity<br \/>\nconstraints for the case of a one-sided hexiamond puzzle.  The puzzle has four<br \/>\npieces with parity magnitude two (and the rest have parity zero).  The puzzle<br \/>\nas a whole has parity zero, so exactly two of these four pieces must be placed<br \/>\nso their parity is -2 and two must be placed so their parity is 2.  Knuth took<br \/>\nthe approach of dividing this problem into 6 subproblems, one for each way to<br \/>\nchoose the two pieces that will have positive parity.  His expectation was<br \/>\nthat since each of the four pieces were constrained to have half as many<br \/>\nimages, that each subproblem would run 16 times as fast.  Then, the total<br \/>\nwork for all 6 subproblems should be be only 6\/16 of the work to solve the<br \/>\noriginal (unconstrained) problem.  But the total work to solve all 6<br \/>\nsubproblems was actually <i>more<\/i> than the original problem.  (I offer an<br \/>\nexplanation as to why this experiment failed<br \/>\n<a href=\"#filterperformance\">below<\/a>.)<\/p>\n<p>I use a different approach to take advantage of parity constraints: simply<br \/>\nmonitor the parity of the remaining holes in the puzzle and if it ever reaches<br \/>\na value that the remaining pieces cannot achieve, then immediately trigger a<br \/>\nbacktrack.<\/p>\n<p>To implement this parity-based backtracking feature, after each piece<br \/>\nplacement you must determine if the remaining puzzle pieces can be placed to<br \/>\nachieve the parity of the remaining holes in the puzzle.  This may sound<br \/>\ncomputationally expensive, but it&#8217;s not.  Consider the Tetris Cube puzzle as<br \/>\nan example.  Piece A has parity 0, pieces B, E and L have a parity magnitude<br \/>\nof 2, and the remaining eight pieces have a parity magnitude of 1.  We can<br \/>\nimmediately forget about piece A since it has parity 0.  So we have three<br \/>\npieces with parity magnitude 2 and eight pieces with parity magnitude 1.  If<br \/>\nyou look at the parity of the pieces that are left at any given time, there<br \/>\nare only (3+1) x (8+1) = 36 cases.  During puzzle initialization I create a<br \/>\nparity state object for each of these situations.  So, for example, there is a<br \/>\nparity state object that represents the specific case of having three<br \/>\nremaining pieces of parity magnitude 1 and two remaining pieces of parity<br \/>\nmagnitude 2.  In each of these 36 cases, I precalculate the parities that you<br \/>\ncan possibly achieve with that specific combination of pieces.  I store these<br \/>\nresults in a boolean array inside the state object.  So if you know your<br \/>\nparity state, the task of determining if the parity of the remaining holes in<br \/>\nthe puzzle is achievable reduces to an array lookup.  It looks something like<br \/>\nthis:<\/p>\n<pre>\r\n        if ( ! parityState-&gt;parityIsAchievable[parityOfRemainingHoles] )\r\n            \/\/ force a backtrack due to parity violation\r\n        else\r\n            \/\/ parity looks ok so forge on\r\n<\/pre>\n<p>In addition to this boolean array, each parity state object also keeps<br \/>\ntrack of its neighboring states in two arrays indexed by parity.  One array<br \/>\nis called <span class=\"code\">place<\/span> which you use to lookup your new<br \/>\nstate when a piece is placed; and the other is called <span\nclass=\"code\">unplace<\/span> which you use to lookup your new state when a<br \/>\npiece is removed.  The only other task is to update the running sum of the<br \/>\nparity of the remaining holes in the puzzle.  So the processing for a piece<br \/>\nplacement looks like this:<\/p>\n<pre>\r\n        parityState = parityState-&gt;place[parityOfPiecePlaced];\r\n        parityOfRemainigHoles -= parityOfPiecePlaced;\r\n<\/pre>\n<p>and piece removal processing looks like this:<\/p>\n<pre>\r\n        parityOfRemainigHoles += parityOfPieceRemoved;\r\n        parityState = parityState-&gt;unplace[parityOfPieceRemoved];\r\n<\/pre>\n<p>Here, I&#8217;m using a double sided arrays so <span\nclass=\"code\">place[-2]<\/span> and <span class=\"code\">place[2]<\/span> actually<br \/>\ntake you to the same state, saving the trouble of calculating the absolute<br \/>\nvalue of <span class=\"code\">parityOfPiecePlaced<\/span>.<\/p>\n<p>So the cost of parity checking is quite small, but typically parity<br \/>\nviolations do not start to appear until the last few pieces are being placed.<br \/>\nIn the 10&#215;6 pentomino puzzle, the first parity violations did not appear<br \/>\nuntil the 9th piece was placed; and adding the parity backtrack trigger to the<br \/>\nfastest solver configuration for that puzzle actually increased run times by<br \/>\nabout 8%.  (So adding just the above 5 lines of code to the de Bruijn<br \/>\nprocessing loop increased the work to solve the problem by 1 part in 12!<br \/>\nIndeed, even the time required to process the if statements that are<br \/>\nused to see if various algorithm features are turned on, or if trace<br \/>\noutput is enabled, etc, measurably impairs the performance of the<br \/>\nde Bruijn algorithm for this puzzle.)  For the Tetris Cube, parity violations<br \/>\nstarted to appear after only 6 pieces were placed, and use of the parity<br \/>\nmonitor improved performance by about 3%.<\/p>\n<p>This parity backtrack trigger technique leaves the algorithms blinded to<br \/>\nthe true constraints on pieces with non-zero parity; so parity constraints are<br \/>\nonly hit haphazardly as opposed to being actively sought out by the algorithms.<br \/>\nThere is likely some better way to take advantage of the parity constraints on<br \/>\na puzzle.  Thorleif found that for the case of the the Soma cube puzzle,<br \/>\nforcibly placing pieces with non-zero parity first improved performance<br \/>\nmarkedly; but I am skeptical that such an approach would work well in general<br \/>\nbecause typically it&#8217;s so much better to fill holes, rather than place pieces.<br \/>\nOne approach might be to simply assign some fractional weight to the counts<br \/>\nmaintained for piece columns that have non-zero parity.   This would gently<br \/>\ncoax DLX into considering placing them earlier.  I have not pursued such an<br \/>\ninvestigation.<\/p>\n<p><a name=\"figure11\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar boxDiamondParity = '* * * * * * * * * * * @ * * * * * * * * * * *\\n' +\n                       '* * * * * * * * * * @ . @ * * * * * * * * * *\\n' +\n                       '* * * * * * * * * @ . @ . @ * * * * * * * * *\\n' +\n                       '* * * * * * * * @ . @ . @ . @ * * * * * * * *\\n' +\n                       '* * * * * * * @ . @ . @ . @ . @ * * * * * * *\\n' +\n                       '* * * * * * @ . @ . @ . @ . @ . @ * * * * * *\\n' +\n                       '* * * * * @ . @ . @ . @ . @ . @ . @ * * * * *\\n' +\n                       '* * * * @ . @ . @ . @ . @ . @ . @ . @ * * * *\\n' +\n                       '* * * @ . @ . @ . @ . @ . @ . @ . @ . @ * * *\\n' +\n                       '* * @ . @ . * * * * * * * * * * * . @ . @ * *\\n' +\n                       '* @ . @ . @ * * * * * * * * * * * @ . @ . @ *\\n' +\n                       '@ . @ . @ . * * * * * * * * * * * . @ . @ . @\\n' +\n                       '* @ . @ . @ * * * * * * * * * * * @ . @ . @ *\\n' +\n                       '* * @ . @ . * * * * * * * * * * * . @ . @ * *\\n' +\n                       '* * * @ . @ . @ . @ . @ . @ . @ . @ . @ * * *\\n' +\n                       '* * * * @ . @ . @ . @ . @ . @ . @ . @ * * * *\\n' +\n                       '* * * * * @ . @ . @ . @ . @ . @ . @ * * * * *\\n' +\n                       '* * * * * * @ . @ . @ . @ . @ . @ * * * * * *\\n' +\n                       '* * * * * * * @ . @ . @ . @ . @ * * * * * * *\\n' +\n                       '* * * * * * * * @ . @ . @ . @ * * * * * * * *\\n' +\n                       '* * * * * * * * * @ . @ . @ * * * * * * * * *\\n' +\n                       '* * * * * * * * * * @ . @ * * * * * * * * * *\\n' +\n                       '* * * * * * * * * * * @ * * * * * * * * * * *';\n\ndocument.write(puzzleToHtmlTable(boxDiamondParity, hexominoColor, false, hexominoLabel, 'small'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;11.  Checker board pattern for the<br \/>\nbox-in-a-diamond hexomino puzzle.<\/span>  Counting the number of black squares<br \/>\nand subtracting the number of white squares shows the parity of this puzzle to<br \/>\nbe 22, which is the maximum parity a 35 piece hexomino puzzle can possibly<br \/>\nachieve.\n<\/div>\n<p>Still, with the right puzzle, monitoring parity constraints can be more<br \/>\nuseful.  I&#8217;ve reproduced the box-in-a-diamond puzzle layout in Figure&nbsp;11<br \/>\nto call attention to the parity of this puzzle.  I designed this puzzle to<br \/>\nhave the the interesting property that its parity is exactly 22, which is the<br \/>\nmaximum parity the 35 hexomino puzzle pieces can possibly achieve.  Any<br \/>\nsolution to this puzzle requires all eleven hexomino pieces with non-zero<br \/>\nparity to favor black squares.  Figure&nbsp;12 shows one such solution with<br \/>\nthe 11 pieces having non zero parity highlighted.  Monte Carlo estimation<br \/>\ntechniques showed that enabling the parity backtrack trigger on this puzzle<br \/>\nproduces about a two-thirds increase in performance.  Although a substantial<br \/>\nperformance boost, this is less than I would have expected.<\/p>\n<p><a name=\"figure12\"><\/a><\/p>\n<div class=\"centered\" style=\"margin-bottom:10px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar boxDiamondSolution = '* * * * * * * * * * * s * * * * * * * * * * *\\n' +\n                         '* * * * * * * * * * s S s * * * * * * * * * *\\n' +\n                         '* * * * * * * * * P P P S s * * * * * * * * *\\n' +\n                         '* * * * * * * * P P N N N N V * * * * * * * *\\n' +\n                         '* * * * * * * h P h 6 N V V V V * * * * * * *\\n' +\n                         '* * * * * * h H h H 6 N 6 Q Q V Z * * * * * *\\n' +\n                         '* * * * * E E E E X 6 6 6 Q Z Z Z Z * * * * *\\n' +\n                         '* * * * E E X X X X c Q Q Q D Z % 5 % * * * *\\n' +\n                         '* * * k K k X c C c C c D D D D D % 9 9 * * *\\n' +\n                         '* * k K k 3 * * * * * * * * * * * 5 % 9 9 * *\\n' +\n                         '* &#038; 7 3 3 3 * * * * * * * * * * * I 9 9 I o *\\n' +\n                         '&#038; 7 &#038; J 3 3 * * * * * * * * * * * I I I I O o\\n' +\n                         '* &#038; J J 2 2 * * * * * * * * * * * G G o O o *\\n' +\n                         '* * J J 2 2 * * * * * * * * * * * G G G G * *\\n' +\n                         '* * * J 2 2 B B A M M M M F F F T T 1 1 * * *\\n' +\n                         '* * * * $ 4 $ B A M R F F F T T T 1 1 * * * *\\n' +\n                         '* * * * * $ 4 B A M R u U u T y 1 1 * * * * *\\n' +\n                         '* * * * * * $ B A R R R u Y y Y y * * * * * *\\n' +\n                         '* * * * * * * B A L L R U 8 8 y * * * * * * *\\n' +\n                         '* * * * * * * * A L w W u 8 8 * * * * * * * *\\n' +\n                         '* * * * * * * * * L L w 8 8 * * * * * * * * *\\n' +\n                         '* * * * * * * * * * L W w * * * * * * * * * *\\n' +\n                         '* * * * * * * * * * * w * * * * * * * * * * *';\n\ndocument.write(puzzleToHtmlTable(boxDiamondSolution, hexominoColor, true, hexominoLabel, 'small'));\n\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;12.  A solution to the box-in-a-diamond<br \/>\nhexomino puzzle.<\/span>  The 11 non-zero parity pieces are marked with &#9632;<br \/>\nsymbols.\n<\/div>\n<p><a name=\"volumebacktrack\"><\/a><\/p>\n<h4><span class=\"h4\">Volume Constraint Violations<\/span><\/h4>\n<p>The volume backtrack trigger, when enabled, performs the following<br \/>\nprocessing after each piece placed:<\/p>\n<ol>\n<li>scans the open space of the puzzle, measuring the volume of each partition<br \/>\nit finds, and<\/li>\n<li>triggers a backtrack if a volume is discovered that cannot be achieved by<br \/>\nthe remaining pieces.<\/li>\n<\/ol>\n<p>To find and measure the volumes of subspaces in step 1, I use a simple fill<br \/>\nalgorithm.  Step 2 of the problem &mdash; determining whether a particular<br \/>\nvolume is achievable &mdash; is easy if all pieces have the same size; but to<br \/>\nhandle the problem generally (when pieces are not all the same size) I use the<br \/>\nsame technique used by the parity monitor above:  I precalculate the<br \/>\nachievable volumes for each possible grouping of remaining pieces and track<br \/>\nthe group as a state variable.<\/p>\n<p>The solver allows you to configure the minimum number of remaining pieces<br \/>\nrequired to perform volume backtrack processing.  As long as you turn off the<br \/>\nvolume backtrack feature sufficiently early, its cost is insignificant.<\/p>\n<p>I originally implemented this backtrack trigger to keep DLX from<br \/>\npartitioning polyomino puzzles into unfillable volumes while it wandered about<br \/>\nthe puzzle pursuing constrained holes or pieces; but I now believe it&#8217;s often<br \/>\nbetter to initially follow a simple packing strategy that precludes the<br \/>\ncreation of isolated volumes.  I think this backtrack trigger may still be<br \/>\nuseful for some puzzles once the min-fit heuristic is enabled, but I have not<br \/>\nhad the time to study its effects.<\/p>\n<p><a name=\"imagefilter\"><\/a><\/p>\n<h3><span class=\"h3\">Image Filters<\/span><\/h3>\n<p>In the previous sections we examined the technique of monitoring a constraint<br \/>\nduring algorithm execution and triggering a backtrack when the constraint is<br \/>\nviolated.  Another (more aggressive) way you can take advantage of a<br \/>\nconstraint is to check all images one-by-one to see if using them would result<br \/>\nin a constraint violation.  For each image that causes a violation, simply<br \/>\nremove it from the cache of available images.  Some of the image filters<br \/>\ndiscussed below are applied only once before the algorithms begin.  Other<br \/>\nimage filers can be applied repeatedly (after each piece placement).  In my<br \/>\nsolver, image filters can only be applied when DLX is active because the<br \/>\nlinked list structure of DLX makes it easy to remove and replace images at<br \/>\neach algorithmic step.<\/p>\n<p><a name=\"boundsfilter\"><\/a><\/p>\n<h4><span class=\"h4\">Puzzle Bounds Constraint Violations<\/span><\/h4>\n<p>N.G. de Bruijn&#8217;s original software used to solve the 10&#215;6 pentomino problem<br \/>\npredefined the layouts of the 12 puzzle pieces in each of their unique<br \/>\norientations.  There are 63 unique orientations of the pieces in total, but<br \/>\nthe various possible translations of these orientations were not<br \/>\nprecalculated.  This was a simple approach, and perhaps more importantly (in<br \/>\nthose days) made for a quite small program.  This results, however, in the de<br \/>\nBruijn algorithm spending a lot of time checking fits for images that clearly<br \/>\nfall outside the 10&#215;6 box.  These days, memory is cheap, so it is easy to<br \/>\nimprove on this basic approach.  I&#8217;ve already explained the technique in the<br \/>\nsection on MCH above:  for MCH I keep at each<br \/>\n<span class=\"code\">GridPoint<\/span> a separate list for each piece which holds<br \/>\nonly those images of a piece that both fill the hole <i>and<\/i> actually fit<br \/>\nin the puzzle box.  I&#8217;ve done exactly the same thing for the de Bruijn<br \/>\nalgorithm:  I created another array of image lists at each <span\nclass=\"code\">GridPoint<\/span>, each list holding only the images of a<br \/>\nparticular piece that fill the hole with its root tiling node and also fit in<br \/>\nthe puzzle box.  This completely eliminates all processing associated with<br \/>\nplacement attempts for images that don&#8217;t even fit in the solution box.<\/p>\n<p>By filtering out images that don&#8217;t fit in the box, the average number of de<br \/>\nBruijn images at each hole in the 10&#215;6 pentomino puzzle drops from 63 to 33.87<br \/>\n&#8212; an almost 50% reduction.  This should translate to a significant<br \/>\nperformance boost, though I can&#8217;t say for sure since this is the only way I&#8217;ve<br \/>\never implemented the algorithm.<\/p>\n<p><a name=\"redundancyfilter\"><\/a><\/p>\n<h4><span class=\"h4\">Rotational Redundancy Constraint Violations<\/span><\/h4>\n<p>If you picked up a Tetris Cube when it was already solved; turned it on its<br \/>\nside; and then excitedly told your brother you found a new solution, you&#8217;d<br \/>\nlikely get thumped.  Because the puzzle box is cubic, there are actually 23<br \/>\nways to rotate any solution to produce a new solution that is of the same<br \/>\nshape as the original.  My software can filter out solutions that are just<br \/>\nrotated copies of previously discovered solutions (just enable the <span\nclass=\"code\">&#8211;unique<\/span> command line option), but the search algorithms<br \/>\nas described so far do actually find all 24 rotations of every solution (only<br \/>\nto have 23 of them filtered out).<\/p>\n<p>If by imperial decree, we only allow rotationally unique solutions, then it<br \/>\nis possible to produce an image filter to take advantage of this constraint.<br \/>\nIf we simply fix the orientation of a piece that has 24 unique orientations,<br \/>\nthen the algorithms will only find rotationally unique solutions.  Why does<br \/>\nthis work?  If you fix the orientation of a piece, any solution you find is<br \/>\ngoing to have that constrained piece in its fixed orientation; and the other<br \/>\n23 rotations of that same solution cannot possibly be found because those<br \/>\nsolutions have the constrained piece in some orientation that you never<br \/>\nallowed to enter the box.  Application of just this one filter reduced the<br \/>\ntime it takes DLX to find all solutions to the Tetris Cube from over<br \/>\nseven hours down to about 20 minutes.  Quite useful indeed.<\/p>\n<p>It is possible to apply this same technique to puzzles that are not cubic;<br \/>\nbut instead of keeping the orientation of the piece completely fixed, you<br \/>\nlimit the set of rotations allowed.<\/p>\n<p>But what if all of the pieces have fewer unique rotations than the<br \/>\npuzzle has symmetric rotations?  In this case you can also try constraining<br \/>\nthe translations of the piece within the solution box.  This is slightly<br \/>\nharder to do (it was for me anyway), and is not always guaranteed to eliminate<br \/>\nall rotationally redundant solutions from the search.  As an example try<br \/>\neliminating the rotationally redundant solutions from a 3x3x3 puzzle by<br \/>\nconstraining a puzzle piece that is a 1x1x1 cube.  It can&#8217;t be done.  The best<br \/>\nyou can do is to constrain the piece to appear at one of four places:  the<br \/>\ncenter, the center of a face, the center of an edge and at a corner.  This<br \/>\nwill eliminate some rotationally redundant solutions from the search, but not<br \/>\nall.<\/p>\n<p>A much harder problem is to try to eliminate rotationally redundant<br \/>\nsolutions from the search when none of the pieces in the puzzle have a unique<br \/>\nshape.  In this case, you can&#8217;t simply constrain a single piece, but must<br \/>\ninstead somehow constrain in concert an entire set of pieces that share the<br \/>\nsame shape.  I have some rough ideas on how one might algorithmically approach<br \/>\nthis problem, but I have not yet tried to work the problem out in detail.<\/p>\n<p>For now, you can ask my solver to constrain any uniquely shaped piece so as<br \/>\nto eliminate as many rotationally redundant solutions as possible.  But even<br \/>\nbetter, you can ask the solver to pick the piece to constrain.  In this case<br \/>\nit compares the results of constraining each uniquely shaped puzzle piece and<br \/>\npicks the piece that will do the best job of eliminating rotationally<br \/>\nredundant solutions.  If two or more pieces tie, then it will pick the piece<br \/>\nthat after constraint has the fewest images that fit in the puzzle box.  If<br \/>\nfor example you ask my solver to pick a piece for constraint on the 10&#215;6<br \/>\npentomino puzzle, it will pick X (the piece that looks like a plus sign), and<br \/>\nconstrain it so that it can only appear in the lower-left quadrant of the box.<br \/>\nThis is exactly the approach de Bruijn took when he solved the 10&#215;6 pentomino<br \/>\npuzzle 40 years ago, but de Bruijn identified this as the best constraint<br \/>\npiece through manual analysis of the puzzle and programmed it as a special<br \/>\ninitial condition in his software.  With my solver, you need only add the<br \/>\noption <span class=\"code\">-r<\/span> to the command line.<\/p>\n<p>Often times a piece that has been constrained will have so few remaining<br \/>\nimages that it becomes the best candidate for the first algorithm step.  But<br \/>\nof the algorithms I&#8217;ve implemented, only DLX will consider the option of<br \/>\niterating over the images of a single piece.  So when running my solver with a<br \/>\npiece constraint I usually use the DLX algorithm with a min-fit heuristic for<br \/>\nat least the first piece placement.  For the 10&#215;6 pentomino problem, if you<br \/>\nturn on constraint processing (which constrains the images of the X piece),<br \/>\nbut fail to use DLX for the first piece placement you&#8217;ll find the run time to<br \/>\nbe eight times longer.<\/p>\n<p>This feature was far and away the most difficult part of the solver for me<br \/>\nto design and implement.  (Perhaps some formal education in the field of<br \/>\nspatial modeling would have been useful.)  I have copious comments on the<br \/>\napproach in the software.  There are two parts to the problem:  I first<br \/>\nidentify which rotations of the puzzle box as a whole produce a new puzzle box<br \/>\nof exactly the same shape.  This is normally a trivial problem, but the solver<br \/>\nalso handles situations where some of the puzzle pieces are loaded into fixed<br \/>\npositions.  If some of those pieces have a shape in common with pieces that<br \/>\nare free to move about, then things get tricky.  One-sided polyomino problems<br \/>\n(which the solver also handles) also add complexity.  Once I know the set of<br \/>\nrotations that when applied to the puzzle can possibly result in a completely<br \/>\nsymmetric shape, I apply a second algorithm that filters the images produced<br \/>\nfor a (uniquely shaped) piece through a combination of rotational and\/or<br \/>\ntranslational constraints that eliminate these symmetries and has the net<br \/>\neffect of preventing the algorithms from discovering rotationally redundant<br \/>\nsolutions.  For a more exacting description of these techniques, please read<br \/>\nmy software comments for the methods<br \/>\n<span class=\"code\">Puzzle::initSymmetricRotationAndPermutationLists()<\/span><br \/>\nand for <span class=\"code\">Puzzle::genImageLists()<\/span>.<\/p>\n<p><a name=\"parityfilter\"><\/a><\/p>\n<h4><span class=\"h4\">Parity Constraint Violations<\/span><\/h4>\n<p>You can also filter images based on parity constraints.  So instead of<br \/>\nwaiting around for an image to be placed to trigger a parity backtrack; after<br \/>\neach piece placement, you can look at the parity of each remaining image and<br \/>\ndetermine if placing that image would introduce a parity violation; and if so,<br \/>\nremove the image.<\/p>\n<p>Of course I don&#8217;t actually do the check for all images &mdash; only twice<br \/>\nfor each remaining piece with non-zero parity (once for positive parity and<br \/>\nonce for negative parity).  If a violation would be introduced through the use<br \/>\nof that piece when its parity is, say, negative, then I traverse the list of<br \/>\nimages for that piece and remove all the copies that have a negative parity.<br \/>\nAlso, the parity filter is skipped completely if the parity of the last piece<br \/>\nplaced was zero:  nothing has changed in that case and it&#8217;s pointless to look<br \/>\nfor new potential parity violations.<\/p>\n<p>Applying the parity filter to the box-in-a-diamond puzzle causes the solver<br \/>\nto filter out roughly half of the images of eleven pieces before DLX even<br \/>\nstarts.  Replacing the parity backtrack trigger with the parity filter for<br \/>\nthis puzzle increased performance by more than 40%.  In total, the solver<br \/>\nrunning with the parity filter generates solutions 2.4 times as fast as it<br \/>\ndoes without any parity constraint-based checks at all.<\/p>\n<p><a name=\"volumefilter\"><\/a><\/p>\n<h4><span class=\"h4\">Volume Constraint Violations<\/span><\/h4>\n<p>You can also use volume constraints to filter images.  This is very much<br \/>\nakin to using volume constraints to trigger backtracks, but instead of waiting<br \/>\naround for an image to be placed that partitions the open space; you can<br \/>\ninstead, one-by-one, place all remaining images in the puzzle and perform a<br \/>\nvolume check operation.  This can be particularly useful as an initial step<br \/>\nbefore you even set the algorithms to working.  Of the 2056 images that fit in<br \/>\nthe 10&#215;6 pentomino puzzle box, 128 of them are jammed up against a side or into a<br \/>\ncorner in such a way as to produce a little confined area that can&#8217;t possibly<br \/>\nbe filled as seen in Figure&nbsp;13.  Searching for and eliminating these<br \/>\nimages up front improved my best run times for this puzzle by about 13%.  This<br \/>\nis the only technique I&#8217;ve found (other than the puzzle bounds filter<br \/>\ndiscussed above) that actually improved performance for this classic<br \/>\npuzzle.<\/p>\n<p><a name=\"figure13\"><\/a><\/p>\n<div class=\"centered puzzle\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar pentominoVolume = '. . . L . . . . X .\\n' +\n                      'L L L L . . . X X X\\n' +\n                      '. . . . . . . . X .\\n' +\n                      'V V V . . . . . . .\\n' +\n                      '. . V . U U U . . .\\n' +\n                      '. . V . U . U . . .';\n\ndocument.write(puzzleToHtmlTable(pentominoVolume, pentominoColor, false, {}, 'big'));\n\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;13.  Volume constraint violations in the<br \/>\n10&#215;6 pentomino puzzle.<\/span>  128 of the 2056 pentomino images (over 5%)<br \/>\nproduce volume constraint violations.  The volume constraint filter can<br \/>\nexpunge these from the image set before the algorithmic search for solutions<br \/>\nbegins.\n<\/div>\n<p>The previous polyomino puzzles were all based on <i>free<\/i> polyominoes:<br \/>\npolyomino pieces that you are free to not only rotate in the plane of the<br \/>\npuzzle, but are also free to flip up side down; but there is another class of<br \/>\npuzzles based on <i>one-sided<\/i> polyominoes: polyomino pieces that you are<br \/>\nallowed to rotate within the plane, but are not allowed to flip up-side-down.<br \/>\nWhere there are only twelve free pentominoes, there are eighteen uniquely<br \/>\nshaped one-sided pentominoes.  Consider the problem of placing the<br \/>\neighteen one-sided pentominoes into a 30&#215;3 box as shown in Figure&nbsp;14.<br \/>\nBecause pieces can actually reach from one long wall of this puzzle box to the<br \/>\nother, 40% of the images (776 out of 1936) that fit in this box produce<br \/>\nunfillable volumes.  (See Figure&nbsp;15.)  Applying the volume constraint<br \/>\nfilter to the images of this puzzle improved performance by about a factor of<br \/>\nnine.<\/p>\n<p><a name=\"figure14\"><\/a><\/p>\n<div class=\"centered puzzle\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar oneSidedPentominoPuzzle = 'L L L L V T I I I I I G S S Q Q Q F F W W Z Z B B B B X U U\\n' +\n                              'L M M M V T T T Y G G G S J Q Q F F P P W W Z N N B X X X U\\n' +\n                              'M M V V V T Y Y Y Y G S S J J J J F P P P W Z Z N N N X U U';\n\ndocument.write(puzzleToHtmlTable(oneSidedPentominoPuzzle, pentominoColor, false, {}, 'small'));\n\n\/* ]]> *\/\n<\/script>\n<\/div>\n<p><a name=\"figure15\"><\/a><\/p>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;14.  One solution to the 30&#215;3 one-sided<br \/>\npentomino puzzle.<\/span>\n<\/div>\n<div class=\"centered puzzle\" style=\"margin-top:20px;\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar oneSidedPentominoVolume = '. * . Z Z * . * . * . * . * . * . * . * . * . * . * . * . *\\n' +\n                              '* . * . Z . * . * . * . * . * . * . * . * . * . * . * . * .\\n' +\n                              '. * . * Z Z . * . * . * . * . * . * . * . * . * . * . * . *';\n\ndocument.write(puzzleToHtmlTable(oneSidedPentominoVolume, pentominoColor, false, {}, 'small'));\n\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;15.  A volume constraint violation in the<br \/>\n30&#215;3 one-sided pentomino puzzle.<\/span>  No matter how you rotate the Z piece,<br \/>\nit will always partition the puzzle box.  Roughly 4 out of 5 of these images<br \/>\nresult in a volume constraint violation.\n<\/div>\n<p>Consider next another puzzle I came across at<br \/>\n<a href=\"http:\/\/www.xs4all.nl\/~gp\/PolyominoSolver\/Polyomino.html\"> Gerard&#8217;s<br \/>\nPolyomino Solution Page<\/a>: placing the 108 free heptominoes into a 33&#215;23 box<br \/>\nwith 3 symmetrically spaced holes left over as shown in Figure&nbsp;16.  One<br \/>\nof the heptomino pieces has the shape of a doughnut with a corner bit out of<br \/>\nit.  This piece is shown in red in Figure&nbsp;16.  There&#8217;s no way for another<br \/>\npiece to fill this hole, so heptomino puzzles always leave at least one<br \/>\nunfilled hole.  To solve this puzzle, the doughnut piece clearly must be<br \/>\nplaced around one of these holes; but none of the algorithms are smart enough<br \/>\nto take advantage of this constraint and will only place the doughnut around a<br \/>\nhole by chance.  And this could take a very long time indeed!  Applying the<br \/>\nvolume constraint filter to this problem, removes not only the images that<br \/>\nproduce confined spaces around the perimeter of the puzzle, but also<br \/>\n<i>all<\/i> images of the doughnut piece except those few that wrap one of the<br \/>\nprescribed holes.  The DLX min-fit heuristic will then correctly recognize the<br \/>\ntrue inflexibility of this piece and place it first.<\/p>\n<p><a name=\"figure16\"><\/a><\/p>\n<div class=\"centered puzzle\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar heptomino = '02 0D 0D 0D 0D 0D 20 20 20 20 20 21 21 35 35 35 35 35 35 57 6C 6C 6C 6C 4A 48 48 48 48 5B 5B 5B 5B\\n' +\n                '02 02 0D 0C 0C 0D 14 20 21 21 21 21 27 35 4E 4E 4E 4E 57 57 57 57 57 6C 4A 4A 4A 4A 48 5C 5B 5B 49\\n' +\n                '03 02 02 02 0C 0C 14 20 16 16 21 27 27 27 27 27 26 4E 4E 3E 45 45 57 6C 6C 67 4A 48 48 5C 49 5B 49\\n' +\n                '03 08 02 0C 0C 0C 14 16 16 16 16 27 1F 26 26 26 26 26 4E 3E 3E 45 67 67 67 67 4A 64 64 5C 49 49 49\\n' +\n                '03 08 08 08 14 14 14 14 19 16 1F 1F 1F 1F 2E 38 26 38 38 3E 45 45 45 67 5E 67 64 64 5C 5C 5C 49 54\\n' +\n                '03 03 03 08 08 08 19 19 19 19 1F 1F 22 2E 2E 38 38 38 3E 3E 44 44 45 44 5E 5E 5E 64 5C 62 62 62 54\\n' +\n                '04 03 23 23 23 23 23 19 0F 19 22 22 22 1D 2E 2E 2E 38 34 3E 3C 44 44 44 5E 5F 5E 64 64 62 54 54 54\\n' +\n                '04 23 23 6A 6A 6A 0F 0F 0F 22 22 22 1D 1D 1D 1D 2E 34 34 34 3C 53 53 44 5E 5F 5F 5F 5F 62 62 54 66\\n' +\n                '04 04 04 6A 09 6A 0F 25 25 25 25 25 32 1D 3B 1D 3D 34 3C 3C 3C 3C 53 53 53 53 5A 4C 5F 4C 62 54 66\\n' +\n                '04 04 6A 6A 09 0F 0F 25 13 13 32 25 32 3B 3B 3B 3D 34 34 2C 3C 60 60 60 60 53 5A 4C 5F 4C 66 66 66\\n' +\n                '09 09 09 09 09 3A 3A 13 13 13 32 32 32 3B 3B 3D 3D 3D 3D 2C 2C 52 60 6B 60 5A 5A 4C 4C 4C 66 66 46\\n' +\n                '2A 2A 2A 2A 3A  * 3A 13 13 1A 32 1A 1A 3B 2D 3D  * 2C 2C 2C 52 52 60 6B 5A 5A 58  * 58 40 40 46 46\\n' +\n                '2A 07 07 2A 3A 3A 3A 1E 1E 1A 1A 1A 2D 2D 2D 2D 2D 2D 2C 52 52 52 6B 6B 6B 5A 58 58 58 40 40 40 46\\n' +\n                '2A 07 07 07 0E 1E 1E 1E 1E 1E 1A 24 24 24 33 33 33 31 31 52 31 31 6B 50 6B 69 58 5D 5D 5D 40 46 46\\n' +\n                '07 07 06 06 0E 15 15 15 15 15 24 24 24 24 59 59 33 33 31 31 31 50 50 50 50 69 58 56 5D 51 40 51 46\\n' +\n                '06 06 06 0E 0E 0E 0E 15 1B 15 1B 1B 59 59 59 41 41 33 33 41 50 50 69 69 69 69 56 56 5D 51 51 51 61\\n' +\n                '06 05 12 12 12 0E 12 1C 1B 1B 1B 1B 59 59 2B 2B 41 41 41 41 55 55 55 69 56 56 56 43 5D 51 61 51 61\\n' +\n                '06 05 05 05 12 12 12 1C 1C 1C 1C 1C 2B 2B 2B 2B 30 55 55 55 55 4F 4B 4B 56 68 43 43 5D 61 61 61 61\\n' +\n                '05 05 05 0A 0A 10 10 11 11 37 37 1C 2B 29 29 29 30 4F 4F 4F 4F 4F 4B 68 68 68 68 43 43 65 65 65 65\\n' +\n                '01 01 01 0A 0A 10 10 10 11 37 37 37 37 29 30 30 30 30 30 4F 4D 4D 4B 4B 39 42 68 43 47 3F 3F 63 65\\n' +\n                '01 01 0A 0A 0A 10 10 11 11 37 17 29 29 29 2F 2F 2F 2F 4D 4D 4D 4B 4B 39 39 42 68 43 47 3F 63 63 65\\n' +\n                '01 0B 0B 0B 0B 0B 11 11 17 17 17 17 17 2F 2F 28 2F 4D 4D 36 36 36 39 39 42 42 42 47 47 3F 63 63 65\\n' +\n                '01 0B 0B 18 18 18 18 18 18 18 17 28 28 28 28 28 28 36 36 36 36 39 39 42 42 47 47 47 3F 3F 3F 63 63';\n\n\nvar noLabel = {};\n\nvar heptominoLabel = {};\nheptominoLabel['01'] = '01';\nheptominoLabel['02'] = '02';\nheptominoLabel['03'] = '03';\nheptominoLabel['04'] = '04';\nheptominoLabel['05'] = '05';\nheptominoLabel['06'] = '06';\nheptominoLabel['07'] = '07';\nheptominoLabel['08'] = '08';\nheptominoLabel['09'] = '09';\nheptominoLabel['0A'] = '0A';\nheptominoLabel['0B'] = '0B';\nheptominoLabel['0C'] = '0C';\nheptominoLabel['0D'] = '0D';\nheptominoLabel['0E'] = '0E';\nheptominoLabel['0F'] = '0F';\nheptominoLabel['10'] = '10';\nheptominoLabel['11'] = '11';\nheptominoLabel['12'] = '12';\nheptominoLabel['13'] = '13';\nheptominoLabel['14'] = '14';\nheptominoLabel['15'] = '15';\nheptominoLabel['16'] = '16';\nheptominoLabel['17'] = '17';\nheptominoLabel['18'] = '18';\nheptominoLabel['19'] = '19';\nheptominoLabel['1A'] = '1A';\nheptominoLabel['1B'] = '1B';\nheptominoLabel['1C'] = '1C';\nheptominoLabel['1D'] = '1D';\nheptominoLabel['1E'] = '1E';\nheptominoLabel['1F'] = '1F';\nheptominoLabel['20'] = '20';\nheptominoLabel['21'] = '21';\nheptominoLabel['22'] = '22';\nheptominoLabel['23'] = '23';\nheptominoLabel['24'] = '24';\nheptominoLabel['25'] = '25';\nheptominoLabel['26'] = '26';\nheptominoLabel['27'] = '27';\nheptominoLabel['28'] = '28';\nheptominoLabel['29'] = '29';\nheptominoLabel['2A'] = '2A';\nheptominoLabel['2B'] = '2B';\nheptominoLabel['2C'] = '2C';\nheptominoLabel['2D'] = '2D';\nheptominoLabel['2E'] = '2E';\nheptominoLabel['2F'] = '2F';\nheptominoLabel['30'] = '30';\nheptominoLabel['31'] = '31';\nheptominoLabel['32'] = '32';\nheptominoLabel['33'] = '33';\nheptominoLabel['34'] = '34';\nheptominoLabel['35'] = '35';\nheptominoLabel['36'] = '36';\nheptominoLabel['37'] = '37';\nheptominoLabel['38'] = '38';\nheptominoLabel['39'] = '39';\nheptominoLabel['3A'] = '3A';\nheptominoLabel['3B'] = '3B';\nheptominoLabel['3C'] = '3C';\nheptominoLabel['3D'] = '3D';\nheptominoLabel['3E'] = '3E';\nheptominoLabel['3F'] = '3F';\nheptominoLabel['40'] = '40';\nheptominoLabel['41'] = '41';\nheptominoLabel['42'] = '42';\nheptominoLabel['43'] = '43';\nheptominoLabel['44'] = '44';\nheptominoLabel['45'] = '45';\nheptominoLabel['46'] = '46';\nheptominoLabel['47'] = '47';\nheptominoLabel['48'] = '48';\nheptominoLabel['49'] = '49';\nheptominoLabel['4A'] = '4A';\nheptominoLabel['4B'] = '4B';\nheptominoLabel['4C'] = '4C';\nheptominoLabel['4D'] = '4D';\nheptominoLabel['4E'] = '4E';\nheptominoLabel['4F'] = '4F';\nheptominoLabel['50'] = '50';\nheptominoLabel['51'] = '51';\nheptominoLabel['52'] = '52';\nheptominoLabel['53'] = '53';\nheptominoLabel['54'] = '54';\nheptominoLabel['55'] = '55';\nheptominoLabel['56'] = '56';\nheptominoLabel['57'] = '57';\nheptominoLabel['58'] = '58';\nheptominoLabel['59'] = '59';\nheptominoLabel['5A'] = '5A';\nheptominoLabel['5B'] = '5B';\nheptominoLabel['5C'] = '5C';\nheptominoLabel['5D'] = '5D';\nheptominoLabel['5E'] = '5E';\nheptominoLabel['5F'] = '5F';\nheptominoLabel['60'] = '60';\nheptominoLabel['61'] = '61';\nheptominoLabel['62'] = '62';\nheptominoLabel['63'] = '63';\nheptominoLabel['64'] = '64';\nheptominoLabel['65'] = '65';\nheptominoLabel['66'] = '66';\nheptominoLabel['67'] = '67';\nheptominoLabel['68'] = '68';\nheptominoLabel['69'] = '69';\nheptominoLabel['6A'] = '6A';\nheptominoLabel['6B'] = '6B';\nheptominoLabel['6C'] = '6C';\n\n\nvar heptominoColor = {};\nheptominoColor['01'] = 'blue';\nheptominoColor['02'] = 'yellow';\nheptominoColor['03'] = 'blue';\nheptominoColor['04'] = 'purple';\nheptominoColor['05'] = 'purple';\nheptominoColor['06'] = 'green';\nheptominoColor['07'] = 'yellow';\nheptominoColor['08'] = 'green';\nheptominoColor['09'] = 'yellow';\nheptominoColor['0A'] = 'green';\nheptominoColor['0B'] = 'yellow';\nheptominoColor['0C'] = 'blue';\nheptominoColor['0D'] = 'green';\nheptominoColor['0E'] = 'blue';\nheptominoColor['0F'] = 'blue';\nheptominoColor['10'] = 'purple';\nheptominoColor['11'] = 'green';\nheptominoColor['12'] = 'yellow';\nheptominoColor['13'] = 'blue';\nheptominoColor['14'] = 'yellow';\nheptominoColor['15'] = 'green';\nheptominoColor['16'] = 'blue';\nheptominoColor['17'] = 'yellow';\nheptominoColor['18'] = 'blue';\nheptominoColor['19'] = 'purple';\nheptominoColor['1A'] = 'green';\nheptominoColor['1B'] = 'blue';\nheptominoColor['1C'] = 'purple';\nheptominoColor['1D'] = 'blue';\nheptominoColor['1E'] = 'yellow';\nheptominoColor['1F'] = 'green';\nheptominoColor['20'] = 'purple';\nheptominoColor['21'] = 'yellow';\nheptominoColor['22'] = 'yellow';\nheptominoColor['23'] = 'yellow';\nheptominoColor['24'] = 'yellow';\nheptominoColor['25'] = 'green';\nheptominoColor['26'] = 'blue';\nheptominoColor['27'] = 'purple';\nheptominoColor['28'] = 'green';\nheptominoColor['29'] = 'green';\nheptominoColor['2A'] = 'green';\nheptominoColor['2B'] = 'yellow';\nheptominoColor['2C'] = 'purple';\nheptominoColor['2D'] = 'blue';\nheptominoColor['2E'] = 'purple';\nheptominoColor['2F'] = 'blue';\nheptominoColor['30'] = 'purple';\nheptominoColor['31'] = 'green';\nheptominoColor['32'] = 'yellow';\nheptominoColor['33'] = 'purple';\nheptominoColor['34'] = 'yellow';\nheptominoColor['35'] = 'blue';\nheptominoColor['36'] = 'blue';\nheptominoColor['37'] = 'blue';\nheptominoColor['38'] = 'green';\nheptominoColor['39'] = 'green';\nheptominoColor['3A'] = 'red';\nheptominoColor['3B'] = 'purple';\nheptominoColor['3C'] = 'green';\nheptominoColor['3D'] = 'green';\nheptominoColor['3E'] = 'blue';\nheptominoColor['3F'] = 'blue';\nheptominoColor['40'] = 'blue';\nheptominoColor['41'] = 'blue';\nheptominoColor['42'] = 'yellow';\nheptominoColor['43'] = 'purple';\nheptominoColor['44'] = 'yellow';\nheptominoColor['45'] = 'purple';\nheptominoColor['46'] = 'green';\nheptominoColor['47'] = 'green';\nheptominoColor['48'] = 'blue';\nheptominoColor['49'] = 'yellow';\nheptominoColor['4A'] = 'green';\nheptominoColor['4B'] = 'purple';\nheptominoColor['4C'] = 'green';\nheptominoColor['4D'] = 'yellow';\nheptominoColor['4E'] = 'yellow';\nheptominoColor['4F'] = 'blue';\nheptominoColor['50'] = 'purple';\nheptominoColor['51'] = 'yellow';\nheptominoColor['52'] = 'yellow';\nheptominoColor['53'] = 'blue';\nheptominoColor['54'] = 'purple';\nheptominoColor['55'] = 'yellow';\nheptominoColor['56'] = 'yellow';\nheptominoColor['57'] = 'green';\nheptominoColor['58'] = 'purple';\nheptominoColor['59'] = 'green';\nheptominoColor['5A'] = 'yellow';\nheptominoColor['5B'] = 'green';\nheptominoColor['5C'] = 'purple';\nheptominoColor['5D'] = 'green';\nheptominoColor['5E'] = 'green';\nheptominoColor['5F'] = 'purple';\nheptominoColor['60'] = 'purple';\nheptominoColor['61'] = 'blue';\nheptominoColor['62'] = 'blue';\nheptominoColor['63'] = 'yellow';\nheptominoColor['64'] = 'yellow';\nheptominoColor['65'] = 'green';\nheptominoColor['66'] = 'yellow';\nheptominoColor['67'] = 'blue';\nheptominoColor['68'] = 'blue';\nheptominoColor['69'] = 'green';\nheptominoColor['6A'] = 'green';\nheptominoColor['6B'] = 'blue';\nheptominoColor['6C'] = 'yellow';\n\ndocument.write(puzzleToHtmlTable(heptomino, heptominoColor, true, noLabel, 'small'));\n\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;16.  Solution to a 33&#215;23 heptomino problem<br \/>\nwith 3 symmetrically spaced holes.<\/span>  The piece highlighted in red must be<br \/>\nplaced around one of these holes.  All other images of this piece are nicely<br \/>\neliminated by the volume constraint filter.\n<\/div>\n<p>For 3-D puzzles, I think it would be rare for pieces to construct a planar<br \/>\nbarrier isolating two volumes large enough to cause serious trouble;<br \/>\naccordingly, I have not studied the effects of this filter on 3-D puzzles.<\/p>\n<p>In all of these examples I&#8217;ve only applied the volume filter once to the<br \/>\ninitial image set (prior to algorithm execution), but you can also apply the<br \/>\nfilter repeatedly, after each step in the algorithm (turning it off when the<br \/>\nnumber of remaining pieces reaches some prescribed threshold).  This should<br \/>\nhave the effect of giving DLX a better view of the puzzle constraints; but I<br \/>\nhaven&#8217;t studied this primarily because my current implementation of the filter<br \/>\nis so inefficient:  at each algorithmic step each remaining image is<br \/>\ntemporarily placed and a graphical fill operation is performed to detect<br \/>\nisolated volumes.  This is simple, but the vast majority of these image checks<br \/>\nare pointless.  The next time I work on this project, I&#8217;ll be improving the<br \/>\nimplementation of this filter which I hope will offer performance benefits<br \/>\nwhen reapplied after each piece placement.<\/p>\n<p><a name=\"fitfilter\"><\/a><\/p>\n<h4><span class=\"h4\">Fit Constraint Violations<\/span><\/h4>\n<p>Another filter I&#8217;ve implemented is based on a next-step fit constraint.  By<br \/>\nthis I mean, if placing an image would result in either a hole that can&#8217;t be<br \/>\nfilled, or a piece that can&#8217;t be placed, then it is pointless to include that<br \/>\nimage in the image set.  Running this fit filter on the 2056 images of the<br \/>\n10&#215;6 pentomino puzzle finds all of the 128 images found by the volume<br \/>\nconstraint filter plus an additional 16 images like those shown in<br \/>\nFigure&nbsp;17.  There can obviously be no puzzle solution with these piece<br \/>\nplacements.  If the rotational redundancy filter is also enabled (which<br \/>\nconstrains the X piece to 8 possible positions in the lower left quadrant of<br \/>\nthe box), then the fit filter will eliminate 227 images.  (There are numerous<br \/>\nimages that conflict with <i>all<\/i> of the constrained placements of the X<br \/>\npiece.)<\/p>\n<p><a name=\"figure17\"><\/a><\/p>\n<div class=\"centered puzzle\">\n<script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar nofit = '. . . . . . . . . .\\n' +\n            'I I I I I . . . L .\\n' +\n            '. . . . . . . . L .\\n' +\n            '. . . . . . . . L .\\n' +\n            '. . . . . . . . L L\\n' +\n            '. . . . . . . . . .';\n\ndocument.write(puzzleToHtmlTable(nofit, pentominoColor, false, {}, 'big'));\n\/* ]]> *\/\n<\/script>\n<\/div>\n<div class=\"caption\">\n<span class=\"heading\">Figure&nbsp;17.  Samples of two images expunged by the<br \/>\nfit filter for the 10&#215;6 pentomino puzzle.<\/span>  These images of the I and L<br \/>\npentomino pieces preclude the possibility of solutions.  There are 16 such<br \/>\nimages and the fit constraint filter detects and removes them all.\n<\/div>\n<p>Note that running the fit filter twice on the same image set can sometimes<br \/>\nfilter additional images:  on the first run you may remove images that were<br \/>\nrequired for previously tested images to pass the fit check.  If you run the<br \/>\nfit filter twice on the 10&#215;6 pentomino problem while the X piece is<br \/>\nconstrained, the number of filtered images jumps from 227 to 235.  To do a<br \/>\nthorough job you&#8217;d have to filter repeatedly until there was no change in the<br \/>\nimage set.<\/p>\n<p>Although this filter is interesting, its current implementation is too<br \/>\nslow to be of much practical use.  I use DLX itself to identify fit-constraint<br \/>\nviolations and it takes 45 seconds to perform just the first fit filtering<br \/>\noperation for the box-in-a-diamond hexomino puzzle on my 2.5 GHz P4.  I<br \/>\nsuspect I could write something that does the same job much quicker, but I&#8217;m<br \/>\nskeptical I could make it fast enough to be effective.  Still, if your aim is<br \/>\nthe lofty goal of finding all solutions to this puzzle, this filter could<br \/>\nprove worth-while: 45 seconds is nothing for at least the first several piece<br \/>\nplacements of this sizable puzzle.<\/p>\n<p><a name=\"filterperformance\"><\/a><\/p>\n<h4><span class=\"h4\">Image Filter Performance (or lack thereof)<\/span><\/h4>\n<p>Some of the image filters discussed above are only run once before<br \/>\nthe algorithms begin.  I wanted to share some insight as to why such filters<br \/>\nsometimes don&#8217;t give the performance gains you might expect.<\/p>\n<p>As a first example, consider the effects of filtering pentominoes<br \/>\nimages that fall outside the 10&#215;6 puzzle box.  This cuts the total number of<br \/>\nimages that have to be examined by the de Bruijn algorithm at each algorithm<br \/>\nstep by almost a factor 2.  In an extraordinary flash of illogic, you might<br \/>\nconclude that since there are 12 puzzle pieces, the performance advantage to<br \/>\nthe algorithm would be a factor of 2<sup>12<\/sup>&nbsp;=&nbsp;4096.  The problem<br \/>\nwith this logic is that the algorithm immediately skips these images as soon<br \/>\nas they are considered for placement anyway.<\/p>\n<p>For the same reason, filtering images that produce volume constraint<br \/>\nviolations before you begin running the algorithms do not give such<br \/>\nexponential performance gains:  such images typically construct tiny little<br \/>\nconfined spaces that the algorithm would have quickly identified as unfillable<br \/>\nanyway.<\/p>\n<p>But the filter that removes images of a single piece to eliminate<br \/>\nrotational redundancies among discovered solutions seems different:  the<br \/>\nimages removed are not images that will necessarily cause the algorithm to<br \/>\nimmediately backtrack and so you might reasonably expect the filter to not<br \/>\nonly reduce the number of solutions found for the Tetris Cube by a factor of<br \/>\n24 (which it does); but also to improve the overall performance of the<br \/>\nalgorithm by a factor of 24, but it only gave a factor of 21.  (Close!)<\/p>\n<p>Knuth expected that reducing the number of images of 4 pieces each by a<br \/>\nfactor of 2 (to take advantage of a parity constraint on a one-sided hexiamond<br \/>\npuzzle) would lead to a reduction in the work needed to solve the puzzle by a<br \/>\nfactor of 16, but the gains again fell far short of this expectation.<\/p>\n<p>And although I wasn&#8217;t expecting a performance improvement factor of<br \/>\n2<sup>11<\/sup> from the parity filter for the box-in-a-diamond problem, I<br \/>\nthought I&#8217;d get a lot more than a factor of 2.4 (which is all it gave me).<br \/>\nThis result was very surprising to me.<\/p>\n<p>The problem in all of these cases is that you&#8217;re trying to extract<br \/>\nefficiencies from a search tree that is already significantly pruned by the<br \/>\nalgorithm.  Here are some other observations that might be illuminating.<\/p>\n<p>First, consider the case where you a priori force a piece whose images are<br \/>\nto be filtered to be placed first; and then reduce the number of images of<br \/>\nthat piece by a factor of N.  Then the number of ways to place that first<br \/>\npiece is reduced by a factor of N.  Assuming each of those placements<br \/>\noriginally had similar work loads, then the total work would indeed be reduced<br \/>\nby a factor of N.  But what if you always placed this piece last?  Would<br \/>\nperformance still improve by a factor of N?  Of course not!  The vast majority<br \/>\nof search paths terminate in failure before you even get to the last piece.<br \/>\nNow assuming the piece is not being placed first, or last but is instead<br \/>\nplaced uniformly across the search tree, you&#8217;ll find that a sizable percentage<br \/>\nof search paths don&#8217;t even use the filtered piece: they die off before that<br \/>\npiece can be placed.  Filtering the images of that piece won&#8217;t reduce the<br \/>\nweight from these branches of the search tree at all.<\/p>\n<p>Second, the vast majority of the appearances of the piece will be high up<br \/>\nin the branches of the search tree.  At this part of the tree, the branching<br \/>\nfactor is small and obviously drops below 1 at some point.  Because of this,<br \/>\nwhen you prune the tree at one of the appearances of the constraint piece, you<br \/>\ncan&#8217;t assume that the weight of the path left behind is negligible (even<br \/>\nthough that weight is shared by other paths).<\/p>\n<p>These arguments are obviously imprecise and contain (at least) one serious<br \/>\nflaw:  the DLX algorithm (unlike the other two) can reshape the entire search<br \/>\ntree after you constrain the piece to take advantage of its new constrained<br \/>\nnature, but if during execution of the algorithm, the piece is still found<br \/>\nto be less constrained than other elements of the puzzle, then the arguments<br \/>\nabove still apply.  Even if DLX decides to place the newly constrained piece<br \/>\nfirst (and it often does), the average branching factor will still not typically<br \/>\nimprove sufficiently to achieve a factor of N performance improvement.<\/p>\n<p><a name=\"performance\"><\/a><\/p>\n<h2><span class=\"h2\">Performance Comparisons<\/span><\/h2>\n<p>Table 2 shows the performance results for a few different puzzles with many<br \/>\ndifferent combinations of algorithms, backtrack triggers and image filters.<br \/>\nMany of these results have already been discussed in earlier sections but<br \/>\nare provided here in detail.  The run producing the best unique solution<br \/>\nproduction rate is highlighted in yellow for each puzzle.  The table key<br \/>\nexplains everything.<\/p>\n<p>Using the unique solution generation rate as a means of comparing algorithm<br \/>\nquality is flawed as these rates are not completely consistent from<br \/>\nrun-to-run.  The relative performance of the different algorithms can also<br \/>\nchange with the processor design because, for example, one algorithm may make<br \/>\nbetter use of a larger instruction or data cache.  I liked Knuth&#8217;s technique<br \/>\nof simply counting linked list updates to measure performance, but since I&#8217;m<br \/>\ncomparing different algorithms, such an approach seems difficult to apply.<\/p>\n<div style=\"width:900px; background-color:white;\">\n<table align=\"center\" class=\"data\" style=\"width:100%; font-size:70%; background-color:white;\">\n<caption>Table 2.  Test Cases<\/caption>\n<tr>\n<th rowspan=2>Test Case<\/th>\n<th colspan=4>Algorithms<\/th>\n<th colspan=4>Image Filters<\/th>\n<th colspan=2>Backtrack Triggers<\/th>\n<th colspan=3>Monte-Carlo<\/th>\n<th rowspan=2>Attempts<\/th>\n<th rowspan=2>Fits<\/th>\n<th rowspan=2>Unique<\/th>\n<th rowspan=2>Run&nbsp;Time (hh:mm:ss)<\/th>\n<th rowspan=2>Rate<\/th>\n<\/tr>\n<tr>\n<th>DLX<\/th>\n<th>MCH<\/th>\n<th>EMCH<\/th>\n<th>de Bruijn<\/th>\n<th>R<\/th>\n<th>P<\/th>\n<th>V<\/th>\n<th>F<\/th>\n<th>P<\/th>\n<th>V<\/th>\n<th>N<\/th>\n<th>R<\/th>\n<th>S<\/th>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-1<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">3,615,971<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">3,615,971<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:38.761<\/td>\n<td>\n<div style=\"text-align:right;\">60<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-2<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">138,791,760<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9,077,194<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:29.250<\/td>\n<td>\n<div style=\"text-align:right;\">80<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-3<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">191,960,438<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">12,114,615<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:22.485<\/td>\n<td>\n<div style=\"text-align:right;\">104<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-4<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">178,983,597<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">25,848,915<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:06.086<\/td>\n<td>\n<div style=\"text-align:right;\">384<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-5<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">892,247<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">892,247<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:09.449<\/td>\n<td>\n<div style=\"text-align:right;\">246<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-6<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">114,753,421<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">7,646,476<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:24.504<\/td>\n<td>\n<div style=\"text-align:right;\">95<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-7<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">153,036,807<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9,875,973<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:19.992<\/td>\n<td>\n<div style=\"text-align:right;\">117<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-8<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">133,086,329<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">20,073,791<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:04.700<\/td>\n<td>\n<div style=\"text-align:right;\">498<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-9<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">12,411,752<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">924,167<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:02.701<\/td>\n<td>\n<div style=\"text-align:right;\">866<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-10<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">20,374,275<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,425,356<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:02.569<\/td>\n<td>\n<div style=\"text-align:right;\">911<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-11<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">17,703,679<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2,455,947<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:00.579<\/td>\n<td>\n<div style=\"text-align:right;\">4049<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-12<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">17,572,247<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2,454,746<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:00.620<\/td>\n<td>\n<div style=\"text-align:right;\">3781<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tpurple\">P-13<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">15,198,004<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2,091,215<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2339<\/div>\n<\/td>\n<td>00:00:00.510<\/td>\n<td style=\"background-color:yellow;\">\n<div style=\"text-align:right;\">4592<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td colspan=\"19\" style=\"background-color:gray;\"><\/td>\n<\/tr>\n<tr>\n<td class=\"tseagreen\">OP-1<\/td>\n<td class=\"tgreen\">18f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">38,479,316<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">7,060,175<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">46<\/div>\n<\/td>\n<td>00:00:03.611<\/td>\n<td>\n<div style=\"text-align:right;\">12.7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tseagreen\">OP-2<\/td>\n<td class=\"tgreen\">18f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">18<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">1,930,304<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">668,117<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">46<\/div>\n<\/td>\n<td>00:00:00.411<\/td>\n<td style=\"background-color:yellow;\">\n<div style=\"text-align:right;\">112.1<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td colspan=\"19\" style=\"background-color:gray;\"><\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-1<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">1,502,932,134<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,502,932,134<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>07:21:31<\/td>\n<td>\n<div style=\"text-align:right;\">0.37<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-2<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">58,306,235,943<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,604,152,199<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>02:54:07<\/td>\n<td>\n<div style=\"text-align:right;\">0.94<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-3<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">109,746,141,977<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">2,835,090,958<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>02:19:27<\/td>\n<td>\n<div style=\"text-align:right;\">1.18<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-4<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">737,892,116,733<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">38,637,085,619<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>03:29:26<\/td>\n<td>\n<div style=\"text-align:right;\">0.78<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-5<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">68,141,081<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">68,141,081<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:20:37<\/td>\n<td>\n<div style=\"text-align:right;\">7.95<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-6<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">9,727,894,584<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">297,896,605<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:33:17<\/td>\n<td>\n<div style=\"text-align:right;\">4.93<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-7<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">19,436,156,238<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">551,894,232<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:28:45<\/td>\n<td>\n<div style=\"text-align:right;\">5.70<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-8<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">12<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">140,658,669,459<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">7,992,209,655<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:43:08<\/td>\n<td>\n<div style=\"text-align:right;\">3.80<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-9<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">2,153,543,323<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">72,670,225<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:07:20<\/td>\n<td>\n<div style=\"text-align:right;\">22.35<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-10<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">4,196,219,275<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">129,746,342<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:06:02<\/td>\n<td>\n<div style=\"text-align:right;\">27.16<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-11<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">32,810,876,767<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,898,921,763<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:09:48<\/td>\n<td>\n<div style=\"text-align:right;\">16.74<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-12<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tgreen\">6<\/td>\n<td class=\"tgreen\">4<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">10,380,361,756<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">453,289,747<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:04:04<\/td>\n<td>\n<div style=\"text-align:right;\">40.25<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tgray\">TC-13<\/td>\n<td class=\"tgreen\">12f<\/td>\n<td class=\"tgreen\">11<\/td>\n<td class=\"tgreen\">6<\/td>\n<td class=\"tgreen\">4<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>\n<div style=\"text-align:right;\">9,421,945,256<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">439,737,621<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9839<\/div>\n<\/td>\n<td>00:03:57<\/td>\n<td style=\"background-color:yellow;\">\n<div style=\"text-align:right;\">41.53<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td colspan=\"19\" style=\"background-color:gray;\"><\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-1<\/td>\n<td class=\"tgreen\">35x&nbsp;0f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,131,766,165<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,131,766,165<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>05:28:15<\/td>\n<td>\n<div style=\"text-align:right;\">0.885<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-2<\/td>\n<td class=\"tgreen\">35x&nbsp;2f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,131,686,519<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,131,686,519<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>05:29:15<\/td>\n<td>\n<div style=\"text-align:right;\">0.883<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-3<\/td>\n<td class=\"tgreen\">35x&nbsp;4f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,097,629,194<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,097,629,194<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>05:28:58<\/td>\n<td>\n<div style=\"text-align:right;\">0.883<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-4<\/td>\n<td class=\"tgreen\">35x&nbsp;6f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">849,818,771<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">849,818,771<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>04:48:02<\/td>\n<td>\n<div style=\"text-align:right;\">1.009<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-5<\/td>\n<td class=\"tgreen\">35x&nbsp;8f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">507,044,709<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">507,044,709<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>03:14:58<\/td>\n<td>\n<div style=\"text-align:right;\">1.490<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-6<\/td>\n<td class=\"tgreen\">35x&nbsp;10f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">326,708,081<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">326,708,081<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>02:07:31<\/td>\n<td>\n<div style=\"text-align:right;\">2.279<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-7<\/td>\n<td class=\"tgreen\">35x&nbsp;12f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">272,000,566<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">272,000,566<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>01:44:36<\/td>\n<td>\n<div style=\"text-align:right;\">2.778<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-8<\/td>\n<td class=\"tgreen\">35x&nbsp;14f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">241,487,173<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">241,487,173<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">17,435<\/div>\n<\/td>\n<td>01:34:34<\/td>\n<td>\n<div style=\"text-align:right;\">3.073<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-9<\/td>\n<td class=\"tgreen\">35x&nbsp;16f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">420,363,728<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">420,363,728<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">30,945<\/div>\n<\/td>\n<td>02:15:46<\/td>\n<td>\n<div style=\"text-align:right;\">3.799<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-10<\/td>\n<td class=\"tgreen\">35x&nbsp;18f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">880,638,007<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">880,638,007<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">60,415<\/div>\n<\/td>\n<td>04:04:34<\/td>\n<td>\n<div style=\"text-align:right;\">4.117<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-11<\/td>\n<td class=\"tgreen\">35x&nbsp;20f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,363,568,660<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,363,568,660<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">106,960<\/div>\n<\/td>\n<td>05:53:36<\/td>\n<td style=\"background-color:yellow;\">\n<div style=\"text-align:right;\">5.041<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-12<\/td>\n<td class=\"tgreen\">35x&nbsp;22f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,508,462,348<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,508,462,348<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">112,975<\/div>\n<\/td>\n<td>06:18:54<\/td>\n<td>\n<div style=\"text-align:right;\">4.970<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-13<\/td>\n<td class=\"tgreen\">35x&nbsp;24f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,728,349,705<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,728,349,705<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">119,370<\/div>\n<\/td>\n<td>07:10:09<\/td>\n<td>\n<div style=\"text-align:right;\">4.625<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-14<\/td>\n<td class=\"tgreen\">35x&nbsp;26f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,718,965,943<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,718,965,943<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">119,862<\/div>\n<\/td>\n<td>07:09:28<\/td>\n<td>\n<div style=\"text-align:right;\">4.652<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-15<\/td>\n<td class=\"tgreen\">35x&nbsp;28f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,858,118,645<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,858,118,645<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">133,872<\/div>\n<\/td>\n<td>07:44:54<\/td>\n<td>\n<div style=\"text-align:right;\">4.799<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-16<\/td>\n<td class=\"tgreen\">35x&nbsp;30f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,700,793,486<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,700,793,486<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">108,882<\/div>\n<\/td>\n<td>07:07:56<\/td>\n<td>\n<div style=\"text-align:right;\">4.241<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-17<\/td>\n<td class=\"tgreen\">35x&nbsp;32f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,735,853,837<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,735,853,837<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">115,466<\/div>\n<\/td>\n<td>07:19:01<\/td>\n<td>\n<div style=\"text-align:right;\">4.384<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"torange\">HP-18<\/td>\n<td class=\"tgreen\">35x&nbsp;34f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,912,535,104<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,912,535,104<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">140,085<\/div>\n<\/td>\n<td>07:53:32<\/td>\n<td>\n<div style=\"text-align:right;\">4.930<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td colspan=\"19\" style=\"background-color:gray;\"><\/td>\n<\/tr>\n<tr>\n<td class=\"tbrown\">HBD-1<\/td>\n<td class=\"tgreen\">35f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">22<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">0<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9,381,994,687<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">9,381,994,687<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">16,735<\/div>\n<\/td>\n<td>49:54:40<\/td>\n<td>\n<div style=\"text-align:right;\">0.093<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tbrown\">HBD-2<\/td>\n<td class=\"tgreen\">35a@160&nbsp;15f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">22<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">0<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">978,785,202<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">978,785,202<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">3731<\/div>\n<\/td>\n<td>05:28:58<\/td>\n<td>\n<div style=\"text-align:right;\">0.189<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tbrown\">HBD-3<\/td>\n<td class=\"tgreen\">35a@160&nbsp;15f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">ON<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">22<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">0<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">968,436,589<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">968,436,589<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5761<\/div>\n<\/td>\n<td>05:08:05<\/td>\n<td>\n<div style=\"text-align:right;\">0.312<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tbrown\">HBD-4<\/td>\n<td class=\"tgreen\">35a@160&nbsp;15f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">35<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">22<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">0<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,156,373,212<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,156,373,212<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">8738<\/div>\n<\/td>\n<td>05:27:04<\/td>\n<td>\n<div style=\"text-align:right;\">0.445<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td class=\"tbrown\">HBD-5<\/td>\n<td class=\"tgreen\">35a@160&nbsp;15f<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">0<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tgreen\">35<\/td>\n<td class=\"tgreen\">35<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td class=\"tred\">OFF<\/td>\n<td>\n<div style=\"text-align:right;\">10,000<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">22<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">0<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">1,629,292,460<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">629,292,460<\/div>\n<\/td>\n<td>\n<div style=\"text-align:right;\">5652<\/div>\n<\/td>\n<td>02:44:54<\/td>\n<td style=\"background-color:yellow;\">\n<div style=\"text-align:right;\">1.582<\/div>\n<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<div style=\"display:block; margin:20px auto 20px auto; float:none; clear:both; max-width: 80%;\">\n<table align=\"center\" class=\"data2\">\n<tr>\n<th colspan=\"4\"><span style=\"font-size:150%;\">KEY<\/span><\/th>\n<\/tr>\n<tr>\n<th rowspan=\"5\">Test Case<\/th>\n<th class=\"tpurple\">P<\/th>\n<td width=\"30%\">Pentomino 10&#215;6<\/td>\n<td rowspan=\"5\">\n                                                                                                                      Test Cases P, OP, and TC were run on a 2.5 GHz P4<br \/>\n                                                                                                                      running Unbuntu Linux.  Test Cases HP and HBD were<br \/>\n                                                                                                                      run on a  2.4 GHz Core 2 Quad CPU Q6600 running<br \/>\n                                                                                                                      Windows XP (using only one of the four processors).\n                                                                                                                   <\/td>\n<\/tr>\n<tr>\n<th class=\"tseagreen\">OP<\/th>\n<td>One-Sided Pentomino 30&#215;3<\/td>\n<\/tr>\n<tr>\n<th class=\"tgray\">TC<\/th>\n<td>Tetris Cube<\/td>\n<\/tr>\n<tr>\n<th class=\"torange\">HP<\/th>\n<td>Hexomino 15&#215;14 Parallelogram<\/td>\n<\/tr>\n<tr>\n<th class=\"tbrown\">HBD<\/th>\n<td>Hexomino Box-in-a-Diamond<\/td>\n<\/tr>\n<tr>\n<th>Algorithms<\/th>\n<td colspan=\"3\">\n                                                    The number in each algorithm column is the number of remaining<br \/>\n                                                    pieces when the algorithm is activated.  For the case of DLX<br \/>\n                                                    multiple activation numbers can be given, each with a different<br \/>\n                                                    ordering heuristic.  An entry 12f means the min-fit ordering<br \/>\n                                                    heuristic is activated when 12 pieces remain.  Other heuristics<br \/>\n                                                    used are the x heuristic which picks the hole with minimum x<br \/>\n                                                    coordinate value; and the a@160 heuristic which picks the hole<br \/>\n                                                    that forms the minimum angle from the center of the puzzle with an<br \/>\n                                                    initial angle of 160 degrees.\n                                                <\/td>\n<\/tr>\n<tr>\n<th rowspan=\"4\">Image Filters<\/th>\n<th>R<\/th>\n<td>Rotational Redundancy Filter<\/td>\n<td rowspan=\"4\">\n                                                                        A number in a column gives the minimum number<br \/>\n                                                                        of remaining pieces for the image filter to be applied.<\/td>\n<\/tr>\n<tr>\n<th>P<\/th>\n<td>Parity Constraint Filter<\/td>\n<\/tr>\n<tr>\n<th>V<\/th>\n<td>Volume Constraint Filter<\/td>\n<\/tr>\n<tr>\n<th>F<\/th>\n<td>Fit Constraint Filter<\/td>\n<\/tr>\n<tr>\n<th rowspan=\"2\">Backtrack Triggers<\/th>\n<th>P<\/th>\n<td>Parity Constraint Backtrack Trigger<\/td>\n<td rowspan=\"2\">\n                                                                        A number in a column gives the minimum number of<br \/>\n                                                                        remaining pieces for the backtrack trigger to be applied.<\/td>\n<\/tr>\n<tr>\n<th>V<\/th>\n<td>Volume Constraint Backtrack Trigger<\/td>\n<\/tr>\n<tr>\n<th rowspan=\"3\">Monte-Carlo<\/th>\n<th>N<\/th>\n<td>Number of trials.<\/td>\n<\/tr>\n<tr>\n<th>R<\/th>\n<td>If after removing a piece from the puzzle there are<br \/>\n                                                                exactly R pieces left to place, the Monte-Carlo trial is ended.<\/td>\n<\/tr>\n<tr>\n<th>S<\/th>\n<td>Seed value to the Mersene Twister random number generator.<\/td>\n<\/tr>\n<tr>\n<th>Attempts<\/th>\n<td colspan=\"3\">The number of times pieces were attempted to be placed.<\/td>\n<\/tr>\n<tr>\n<th>Fits<\/th>\n<td colspan=\"3\">The number of times pieces were successfully placed.<\/td>\n<\/tr>\n<tr>\n<th>Unique<\/th>\n<td colspan=\"3\">The number of unique solutions found.<\/td>\n<\/tr>\n<tr>\n<th>Run Time<\/th>\n<td colspan=\"3\">The total run time for the test.<\/td>\n<\/tr>\n<tr>\n<th>Rate<\/th>\n<td colspan=\"3\">The number of unique solutions found per second  (Unique \/ Run Time).<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p><a name=\"performanceP\"><\/a><\/p>\n<h3><span class=\"h3 tpurple\">Test Case P:  Pentominoes in a 10&#215;6 Box<\/span><\/h3>\n<p>The first set of test cases (P) examines the 10&#215;6 pentomino puzzle shown<br \/>\nin <a href=\"#figure3\">Figure&nbsp;3<\/a>.  Runs 1 through 4 show the<br \/>\nperformance of the four basic algorithms.<\/p>\n<p>Comparing these first four runs with runs 5 through 8 shows the significant<br \/>\nperformance advantage of the rotational redundancy filter.  This filter<br \/>\nconsistently offers significant performance gains when looking for all<br \/>\nsolutions to a symmetric puzzle.  Also note that DLX performs relatively<br \/>\nbetter with this filter enabled as it&#8217;s the only algorithm capable of<br \/>\niterating over the possible placements of the piece constrained by the filter.<\/p>\n<p>Runs 9 through 11 use DLX only for the first piece placement (to take full<br \/>\nadvantage of the rotational redundancy filter) but then switch to the other<br \/>\nlighter-weight algorithms to place the last 11 pieces.  Comparing run 8 with<br \/>\nrun 11 shows this combined algorithmic approach to be about eight times faster<br \/>\nthan any single algorithm.<\/p>\n<p>Run 12 shows that although the parity filter does offer a very moderate<br \/>\nreduction in attempts and fits, the net effect is a reduction in the production<br \/>\nrate of unique solutions.<\/p>\n<p>Run 13 uses a one-shot volume filter to expunge many useless images from<br \/>\nthe image set and results in about a 13% increase in performance.<\/p>\n<p><a name=\"performanceOP\"><\/a><\/p>\n<h3><span class=\"h3 tseagreen\">Test Case OP:  One-sided Pentominoes in a 30&#215;3 Box<\/span><\/h3>\n<p>The second set of test cases (OP) examines the problem of placing the<br \/>\none-sided pentominoes in a 30&#215;3 box as shown in <a\nhref=\"#figure14\">Figure&nbsp;14<\/a>.  The volume filter is shown to be<br \/>\nparticularly useful for this puzzle delivering a factor-of-nine performance<br \/>\nimprovement.<\/p>\n<p><a name=\"performanceTC\"><\/a><\/p>\n<h3><span class=\"h3 tgray\">Test Case TC:  Tetris Cube<\/span><\/h3>\n<p>The third set of test cases (TC) examines the Tetris Cube as shown in<br \/>\n<a href=\"#figure1\">Figure&nbsp;1<\/a>.  The first four runs show the<br \/>\nperformance of MCH and EMCH to be superior to DLX and de Bruijn for this small<br \/>\n3-D puzzle.<\/p>\n<p>Runs 5 through 8 again show the huge performance benefits of the rotational<br \/>\nredundancy filter; and again DLX performs relatively better than the other<br \/>\nalgorithms with the rotational redundancy filter active, even outperforming<br \/>\nde Bruijn for this 3D puzzle.<\/p>\n<p>In runs 9 through 11 I start to combine the algorithms only using<br \/>\nDLX to place the first piece (to get it to iterate over the possible<br \/>\nplacements of the piece constrained by the rotational redundancy filter)<br \/>\nbut then switching to just one of the simpler algorithms.  As can be seen from<br \/>\nthe table, the benefits of this combined approach are quite significant.<\/p>\n<p>In run 12 all four algorithms are combined to solve the puzzle.  If you<br \/>\nnumber pieces as you place them in the box counting down from 12 (so the last<br \/>\npiece placed is numbered 1); then DLX was used to place piece 12; MCH to place<br \/>\npieces 11 through 7; EMCH to place pieces 6 and 5; and de Bruijn was used to<br \/>\nplace pieces 4 through 1.  As the number of remaining pieces gets smaller, it<br \/>\npays to use simpler algorithms.  Compare the performance of run 12 with the<br \/>\nperformance of runs 5 through 8 (where just one algorithm was used) and you<br \/>\nsee that the combined algorithmic approach is more than 5 times faster than<br \/>\nthe fastest of those single algorithm runs.<\/p>\n<p>Run 13 shows that the parity backtrack trigger offers a small benefit<br \/>\n(about 3%) for this puzzle.  It is interesting that run 13 is well over 100<br \/>\ntimes faster than the straight DLX approach used in run 1.<\/p>\n<p><a name=\"performanceHP\"><\/a><\/p>\n<h3><span class=\"h3 torange\">Test Case HP:  Hexominoes in a 15&#215;14 Parallelogram<\/span><\/h3>\n<p>The fourth set of test cases (HP) examines the problem of placing<br \/>\nthe 35 hexominoes in the 15&#215;14 parallelogram shown in <a href=\"#figure6\">Figure&nbsp;6<\/a>.<br \/>\nHere I did not try to find the overall best solver configuration, but<br \/>\ninstead only studied the effects of packing pieces simply from left to right<br \/>\n(using the x ordering heuristic) for initial piece placements and then<br \/>\nswitching to the DLX min-fit heuristic for latter piece placements.  I should<br \/>\nnot have had the rotational redundancy filter active for these tests &mdash;<br \/>\nthis only slows solution production rates when examining such a small portion<br \/>\nof the search tree &mdash; but I didn&#8217;t want to tie up my computer for another<br \/>\nweek to rerun the tests.  The best performance was had when using the min-fit<br \/>\nheuristic only for the last twenty piece placements.  Using the min-fit<br \/>\nheuristic for more than twenty pieces resulted in little performance change<br \/>\nbut seems to exhibit some small degradation.<\/p>\n<p>It is likely that application of the volume constraint filter, the parity constraint backtrack<br \/>\ntrigger, and the de Bruijn algorithm (for latter piece placements) would offer additional<br \/>\nperformance gains for this puzzle.<\/p>\n<p><a name=\"performanceHBD\"><\/a><\/p>\n<h3><span class=\"h3 tbrown\">Test Case HBD:  Hexominoes Box-in-a-Diamond<\/span><\/h3>\n<p>The last set of test cases (HBD) examines the hexomino box-in-a-diamond<br \/>\npuzzle shown in <a href=\"#figure12\">Figure&nbsp;12<\/a>.  The first run is a<br \/>\nstraight no-frills DLX run using the min-fit heuristic.  For the second run I<br \/>\ninstead used my angular ordering heuristic which packs pieces into the puzzle<br \/>\nin a counter clock-wise direction.  I started placing pieces at 160 degrees<br \/>\n(about ten o-clock) so that the less confined region at the top of the puzzle<br \/>\nwould be left for last.  Once there were only 15 pieces left I switched to the<br \/>\nmin-fit heuristic.  The number 15 was just a guess and probably too low for<br \/>\nbest performance; but this approach was still twice as fast as using a pure<br \/>\nmin-fit heuristic.<\/p>\n<p>Run 3 shows that enabling the parity constraint backtrack trigger improved<br \/>\nperformance by about 65% in this very high-parity puzzle.  Run 4 switches to<br \/>\nthe parity constraint filter which improves performance by another 42%.<\/p>\n<p>Most interestingly, Run 5 shows a one-shot application of the volume<br \/>\nconstraint filter increased performance by a factor of 3.5.<\/p>\n<p><a name=\"software\"><\/a><\/p>\n<h2><span class=\"h2\">Software<\/span><\/h2>\n<p>This software is protected by the GNU General Public License (GPL)<br \/>\nVersion 3.  See the <a href=\"\/projects\/polycube\/downloads\/1.2.1\/README.txt\">README.txt<\/a> file included in the<br \/>\nzip file download for more information.<\/p>\n<p><i>EDIT (February 11, 2019): the software described and linked below is several years old, but is retained here as it is consistent with this document.  I encourage you, however, to instead download and use my improved version of polycube linked from my more recent <a href=\"\/blog\/article\/fila\">article on FILA<\/a>.<\/i><\/p>\n<p><a name=\"softwareDownload\"><\/a><\/p>\n<h3><span class=\"h3\">Download<\/span><\/h3>\n<div class=\"emphasize\">WINDOWS:  <a href=\"\/projects\/polycube\/downloads\/polycube_1.2.1.zip\">polycube_1.2.1.zip<\/a><\/div>\n<div style=\"margin: 10px 0px 0px 80px\">\nContents:<\/p>\n<ul style=\"margin-top: 0px\">\n<li><b><a href=\"\/projects\/polycube\/downloads\/1.2.1\/README.txt\">README.txt<\/a><\/b> (copyright, build and run instructions)<\/li>\n<li><b><a href=\"\/projects\/polycube\/downloads\/1.2.1\/RELEASE_NOTES.txt\">RELEASE_NOTES.txt<\/a><\/b> (summary of changes for each release)<\/li>\n<li><b>polycube.exe<\/b> (polycube solver executable for Windows)<\/li>\n<li><b>tetriscube_def.txt<\/b> (definition file for the Tetris Cube puzzle)<\/li>\n<li><b>bedlamcube_def.txt<\/b> (definition file for the Bedlam Cube puzzle)<\/li>\n<li><b>somacube_def.txt<\/b> (definition file for the Soma Cube puzzle)<\/li>\n<li>Several definitions for the Pentominoes puzzle for solutions of different shapes.<\/li>\n<li>Puzzle solver C++ source<\/li>\n<\/ul>\n<\/div>\n<div class=\"emphasize\">LINUX \/ UNIX:  <a href=\"\/projects\/polycube\/downloads\/polycube_1.2.1.tgz\">polycube_1.2.1.tgz<\/a><\/div>\n<div style=\"margin: 10px 0px 24px 80px\">\nContents:  same as for Windows, but no executable and all text files are carriage return stripped.\n<\/div>\n<p>The source is about 10,000 lines of C++ code, with dependencies on two<br \/>\nother libraries (boost and the Mersene Twister random number generator) which<br \/>\nare also included in the download.  The executable file polycube.exe is a<br \/>\nWindows console application (sorry, no GUIs folks).  For non-Windows platforms<br \/>\nyou&#8217;ll need to compile the source.<\/p>\n<p><a name=\"softwareRun\"><\/a><\/p>\n<h3><span class=\"h3\">Running the Software<\/span><\/h3>\n<p>The <a href=\"\/projects\/polycube\/downloads\/README.txt\">README.txt<\/a> file gives the full details about<br \/>\nhow to run the software (algorithm control, solution output control, trace<br \/>\noutput control, puzzle definition file formats, etc); but here is a brief<br \/>\nintroduction.  Simply pass <span class=\"code\">polycube<\/span> one (or more)<br \/>\npuzzle definition files on the command like this:<\/p>\n<pre>\r\n    polycube def\/pentominoes_10x6_def.txt\r\n<\/pre>\n<p>This will immediately start spitting out solutions to the 10&#215;6 pentominoes<br \/>\npuzzle.  Once you see that it&#8217;s working you&#8217;ll probably want to explore<br \/>\navailable command line options.  To see them run:<\/p>\n<pre>\r\n    polycube --help\r\n<\/pre>\n<p>There are several puzzle definition files provided.  These are simple text<br \/>\nfiles that look like this:<\/p>\n<pre>\r\n# Tetris Cube Puzzle Definition\r\nD:xDim=4:yDim=4:zDim=4\r\nC:name=A:type=M:layout=0 0 2,  1 0 2,  2 0 2,  2 0 1,  2 0 0,  2 1 0  # Blue angle with end-notch\r\nC:name=B:type=M:layout=0 0 0,  1 0 0,  2 0 0,  2 1 0,  2 2 0,  2 1 1  # Blue angle with mid-notch\r\nC:name=C:type=M:layout=0 0 0,  1 0 0,  1 0 1,  2 0 1,  2 1 1          # Blue angled staircase\r\nC:name=D:type=M:layout=0 0 0,  1 0 0,  2 0 0,  2 1 0,  3 1 0          # Blue 2-D serpent\r\nC:name=E:type=M:layout=0 0 1,  0 0 0,  1 0 0,  1 1 0,  1 2 0,  2 1 0  # Red dog with tail\r\nC:name=F:type=M:layout=0 0 0,  1 0 0,  0 0 1,  1 0 1,  0 1 0          # Red ziggurat\r\nC:name=G:type=M:layout=0 2 0,  0 1 0,  0 0 0,  1 0 0,  2 0 0          # Red angle\r\nC:name=H:type=M:layout=0 0 0,  1 0 0,  2 0 0,  3 0 0,  2 1 0          # Red line with mid-notch\r\nC:name=I:type=M:layout=0 0 1,  1 0 1,  2 0 1,  0 1 1,  0 1 0          # Yellow pole with twisty top\r\nC:name=J:type=M:layout=0 0 0,  1 0 0,  1 0 1,  1 1 1,  2 1 1          # Yellow cork-screw\r\nC:name=K:type=M:layout=0 0 0,  1 0 0,  2 0 0,  1 1 0,  1 1 1          # Yellow radar dish\r\nC:name=L:type=M:layout=0 1 0,  1 1 0,  1 1 1,  2 1 1,  1 0 1,  1 2 1  # Yellow sphinx\r\n~D\r\n<\/pre>\n<p>The type=M means the piece is mobile and free to move about (the typical<br \/>\ncase), but you can also declare a piece to be type S (stationary) to forcibly<br \/>\nload the piece at the given coordinates.  It&#8217;s often easier to define the<br \/>\npuzzle pieces graphically.  Here&#8217;s a definition file for the box-in-a-diamond<br \/>\nhexomino puzzle that uses graphical layouts for piece definitions.<\/p>\n<pre>\r\n# Box-in-a-Diamond Hexomino Puzzle Definition\r\nD:xDim=23:yDim=23:zDim=1\r\nL\r\n. . . . . . . . . . . A . . . . . . . . . . . . . . . . . . . . . . . . . . .\r\n. . . . . . . . . . . A . B B . C . . D . . . E . . F . . . . . . . . . . . .\r\n. . . . . . . . . . . A . B . . C C . D . . E E . . F . . . . . . . . . . . .\r\n. . . . . . . . . . . A . B . . C . . D D . E . . F F . . . . . . . . . . . .\r\n. . . . . . . . . . . A . B . . C . . D . . E . . F . . . . . . . . . . . . .\r\n. . . . . . . . . . . A . B . . C . . D . . E . . F . . . . . . . . . . . . .\r\n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\r\n. G G . H H . I I . J . . K . . . L . M M M . N . . . O . . . P . . . Q . . .\r\n. G G . H . . I . . J J . K K . L L . M . . . N N N . O . . . P . . . Q . . .\r\n. G . . H H . I . . J J . K K . L . . M . . . N . . . O O O . P P . . Q Q Q .\r\n. G . . H . . I I . J . . . K . L L . M . . . N . . . . O . . . P P . . . Q .\r\n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\r\nR . . . S . . . T . . . U U U . V V . . W W . . X X . . . Y . . . Z . . 1 . .\r\nR R R . S S . . T T . . . U . . . V V . . W . . . X . . Y Y Y . Z Z . . 1 1 .\r\n. R . . . S S . . T . . . U . . . V . . . W W . . X . . . Y . . . Z Z . . 1 1\r\n. R . . . S . . . T T . . U . . . V . . . W . . . X X . . Y . . . Z . . . . 1\r\n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\r\n. . . . . 2 2 . 3 . . . 4 . . . 5 . . . 6 . . . 7 7 . . 8 8 . . 9 9 . . . . .\r\n. . . . . 2 2 . 3 3 3 . 4 4 . . 5 5 5 . 6 . 6 . 7 7 7 . 8 8 . . . 9 9 . . . .\r\n. . . . . 2 2 . 3 3 . . 4 4 4 . 5 . 5 . 6 6 6 . . 7 . . . 8 8 . 9 9 . . . . .\r\n~L\r\nL:stationary=*\r\n* * * * * * * * * * * . * * * * * * * * * * *\r\n* * * * * * * * * * . . . * * * * * * * * * *\r\n* * * * * * * * * . . . . . * * * * * * * * *\r\n* * * * * * * * . . . . . . . * * * * * * * *\r\n* * * * * * * . . . . . . . . . * * * * * * *\r\n* * * * * * . . . . . . . . . . . * * * * * *\r\n* * * * * . . . . . . . . . . . . . * * * * *\r\n* * * * . . . . . . . . . . . . . . . * * * *\r\n* * * . . . . . . . . . . . . . . . . . * * *\r\n* * . . . . * * * * * * * * * * * . . . . * *\r\n* . . . . . * * * * * * * * * * * . . . . . *\r\n. . . . . . * * * * * * * * * * * . . . . . .\r\n* . . . . . * * * * * * * * * * * . . . . . *\r\n* * . . . . * * * * * * * * * * * . . . . * *\r\n* * * . . . . . . . . . . . . . . . . . * * *\r\n* * * * . . . . . . . . . . . . . . . * * * *\r\n* * * * * . . . . . . . . . . . . . * * * * *\r\n* * * * * * . . . . . . . . . . . * * * * * *\r\n* * * * * * * . . . . . . . . . * * * * * * *\r\n* * * * * * * * . . . . . . . * * * * * * * *\r\n* * * * * * * * * . . . . . * * * * * * * * *\r\n* * * * * * * * * * . . . * * * * * * * * * *\r\n* * * * * * * * * * * . * * * * * * * * * * *\r\n~L\r\n~D\r\n<\/pre>\n<p>Note that a single stationary piece named * is used to shape the puzzle.<\/p>\n<p><a name=\"softwareFeature\"><\/a><\/p>\n<h3><span class=\"h3\">Planned Features<\/span><\/h3>\n<p>When I get time to work on this again, these are the features<br \/>\nI&#8217;ll be adding:<\/p>\n<ul>\n<li>Improve the implementation of the volume constraint filter.  This filter<br \/>\noften offers remarkable performance enhancements, but I think I can make it<br \/>\nfaster and increase the range of problems where it is effective.<\/li>\n<li>Extend the rotational symmetry filter to also detect and filter 3-D<br \/>\nreflective symmetries.  This is exactly like one-sided polyomino<br \/>\nconstraints:  one-sided polyomino pieces are free to rotate in 2 dimensions but<br \/>\nnot in 3; but because every polyomino piece has a mirror that&#8217;s also<br \/>\nin the piece set, constructions that have mirror symmetries can be flipped<br \/>\nup-side-down (a 180 degree rotation through the third dimension) to produce a<br \/>\nnew valid solution.  Similarly, all 3-D puzzles are effectively one-sided<br \/>\nrelative to the 4th dimension:  we puny humans cannot take a puzzle piece and<br \/>\nrotate it 180 degrees through the 4th dimension.  If we could, we could<br \/>\ntransform any piece into its mirror image.  But, if the piece set as a whole<br \/>\nis <i>complete<\/i> (again, in the sense that the mirror of every piece is also<br \/>\nin the available piece set); then it is possible to rotate any solution to<br \/>\nany puzzle having mirror symmetries 180 degrees through the 4th dimension to<br \/>\nproduce a new valid solution.  I think it should be straight-forward to<br \/>\nfurther constrain the allowed rotations and\/or translations of a piece to<br \/>\neliminate such trivial solutions from the search and achieve additional<br \/>\nperformance gains for those puzzles that have this property.  (E.g., any soma<br \/>\ncube or pentacube construction with mirror symmetries should be able to take<br \/>\nadvantage this technique.)<\/li>\n<li>Add support for multi-threading and\/or distributed processing.<\/li>\n<li>Add support for graphical rendering of puzzle trace and solution output.<\/li>\n<li>Additional constraint-based image filters and\/or backtrack triggers.<\/li>\n<li>Possibly add other algorithms.<\/li>\n<\/ul>\n<p><a name=\"solutions\"><\/a><\/p>\n<h2><span class=\"h2\">Solutions<\/span><\/h2>\n<p>Here are all the solutions to the Tetris Cube and a few other popular<br \/>\npuzzles:<\/p>\n<div class=\"emphasize\">WINDOWS:  <a href=\"\/projects\/polycube\/downloads\/solutions.zip\">solutions.zip<\/a><\/div>\n<div style=\"margin: 10px 0px 0px 80px\">\nContents:<\/p>\n<ul style=\"margin-top: 0px\">\n<li><b>bedlamcube_out.txt<\/b> (all 19186 solutions to the Bedlam Cube puzzle)<\/li>\n<li><b>pentominoes_10x6_out.txt<\/b> (all 2339 solutions to the 10&#215;6 pentomino puzzle)<\/li>\n<li><b>pentominoes_onesided_30x3_out.txt<\/b> (all 46 solutions to the 30&#215;3 one-sided pentomino puzzle)<\/li>\n<li><b>somacube_out.txt<\/b> (all 480 solutions to the Soma Cube puzzle)<\/li>\n<li><b>tetriscube_out.txt<\/b> (all 9839 solutions to the Tetris Cube puzzle)<\/li>\n<\/ul>\n<\/div>\n<div class=\"emphasize\">LINUX \/ UNIX:  <a href=\"\/projects\/polycube\/downloads\/solutions.tgz\">solutions.tgz<\/a><\/div>\n<div style=\"margin: 10px 0px 24px 80px;\">\nContents:  same as for Windows, but all text files are carriage return stripped.\n<\/div>\n<p>The solutions for 3-D puzzles need explanation.  The first three solutions<br \/>\nto the Tetris Cube are shown below.  Each solution is displayed as four<br \/>\nhorizontal slices of the puzzle box like the layers of a four-layer cake.  The<br \/>\nfirst slice (on the left) shows the bottom layer of the box; the next slice is<br \/>\nthe second layer of the box; etc.  The letters match the labels of the pieces<br \/>\nshown in the <a href=\"#figure1\">photo<\/a> above, identifying which piece<br \/>\noccupies each cell in each layer of the puzzle box.  The background color is<br \/>\nalso set to match the color of the pieces.  Because the pieces are three<br \/>\ndimensional, they can span multiple layers of this output.<\/p>\n<p><script type=\"text\/javascript\">\n\/* <![CDATA[ *\/\n\nvar tetrisColor = {\n    A:'#8080FF',\n    B:'#8080FF',\n    C:'#8080FF',\n    D:'#8080FF',\n    E:'red',\n    F:'red',\n    G:'red',\n    H:'red',\n    I:'yellow',\n    J:'yellow',\n    K:'yellow',\n    L:'yellow' };\n\nvar tetrisLabel = {\n    A:'A',\n    B:'B',\n    C:'C',\n    D:'D',\n    E:'E',\n    F:'F',\n    G:'G',\n    H:'H',\n    I:'I',\n    J:'J',\n    K:'K',\n    L:'L' };\n\nvar tetrisSolution = new Array();\n\ntetrisSolution[1] = 'K B E E,K C J J,K C C J,A L C D\\n' +\n                    'G B J E,K K J E,L L L E,A L C D\\n' +\n                    'G B B B,A A B E,A L F H,A I D D\\n' +\n                    'G G G H,I F F H,I F F H,I I D H';\n\ntetrisSolution[2] = 'K I F F,K I J F,K I A E,A A A E\\n' +\n                    'G J J F,K K J F,C I I L,A E E E\\n' +\n                    'G J D D,D D D L,C C L L,A B E L\\n' +\n                    'G G G H,B C H H,B C L H,B B B H';\n\ntetrisSolution[3] = 'K I F F,K I I I,K J A E,A A A E\\n' +\n                    'G I F F,K K J F,C J J L,A E E E\\n' +\n                    'G D D D,D D J L,C C L L,A B E L\\n' +\n                    'G G G H,B C H H,B C L H,B B B H';\n\ndocument.write('\n\n<div class=\"solution\">--- SOLUTION 1 ---<\/div>\n\n');\ndocument.write(puzzleToHtmlTable(tetrisSolution[1], tetrisColor, true, tetrisLabel, 'big'));\ndocument.write('\n\n<div class=\"solution\">--- SOLUTION 2 ---<\/div>\n\n');\ndocument.write(puzzleToHtmlTable(tetrisSolution[2], tetrisColor, true, tetrisLabel, 'big'));\ndocument.write('\n\n<div class=\"solution\">--- SOLUTION 3 ---<\/div>\n\n');\ndocument.write(puzzleToHtmlTable(tetrisSolution[3], tetrisColor, true, tetrisLabel, 'big'));\n\n\/* ]]> *\/\n<\/script><\/p>\n<p>One thing I find fun to do is to use the solutions to place just the first 6<br \/>\nor 7 pieces in the box, and then see if I can solve it from there.  It&#8217;s still<br \/>\nchallenging, but won&#8217;t cost you a week of vacation to find a solution.<\/p>\n<p><a name=\"conclusions\"><\/a><\/p>\n<h2><span class=\"h2\">Conclusions<\/span><\/h2>\n<p>Applying a host of different algorithms and constraints-based optimizations<br \/>\nto a single polyomino or polycube problem can deliver great performance<br \/>\nbenefits.  For large problems it appears that initially simply packing<br \/>\nconfined regions of the puzzle works well.  When the number of remaining<br \/>\npieces reaches some critical threshold (that depends on the complexity of<br \/>\nthe piece and the topology of the remaining puzzle), switching to an<br \/>\nalgorithm that seeks out constrained holes or pieces does better.<br \/>\nExamples of such algorithms include DLX using a min-fit ordering heuristic,<br \/>\nand the MCH algorithm.  For the final piece placements, the deBruijn algorithm<br \/>\nappears most efficient.  Parity-based constraints can offer performance<br \/>\nbenefits especially for high-parity puzzles.  Investing the time to purge the<br \/>\nimages of pieces that partition a puzzle into two regions that are clearly<br \/>\nunfillable based on volume considerations consistently offered<br \/>\nconsiderable performance benefits for all polyomino puzzles examined.<br \/>\nConstraining the allowed images of a piece to eliminate rotationally redundant<br \/>\nsolutions from the search also provides great performance benefits when<br \/>\nenumerating all solutions to a puzzle that has rotational symmetries.  Some of<br \/>\nthese techniques are easy to apply, others (like knowing when to start<br \/>\napplying the min-fit heuristic, or when to switch to the de Bruijn algorithm)<br \/>\nunfortunately require some combination of intuition, experimentation, or<br \/>\nexperience to use effectively.<\/p>\n<p>These types of puzzles are certainly a marvelous distraction and I<br \/>\nend this effort (at least for the time being) leaving many ideas unexplored.<br \/>\nI haven&#8217;t even examined the effectiveness of some of the techniques<br \/>\nI&#8217;ve implemented in the solver (e.g., the volume constraint backtrack<br \/>\ntrigger).  Correspondence with other folks interested in these puzzles<br \/>\nhas brought other promising strategies for attacking these types<br \/>\nof problems to my attention, but I must for now return to other more<br \/>\npractical projects.<\/p>\n<p><a name=\"references\"><\/a><\/p>\n<h2><span class=\"h2\">References<\/span><\/h2>\n<ul>\n<li>Donald Knuth, <a href=\"http:\/\/arxiv.org\/abs\/cs\/0011047\">Dancing Links<\/a>, Nov 2000.<\/li>\n<li>N.G. de Bruijn, <a href=\"http:\/\/alexandria.tue.nl\/repository\/freearticles\/597548.pdf\"><br \/>\nProgrammeren van de pentomino puzzle<\/a>, Euclides 47 (1971\/72), 90-104.<\/li>\n<li>Scott Kurwoski, <a href=\"http:\/\/scottkurowski.com\/tetriscube\/\">Tetris Cube<br \/>\nSolved<\/a>.  [Scott&#8217;s web pages inspired me to share my own software and his<br \/>\nsource code offered me my first view of the Fletcher\/de Bruijn algorithm.]<\/li>\n<li><a href=\"http:\/\/www.xs4all.nl\/~gp\/PolyominoSolver\/Polyomino.html\">Gerard&#8217;s<br \/>\nPolyomino Solution Page<\/a>  [Wonderful stuff.  His solver is really fast.<br \/>\nHe told me how it works in an email.  Pure genius.]<\/li>\n<li>David Goodger, <a href=\"http:\/\/puzzler.sourceforge.net\/docs\/puzzles.html\"><br \/>\nPolyform Puzzler: Puzzles and Solutions<\/a> [Really impressive.  The software<br \/>\nappears to be a python-based implementation of DLX, but I haven&#8217;t looked at<br \/>\nthe source myself.]<\/li>\n<li>Daniel Tebutt, <a href=\"http:\/\/www.danieltebbutt.com\/bedlam.html\">Bedlam Cube Solver<\/a>.<br \/>\n[The solver includes a graphical rendering of solutions via java applet.]<\/li>\n<li>Thorleif Bundg&aring;rd, <a href=\"http:\/\/www.fam-bundgaard.dk\/SOMA\/SOMA.HTM\">Thorleif&#8217;s SOMA<br \/>\npage<\/a>.  [I first learned of coloring tricks at this extensive website.<br \/>\nThorlief&#8217;s solver is written in BASIC.]<\/li>\n<li>Seppe Vanden Broucke, <a href=\"http:\/\/blog.macuyiko.com\/2009\/06\/solving-tetris-cube-recursive.html\"><br \/>\nSolving A Tetris Cube, Recursive Backtracking, Algorithm X, Oh My!<\/a>.  [The<br \/>\nsolver is written in PHP.]<\/li>\n<li>[<a href=\"http:\/\/www.math.missouri.edu\/~stephen\/\">Stephen<br \/>\nMontgomery-Smith<\/a> developed distributed processing facilities with which he<br \/>\nenumerated all solutions to some larger polyomino problems.]<\/p>\n<li>Josh Carrier, <a href=\"http:\/\/javadocs.wordpress.com\/2008\/09\/29\/project-complete-tetris-cube-solver-cloud\/\"><br \/>\nTetris Cube Solver Cloud<\/a>.  [Josh also setup a distributed processing<br \/>\nenvironment and enslaved some of his friend&#8217;s computers to solve the Tetris<br \/>\nCube.]<\/li>\n<li>Wikipedia, <a href=\"http:\/\/en.wikipedia.org\/wiki\/Polyomino\">Polyomino<\/a>.<\/li>\n<\/ul>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Image by Matt Busche I&#8217;ve implemented a set of backtrack algorithms to find solutions to various polyomino and polycube puzzles (2-D and 3-D puzzles where you have to fit pieces composed of little squares or cubes into a confined space). &hellip; <a href=\"https:\/\/www.mattbusche.org\/blog\/article\/polycube\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/posts\/26"}],"collection":[{"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/comments?post=26"}],"version-history":[{"count":4,"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/posts\/26\/revisions"}],"predecessor-version":[{"id":45,"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/posts\/26\/revisions\/45"}],"wp:attachment":[{"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/media?parent=26"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/categories?post=26"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mattbusche.org\/blog\/wp-json\/wp\/v2\/tags?post=26"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}