1. Introduction

The "Gunport Problem" was originated by Bill Sands (1971) and popularised by Martin Gardner in his long-running Mathematical Games column for Scientific American (April 1974). The original paper by Sands is available online at JSTOR and an extract from Gardner's article is reprinted in "The Colossal Book of Short Puzzles and Problems". We introduce the problem by way of the following quote from Sands' paper.

The "holes" are analogous to ports in the sides of a warship or fortress through which cannons may be aimed. The problem is to identify arrangements of dominoes on arbitrary sized boards that maximize the number of holes left vacant or, equivalently, minimize the number of dominoes placed. The following 5x5 solution containing 7 holes is given as an example.

2. Formulation I

In a first attempt at formulation we begin with a number of dominoes (p) sufficient to cover the board with at most a single cell vacant, floor(mn/2) (where m = rows and n = columns). This is naive upper bound on the number of dominoes required. We define sets M = 1..m, N = 1..n, P = 1..p and decision variables x_i,j,k = 1 if cell {i,j} is occupied by domino k and variables d_k = 1 if domino k is used. The objective is to minimize the number of dominoes used subject to constraints that ensure that a domino, if placed, covers two adjacent cells, each cell is covered by, at most, a single domino and, finally, no two adjacent cells are vacant.

1. Used dominoes in adjacent cells.

2. Domino, if placed, covers two cells.

3. Each cell covered by, at most, one domino.

4. No two adjacent cells vacant (rows).

5. No two adjacent cells vacant (columns).

An OPL model of this formulation is here. The performance of this model is wholly unimpressive with only a 4x4 grid solved in a reasonable amount of time. Inspection of the solution procedure reveals that a solution is found rather quickly but the branch-and-bound procedure continues to look for a better solution which does not, in fact, exist.

3. Formulation II

A couple of insights into the nature of solutions to Gunport problems will allow us to modify and improve the above model. Bill Sands (1971) proved that if mod(m,3) or mod(n,3) = 0 then p = mn/3 (where m = rows, n = columns and p = optimum number of dominoes). This may be achieved using a simple repeating pattern. Murray R. Pearce later conjectured that if mod(m,3) = mod(n,3) then p = (mn+2)/3 or if mod(m,3) mod(n,3) then p = (mn+1)/3 (see Gardner). We may use these insights to amend the above formulation. The objective now is to place p dominoes in accordance with the conditions of the puzzle. We no longer need the objective function or the d_i,j variables and constraints (2) are amended to:

An OPL model of this modified formulation is here. This improved model found solutions up to and including the 7x7 board but thereafter the processing time increases dramatically and no result was obtained for an 8x8 board after 5 hours. This was quite disappointing as a solution to an 8x10 board was found by Captain John C. Huvall in 1975 (see Gardner, 2006).

4. Formulation III

An alternative approach is to define a three dimensional array DC where dc_i,j,k = 1 if cell {i,j} is covered when a domino is in position k, 0 otherwise. Decision variables x_k = 1 if position k adopted, 0 otherwise. We also need variables y_i,j = 1 if cell {i,j} covered, 0 otherwise. We include constraints to ensure that each of p dominoes is placed, each cell is covered by, at most, a single domino and finally, as above, no two adjacent cells are vacant. An OPL model of this re-formulation is here.

The improvement in solution times enjoyed by this approach is quite dramatic. For example, the 8x10 problem was unsolved after seven days using the modified initial formulation above whereas this re-formulation found a solution in less than four seconds.

5. Formulation IV

A final approach considers the equivalent problem of filling a rectangle with monominoes and dominoes so that no two monominoes are adjacent and the number of monominoes is minimized (or a specified number of monominoes is placed). In this case three sets of decision variables are defined.

h_r,c = 1 if a domino is placed horizontally with its leftmost square covering square {r,c}

v_r,c = 1 if a domino is placed vertically with its topmost square covering square {r,c}

m_r,c = 1 if a monomino is placed in square {r,c}

One set of constraints ensures that each square is covered exactly once (by a horizontally placed domino, a vertically placed domino, or a monomino).

Another set of constraints prevents us from putting two monominoes next to each other.

Two additional sets of constraints eliminate symmetries. They make sure that the bottom half of the board contains at least at least as many monominoes as the top, and the right half contains at least as many as the left half. These symmetry constraints are important in that they have a marked effect on solution times. An OPL implementation of this approach is here.

Experimentation with this final approach demonstrates its superiority over the previous method. For moderate sized boards the improvement is already noticeable but as the board size increases the differences in solution times rapidly become much more pronounced.

6. Comparison of methods

The following table of solution times for a range of board sizes allows for a direct comparison of the four methods.

The marked differences in solution times witnessed by the above table provide an emphatic demonstration of the benefits that may be gained by the re-formulation of difficult problems.

A solution for board size 11x11 with 39 holes is as follows.

7. Final note

An interesting modification of the Gunport problem may be found at Tim's Interactive Puzzle Solution Center. An additional requirement is that no domino can slide in any direction. Further constraints may be added to the above models to enforce this condition and this is left as an exercise for the reader.

References

Gardner, M. (2006), The Colossal Book of Short Puzzles and Problems, W.W. Norton & Company.

Sands, B. (1971), The Gunport Problem, Mathematics Magazine, Vol. 44, pp. 193-196

	To download a printable version (pdf) of this paper, click here. To download the Adobe Acrobat reader for viewing and printing pdf files, click here.
	To reference this paper, please use:  Chlond, M. J. and R. Bosch (2006), "The Gunport Problem," INFORMS Transactions on Education, Vol. 6, No 2,  http://ite.pubs.informs.org/Vol6No2/ChlondBosch/