### Problem Description

A 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