``Quinto'' is a game played on a 5x5 grid of buttons, each of which is in one of two states (eg, black or white). When any button is clicked, the state of that button and each of its four neighbors (above and below, left and right) is inverted (black to white, white to black). The goal is to set all of the buttons to one color (simultaneously). The game is obviously generalizable to any size grid, and to arbitrary initial button states.
There are obvious questions: how, in general, is the game solved? Does every possible initial board (with a specified size and specified initial button states) have a solution?
This problem also appeared in the Berkeley Programming Contest in Fall 2000, as problem number one. The problems from that contest are available here in PDF format.
Before reading on, I suggest you play the game. If you have a Tcl/Tk interpreter (eg, wish) you can run Quinto.tcl. Otherwise you can try our Java applet implementation by Kaolin Fire.
Analyzing the game, the first obvious fact is that clicking a button twice is the same as not clicking it at all (negation composed with negation is the identity operation), and thus we only have to decide whether or not to click each button. Thus, we can represent any possible solution to the game played on an nxn board as an nxn array of boolean variables, where a value of true indicates that a button is clicked, and false indicates that a button is not clicked. For the following discussion, unless otherwise stated, it is assumed that all buttons start out in one state and the object is to convert them all simultaneously to the other state.
We can easily write down the requirements that a possible solution must satisfy to be an actual solution to the game. Consider the following general representation of a possible solution to the three-by-three form of the game:
a b c d e f g h i
I'll represent the variables from the possible solution with lower case letters, and the final button states with upper case letters. For instance, e is true iff the center button gets clicked, and E is true iff, after clicking the buttons indicated by {a,b,c,...,i}, the center button is in the second state. We can easily write the equations for {A, B, ...} in terms of {a, b, ... }:
A = a xor b xor c B = b xor c xor e xor a C = c xor f xor b D = d xor a xor e xor g E = e xor b xor f xor h xor d F = f xor c xor i xor e G = g xor d xor h H = h xor e xor i xor g I = i xor f xor h
We require than an actual solution have every button set, eg, the following holds:
Solved = A and B and C and D and E and F and G and H and I
Finding a solution to the puzzle is now reduced to satisfying the preceeding logical expression. Taking advantage of the following and other identities, we can reduce the expression to disjunctive normal form (see: boolean normal forms), from which we can read off the solutions.
x xor y = (x and (not y)) or ((not x) and y) [definition of xor] x and (y or z) = (x and y) or (x and z) [distributive property] not (x or y) = (not x) and (not y) [De Morgan's law] not (x and y) = (not x) or (not y) [De Morgan's law]
I found it expedient to implement these operations in Scheme (owing, probably, to a similar assignment from CS70) in which logical operations are written in prefix notation. For instance, a and b and c will be written (and a b c).
The logical expression for a solution to the 3x3 puzzle may be expressed as:
(make-and
(make-xor 'a 'b 'd)
(make-xor 'b 'c 'e 'a)
(make-xor 'c 'f 'b)
(make-xor 'd 'a 'e 'g)
(make-xor 'e 'b 'f 'h 'd)
(make-xor 'f 'c 'i 'e)
(make-xor 'g 'd 'h)
(make-xor 'h 'e 'i 'g)
(make-xor 'i 'f 'h))
And the scheme interpreter spits out the disjunctive normal form equivalent. Notice that a DNF expression is composed of the disjunction ("or") of a series of terms, each of which is the conjunction ("and") of one or more boolean variables (literals), each of which may possibly be negated. Thus each term represents a distinct solution to the puzzle. If a literal is plain (not negated) then the corresponding button must be clicked in this solution, otherwise it must not be clicked:
(and i (not h) g (not f) c e a (not b) (not d))
Evidently, for the 3x3 case, there is only a single solution, in which {a,c,e,g,i} must be clicked, and {b,d,f,h} must not be clicked. Visually (dark indicating that a button must be clicked):
a b c d e f g h i