[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionA program to allow solution of "gunport" domino puzzles requiring that a board be covered with dominoes leaving the maximum number of gunports; squares the size of half a domino. Background & Techniques
Here's another puzzle I found in my "1000 Play Thinks" puzzle book. It belongs to a class of packing or covering type puzzles and has a broader background that I would have thought. It was invented Bill Sands in1971 and popularized by Martin Gardner in his Mathematical Games column for Scientific American (April 1974). Donald Knuth described this class of puzzle which he called "Exact Cover Problems" in a Dancing Links paper which unfortunately is only available in PostScript format at the link. One way to approach solving our puzzle programmatically would be to treat the gun ports as monominoes (1x1 squares) which converts the problem to an exact covering problem.. The best paper I found on this approach is this Chond and Blsch paper . I haven't worked on making this program solve the puzzles yet, but have implemented user play. There are 6 sample problems included ranging in size from 3x3 to 8x10 squares. To play, simply click adjacent empty squares to add a domino and click an occupied square to remove the domino. A congratulation message will reward the successful gunport count. Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now. Programmer's Notes:Not much new in the code so far. Clicks on the image are converted to column and row values which exist visually on the image and in a doubly dimensioned array (Board) of characters using "E' for empty, "L" and "R" for left and right halves of a domino, "U" and "D" for upper and lower halves of a domino, and 'X" for first click on an empty square. The code is well documented and should be easy to follow for those interested in more details. Addendum March 12, 2011: Version 2 posted today adds a "Solver" button to search for solutions. I implemented "Mod 4" of the LP (Linear Programming) solution algorithms defines in the Chond and Bosch paper referenced above. Those guys used a modeling language to implement their search and translating that to the equation formats required by the LPSolve module (introduced here in our LPDemo program) was an interesting challenge. As a refresher, linear programming tries to maximize or minimize an "objective function" subject to linear equations representing constraints. The input data is represented as a matrix of equation coefficients with a column for each variable and a row for each constraint equation. The Chond/Bosch model used define three arrays (H, V, and M) of binary variables (values 0 or 1), each with as many entries as there are cells on the board. H and V represent the left or upper cell of a Horizontal or Vertical domino, The M array represents "monominoes", the empty spaces surrounded by board edges or other H or V dominoes. LPSolve doesn't handle arrays of variables that I could find, so I generate a variable for each cell (for an 8 x 10 board this means 3*80 or 240 variables!) That also means a constraint equation for each cell checking that the sum of the H, V, or M for cell equals 1. The objective function for the setup is to maximize the sum of the M values. Other constraints insure that the sum of all Monominoes equals the calculated maximum number and some symmetry constraints to improve performance by preventing checking configurations that represent rotation or mirroring of ones already checked. Even with that, solving the 8x10 board required 13 hours of computer run time! Lot's of room yet to work on improving the solution times. There is also a bug somewhere that causes the 8x8 board solution to overlap two vertical dominoes. I optionally allow users to save solutions in a list of optimal solutions found so far. With one exception, I've attached optimal solutions for all boards up to 10x9. I invite anyone finding the optimal solution for 10x10 or the 11xN for larger N values, to send me the GunPortSolutions.stm file that will be built. (Check "Allow solution updates" when making these runs! Or, if you forget, you can always make screen shot of the solution and send it.) Addendum March 13, 2011: It didn't take long to produce the next update. Version 2.1 upgrades the LPSolve solver module from V5.1 to V5.5 which looks to be significant faster at finding solutions in the cases I've run so far. Addendum March 18, 2011: Oops. V5.5 of LPSolve doesn't solve as many cases as V5.1 (it ran 20 hours without solving the 7x8 case which V5.1 solved in an hour). Whether there is a problem with V5.5 or my implementation of it is unknown, but I reverted back to the 5.1 version and named it GunPorts512 Version 51.2. I did speed up solving cases with either rows or column is a multiple of 3. These cases have a trivial repeating pattern solutions which had been solved quickly only for the rows mod 3 = 0 case. I now swap rows and columns for solving when columns mod 3 = 0 and swap back and exchange horizontal and vertical dominoes for displaying the solution. March 22, 2011: Help! I'm working on this program and just can't stop! I decided to reorder the variables fed to LPSolve, so the the Horizontal, Vertical, and Monomino binary variables for each cell are interlaced, (H1, V1, M1, H2, V2, M2... HnVnMn instead of H1, H2,...Hn,V1,V2,...Vn, M1, M2,... Mn). This reduced solving time dramatically in some cases. The 7x7 case is now solved in 3 seconds compared to 2 hours for the previous version! However the10x10 board search ran for 49 hours before I stopped it with no solution found. I am , however, proud to include an optimal 10x10 solution found manually by overlapping a 4x10 solution whose last row pattern happened to match the top row pattern of a 7x10 solution. "More than one way to skin a cat" as we say here! There are still invalid results produced occasionally (overlapping dominoes) which I need to debug . Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |