2.0.2 January 6, 2018 This release was made to resolve a bad memory error I discovered last night (described below). The only other functional change was to add the printing of the date and time at program startup and just before program exit when the -i (info) option is enabled. Bug fixes: 1) The multi-dimensional array named "all" in class OrderingEntity was incorrectly dimensioned to numMobileShapes instead of numShapes causing memory corruption program failure. This bug was introduced in version 2.0, and could have affected any puzzle having stationary pieces. 2.0.1 November 25, 2018 Aside from the important bug fix (below), my implementation of the FILA algorithm was revised to look more like the web doc that describes it. I wrote the software before the document, and (as is typical) the process of trying to describe the algorithm very clearly resulted in something a little cleaner and simpler than the original implementation. (To be fair to myself, some of the original complexity was due to my desire to keep all data describing the state of the puzzle in the Puzzle object. To be consistent with the document, the occupancy state of the puzzle now only exists as stack variable in the recursive solveFila_* routines (and in subordinate method calls). As an aside, there are other data that would be better maintained in a similar fasion (i.e., as arguments to recursive solver methods) One example is the current parity state: currently the parity state has to be restored when a recursive call returns -- it would make things considerably simpler if this state variable was instead added to the argument list of the recursive solver routines so that the previous value would be restored simply by returning from the function. I may make more such changes in the future. Bug Fixes: 1) Depending on a number of conditions, the utility function lowestSetBit(__uint128_t bitField) produces erroneous results, causing some (or all) puzzle solutions to not be found. To be affected by the bug, all of the following had to be true. o Both of these preprocessor definitions had to have been set on the compile line used to build the solver program: -DUSE_GNU_BUILTINS -DGRIDBITFIELD_SIZE=128 (Note that the pre-compiled windows executable was NOT compiled with either of these options and therefore was NOT affected by this bug.) o FILA is enabled on the comand line (via the -f option). o The FILA setting was large enough that FILA operated on an unfilled puzzle region that was larger than 64. 2.0 September 14, 2018 New Features: 1) Fixed Image List Algorithm (FILA) replaces MCH, EMCH and de Bruijn algorithms. FILA comes with POF and NOF filtering. Read my blog entry on FILA for more information. 2) In previous releases, ordering heuristics were only available to DLX, but now all heuristics can be used by FILA as well. The heuristics behave slightly differently for the two algorithms. Read the help output for more information. 3) Improved performance made possible with FILA. For example my best times for finding all 9839 solutions to the tetris cube have imrpoved by almost a factor of 2 relative to what I could do with version 1.2.1 of this solver. Here's a timed run on that puzzle on my I3-4130T CPU @ 2.90GHz: time ./polycube -q -rL -f11 -oe=11:f=3 -n -- def/tetriscube.txt real 0m16.884s user 0m16.871s sys 0m0.013s So about 16.9 seconds. The best I can do with version 1.2.1 is about 31.6 seconds. (The performance of DLX is unchanged.) 4) Added a new compile option to set the size of the occupancy bit field. Use one of these three compile options to set it's size to 128, 64 or 32 bits. If unset, size 64 is used. -DGRIDBITFIELD_SIZE=128 -DGRIDBITFIELD_SIZE=64 -DGRIDBITFIELD_SIZE=32 5) Added a new compile settings specifically for gnu compiler that can improve FILA performance by giving certain heuristics access to silicon based bit counting operations. Add these compile options to enable this feature: -march=native -DUSE_GNU_BUILTINS 6) Added statistics on the number of DLX list delete operations which is useful for understanding the DLX work distribution. Remember that every list delete, is ultimately followed by an insert to undo the delete, so total linked-list operations is always double these numbers. 7) In support of research on puzzle parity, I added the following information to the output produced by the -i option: A) Added the printing of the puzzle's parity to informational output. B) Added the printing of the number of mobile images with negative parity to informational output. C) Added statistics showing how often an image is placed that moves the total parity of all placed pieces away from the target parity of the puzzle. 8) Added a compile option to eliminate statistics. (I was worried that all the statistics gathering might be slowing the algorithms, so I added a compile option to keep statistics out of the solver executable altogether. I did not see a significant performance change, but I left the option in place anyway.) You can add this to your compile line to eliminate all stat keeping: -DNO_POLY_STATS Bug fixes: 1) The -i option produced (among many other things) this information: # Piece rotations and translations that don't fit in the solution space: UNBOUNDED=9128 This was calculated by summing the number of allowed rotations of each piece and multiplying by the size of the puzzle space (after stationary pieces are placed) then subtracting off the number of mobile images that actually make it into the DLX matrix (the BOUNDED images). But when the rotational redundancy filter is enabled, one piece is constrained and fewer of its images make it into the DLX matrix. This was causing the UNBOUNDED image count to actually in crease (which is of course just silly). I discovered this as I was trying to get FILA published, and I did not want another delay, so I have not yet fixed this problem. As a work around, this statistic is no longer output when the redundancy filter is enabled. This statistic can be confusing anyway (even when it's working) as it is always from a 3D perspective. This is not the statistic most users would want for a 2D tiling problem. I'll try to address this issue as well when I get around to fixing the count when the redundancy filter is enabled. 2) The exit code was erroneously still set to zero when an exception was thrown. polycube now exits with exit code 1 on failure. 3) Fixed a for-loop bounds error that was causing some memory not to be deleted on program exit. Also added some code to delete a couple of singletons (yeah...i know...) on exit, so that no memory leaks are reported from memory leak checkers. 4) There was a DLX head pointer not getting initialized to NULL in a constructor. This was never getting read before getting set, and so was not really a bug, but it looked like a bug, so now it's getting initalized in the constructor like everything else. 5) Fixed a cut-n-paste error in makeArray4 and initArray4. This would have been a serious bug, but these methods were never used, so it did not affect program execution. Other changes: 1) The output format option has been renamed from -f / --format to -O / --output. This is because I wanted -f for fila. Probably a bad idea to shuffle the option names, but I'm pretty sure that none of my paying customers will care... 2) The software now makes now makes use of c++11 features. I'm now using override (a wonderful feature); I used a lambda to sort FILA grid point targets; and I switched to range-based for loops in several places (which really made things both more compact and far more clear); You'll need a c++11 compiler to build my software now. 3) The limited boost library excerpts I include as part of the download package has been updated to boost 1_64_0. I used boost's own bcp facility to try to extract the portions of boost used by my software. It spit a few disturbing warnings about not being able to resolve some preprocessor macros. Hopefully everything needed is included in my extract. I did test on a windows machine. If you see missing boost headers when trying to build, please let me know, but you can always just delete the boost_1_64_0 subdirectory that comes as part of polycube and just download your own copy of boost. 4) The string '_def' was deleted from all included puzzle definition files to shorten them. E.g., the definition pentominoes_10x6_def.txt is now named pentominoes_10x6.txt 5) There were many other minor software changes made primarily for aesthetical reasons. Many variables and classes were renamed (often just to shorten some long names that had become unweildy). Some of the performance measurement meters were renamed for consistent use of camelCase, and new meters were added. The const attribute was added to a few more methods as I noticed them. (I haven't scoured the code base looking for things that should have been declared const, so there are probably more. They haven't gotten in my way, so I haven't bothered.) I'm sure there were lots of other things I fussed with as well. 1.2.1 August 15, 2014 This release contains only documentation fixes. Corrected the help output for the -g and -R options which previously incorrectly referenced non-existent options. Modified the minimum description length for boost option_descriptions for better looking help output. Modified the paragraph formatting method of boost to eliminate some annoying leading spaces resulting from line breaks that happened to occur on sentence breaks. This change is cosmetic only and can be overwritten if you upgrade to a later release of boost. 1.2 April 10, 2014 New Features 1. I added a simple (and somewhat crude) mechanism for splitting a large puzzle into a set of smaller puzzles. To use it, you configure the maximum number of pieces to be placed via the -g option (the goal). When the goal is met, the current puzzle state is output and a backtrack is forced. In this way, a spanning set of subpuzzles is generated each of which can be subsequently passed back into the program to find the solutions to that subpuzzle. Currently the process of distributing the subpuzzles to other instances of the program, and the collection of the solutions found is a manual process; and so this feature leaves much to be desired. But there is at least now some way to solve larger puzzles. Care must be taken to ensure rotational uniqueness among solutions found when using this feature. The new -R option can be of some help in this regard. When you activate the -R option the piece used to eliminate rotational redundancy from the puzzle is forcibly placed first. Assuming this is successful in removing rotational redundancy from the solution set, you can be assured that solutions found from the set of subordinate puzzles will be collectively rotationally unique. 2. The -c option (for coordinate piece output) is replaced with the more flexible -f output format option, which allows selection of one of several output formats. One format is the SUBPUZZLE output format which can be combined with the -g option to output puzzle definitions that are subpuzzles of the input puzzle. Read --help output for more information. 3. To change the size of the integer used to store the IDs of pieces you now must set the preprocessor definition of PIECEID_SIZE to one of 8, 16, or 32. (Previously, you set the datatype PIECEID_T directly, but this approach was less safe.) Bug fixes: 1. My attempt to fix the a typecasting error seen in 64 bit development environments was botched in the previous release. (I don't have a 64 bit machine to test with.) I think I have finally fixed this problem. Thanks to Daniele Disco (from Italy) for both reporting this problem and testing the fix for me. 2. The script I used to identify which boost headers might be required by various build environments was flawed and missed many operating-system-specific, library-specific, and compiler-specific headers. I've improved the script and have identified many more system-dependent headers and now include them in the package. I'm still not completely confident I've got them all. (Boost headers include bizarre preprocessor scripting the likes of which I've never seen, that ultimately pick headers to include -- I refuse to try to decipher them.) In any case, remember that if you see missing headers from the boost library while compiling, you can correct this problem by simply replacing the boost extract I include with a fresh copy of the entire boost software package. Thanks to Daniele Disco for both identifying this problem and testing the fix. 3. A warning message is now output to stderr if a user attempts to configure a filtering threshold that is lower than the deactivation level for the DLX algorithm. Filters can only be used with DLX and are automatically deactivated (regardless of the user's settings) when one of MCH, EMCH or de Bruijn are activated. Previously the software quietly modified the user setting to be consistent with the activation settings of these other algorithms, but now noisily makes these modifications which will hopefully eliminate confusion among users that can't understand why nothing is getting filtered. 4. An error is now generated if you try to load a puzzle that has more pieces than can be uniquely identified with the defined PIECEID_T data type. By default PIECEID_T is a uint8_t (8 bit unsigned integer) and supports at most 255 pieces. To load puzzles with more pieces, you can recompile with preprocessor definition PIECEID_SIZE set to either 16 or 32. Other cleanups: 1. I replaced a few arrays of booleans used as filter controls with simpler integer scalers that work as filter activation thresholds. 2. Fixed a few getters in MonteCarloConfig.hpp which should have been declared const. 3. Fixed a few more comment typos. 1.1.3 December 14, 2012 Fixed a bug in the parser that was causing crashes when parsing a line from a puzzle definition that consisted of only a comment. I added a couple of (unsigned) typecasts to ParityMonitor.hpp and VolumeMonitor.hpp to (hopefully) fix a build problem associated with 64 bit implementations of the STL. (I don't have a 64 bit build environment to verify this fix.) Thanks to Stefan Westen for reporting this problem. I fixed several problems related to performance metering: 1. I fixed a problem in the puzzle parsing loop where the puzzle "parsing" PerformanceMeter was running while it's parent meter ("all") was not. 2. To catch such blunders going forward, I modified PerformanceMeter::start() and PerformanceMeter::stop() to verify that the parent meter (if any) is running at the time of these calls. 3. The print output for a tree of PerformanceMeters that have never been started (and therefore have zero elapsed time) was displaying some ugly division-by-zero noise for child meters in the percent-of-total-time fields. I modified these outputs to just forcibly display zero percent. (The percentages are actually meaningless in this case, and so perhaps printing asterisks would be more correct, but I somehow find them distracting.) 4. You've always been able to dump the stats of a PerformanceMeter and it's children while they're running. In this case (since the stop time is not yet recorded) a live reading is taken from the system clock. This was previously done independently for each meter during a recursive print request. Because the parent is printed first, the children end up using later stop time values which can ultimately lead to the sum of elapsed time of child meters exceeding the elapsed time of the parent. This behavior was surely both undesirable and confusing. To remedy the problem, I overloaded the PerformanceMeter's getTime and print methods to allow the use of a user-supplied value for the currentTime. See the comments for exact details. 5. Previously, PerformanceMeter output was only generated inside the Solver by a call to Solver::dumpStats(). Solver::dumpStats() in turn was called from two places: from a signal handler in response to signal 10 (an asynchronous user request for progress information) and at the end of solver processing if the info config option was set. The latter case is intended to provide a good estimate of total program processing time, but since it is invoked by the Solver, it can't include Puzzle destruction time. So I moved the call to PerformanceRegistry::print from Solver::dumpStats to the end of the puzzle processing loop in main.c. I still wanted PerformanceMeter output to be displayed in response to signal 10, so I also added a call to PerformanceRegistry::print directly from that signal handler. 1.1.2: August 11, 2012. In an early (unreleased) version of this software the piece id was a single character that doubled as the name. I subsequently introduced a separate string name field so that pieces could be assigned arbitrarily long names. The id field is now automatically assigned so that piece ids are numbered sequentially from 1 to N. I recently stumbled upon a few places in the software that were still working under the assumption that piece ids are user assigned and non-consecutive. Theoretically these flaws would cause program failure if you were to override the PIECEID_T preprocessor definition to increase the size of the pieceId data type from a char to a short and then try to solve a puzzle with more than 255 pieces, but I've never tested with such a large puzzle. Mostly it was just really confusing to anyone (including me) trying to read the code. I cleaned this stuff up. I modified Puzzle::genImageLists to throw an exception when you request automatic selection of a piece for rotational constraint when no uniquely shaped mobile piece is found. Previously, it silently ignored the user request in this case and just turned off rotational redundancy filtering. The boolean field Puzzle::redundancyComplexity was not getting set appropriately when complex rotational symmetries are identified in the puzzle. This can cause the rotational redundancy filter to fail for puzzles where stationary and mobile pieces share the same shape. I modified Puzzle::isSymmetric to set this field when complex rotational symmetries are detected. TEXT-ONLY changes: Various documentation fixes to README.txt, the generated help page and the software comments. 1.1.1: Fixed a ParityMonitor initialization problem that caused program crashes when all pieces of the puzzle had parity 0. Thanks to Andrew Juell for identifying this problem. Reworked both the Puzzle and Solver initialization so that initialization of the ParityMonitor and VolumeMonitor is skipped altogether if parity checks and volume checks are not requested by the user. Previously these monitors were always initialized (whether they were subsequently used or not). This is important because the amount of memory required by the VolumeMonitor grows geometrically with the number of uniquely sized pieces. Thanks to Andrew Juell for identifying this problem. Fixed a bug in solution numbering when rotationally unique solution filtering was activated. Previously the solution number was printed instead of the "unique" solution number. TEXT-ONLY changes: Added a couple of paragraphs to the README.txt file encouraging the use of the end-of-options declaration "--" on the command line. Added warnings to the help page on the memory requirements of the volume filter. Various documentation typo fixes. 1.0.1: Fixed software packaging problem for tgz download: boost and Mersene Twister libraries were missing. Also statically linked gcc and stdc++ libraries for the Windows executable. Thanks to Stefan Westen for identifying these problems. 1.0: Initial release.