Given a \(n \times n\) grid of panes, the objective of the Abbott’s Window puzzle is to maximize the number of lighted panes subject to the constraint that the number of lighted panes in every row, column, and diagonal is even.
Solve the Puzzle
Select the size of the window (choose a value for \(n\) between 4 and 8). Then, enter a “1” in a square to light a window pane. (The corner squares do not count as diagonals.)
|
Window Size |
Problem Statement
Note that the text of this problem statement is taken from H.E. Dudeney (1917).
Once upon a time the Lord Abbott of St. Edmondsbury, in consequence of “devotions too strong for his head,” fell sick and was unable to leave his bed. As he lay awake, tossing his head restlessly from side to side, the attentive monks noticed that something was disturbing his mind; but nobody dared ask what it might be, for the Abbott was of a stern disposition, and never would brook inquisitiveness. Suddenly he called for Father John, and that venerable monk was soon at the bedside.
“Father John,” said the Abbott, “dost thou know that I came into this wicked world on a Christmas Even?”
The monk nodded assent.
“And have I not often told thee that, having been born on Christmas Even, I have no love for the things that are odd? Look there!”
The Abbott pointed to the large dormitory window, of which I give a sketch. The monk looked and was perplexed.
“Dost thou not see that the sixty-four lights add up to an even number vertically and horizontally, but that all the diagonal lines, except fourteen are of a number that is odd? Why is this?”
“Of a truth, my Lord Abbott, it is of the very nature of things, and cannot be changed.”
“Nay, but it shall be changed. I command thee that certain of the lights be closed this day, so that every line shall have an even number of lights. See thou that this be done without delay, lest the cellars be locked for a month and other grievous troubles befall thee.”
Father John was at his wits’ end, but after consultation with one who was learned in strange mysteries (integer programming), a way was found to satisfy the whim of the Lord Abbott. Which lights were blocked up, so that those which remained added up to an even number in every line horizontally, vertically, and diagonally, while the least possible obstruction of light was caused?
The man who was “learned in strange mysteries” pointed out to Father John that the orders of the Lord Abbott of St. Edmondsbury might be easily carried out by blocking up [a certain number] of the lights in the window. Father John held that the four corners should also be darkened, but the sage explained that it was desired to obstruct no more light than was absolutely necessary, and he said, anticipating Lord Dundreary, “A single pane can no more be in line with itself than one bird can go into a corner and flock in solitude. The Abbott’s condition was that no diagonal lines should contain an odd number of lights.”
Therefore, the problem is as follows. Consider a window made up of a grid with 8×8 panes of glass. In each vertical and horizontal direction, there is an even number of glass panes (8). However, there are 14 diagonals with an even number of glass panes and 16 diagonals with an odd number of glass panes. Darken the smallest number of glass panes such that all rows, columns, and diagonals (not including the corner squares as diagonals) have an even number of glass panes not darkened.
Mathematical Formulation
The Abbott’s Window puzzle can be formulated mathematically as a mixed integer linear programming problem.
Parameters
\(n\) = number of rows/columns
Variables
\(x_{ij}\) = 1 if the pane in row \(i\) and column \(j\) is lighted, 0 otherwise
\(y_i\) = integer variable for row \(i\)
\(w_j\) = integer variable for column \(j\)
\(z_{1k}\), \(z_{2k}\), \(z_{3k}\), \(z_{4k}\) = integer variables for the diagonals
Objective Function: Maximize the total number of panes with lights
maximize \(\sum_{i=1}^n \sum_{j=1}^n x_{ij}\)
Constraint1: The number of lighted panes in row \(i\) must be even.
\(\sum_{j=1}^n x_{ij} = 2 y_i, \forall i=1..n\)
Constraint 2: The number of lighted panes in column \(j\) must be even.
\(\sum_{i=1}^n x_{ij} = 2 w_j, \forall j=1..n\)
Constraint 3: The number of lighted panes in each lower left diagonal must be even.
\(\sum_{j=1}^{n-k+1} x_{k+j-1,j} = 2 z_{1k}, \forall k=1..n-1\)
Constraint 4: The number of lighted panes in each upper right diagonal must be even:
\(\sum_{i=1}^{n-k+1} x_{i,k+i-1} = 2 z_{2k}, \forall k=2..n-1\)
Constraint 5: The number of lighted panes in each lower right diagonal must be even:
\(\sum_{i=k}^n x_{i,n-i+k} = 2 z_{3k}, \forall k=2..n-1\)
Constraint 6: The number of lighted panes in each upper left diagonal must be even:
\(\sum_{j=1}^k x_{k-j+1,j} = 2 z_{4k}, \forall k=2..n\)
To solve this mixed integer linear programming problem, we can use one of the NEOS Server solvers in the Mixed Integer Linear Programming (MILP) category.
GAMS Model
Here we provide a GAMS model for the specific instance of an 8 x 8 grid of window panes. Note that the GAMS model describes the diagonal constraints explicitly, one for each diagonal, instead of the algebraic representation as in the formulation presented above. It is easy to change the model to a different size of \(n\): (1) in the ‘set row /1*8/;’ statement, change the number 8 to \(n\), (2) in the ‘set D /1*13/;’ statement, change the number 13 to the value of \((2(n-1) – 1)\), and (3) in the ‘rightdiag(I,J,D) = yes\$(ord(i)-ord(j)=ord(D)-7);’ statement, change the number 7 to \((n-1)\).
Set row /1*8/;
alias(row, i, j);
Set D /1*13/ ;
Set leftdiag(I, J, D);
Set rightdiag(I, J, D);
leftdiag(I, J, D) = yes \$(ord(i)+ord(j)=ord(D)+2);
rightdiag(I, J, D) = yes \$(ord(i)-ord(j)=ord(D)-7);
Variables
z total number;
Binary Variables
x(i,j) set to one if pane is lit;
Integer Variables
y(i) number of entries in rows
w(j) number of entries in columns
z1(D) number of entries in each left diagonal
z2(D) number of entries in each right diagonal;
Equations
ans define objective function
rows(i) constraint for rows
cols(j) constraint for cols
diagL(D) constraint for left diagonal
diagR(D) constraint for right diagonal;
ans.. z =E= sum((i,j), x(i,j));
rows(i).. sum(j, x(i,j)) =E= 2*y(i);
cols(j).. sum(i, x(i,j)) =E= 2*w(j);
diagL(D).. sum((i,j)\$(leftdiag(i, j, D)), x(i,j)) =E= 2*z1(D);
diagR(D).. sum((i,j)\$(rightdiag(i, j, D)), x(i,j)) =E= 2*z2(D);
model abbott /all/;
solve abbott using mip maximizing z;
display x.l;
References
- H.E. Dudeney. Amusements in Mathematics. Thomas Nelson and Sons, 1917. Available at The Project Gutenberg eBook 16713.
- T. Hurlimann. Solving and Running Models through the Internet.