|
|
|
|
|
|
|
|
|
This page outlines the theory behind the game. It will be useful to those who grabbed the page out of curiosity only to find obscure sums and multiplications of several quantities in JavaScript code which does not actually reveals the algorithm. The explanation is by necessity short but provides sufficient information for further search and study. Probably any book encompassing High School Algebra I&II will do although it's unlikely to consider higher (beyond 3 as, for example, 9) dimensionality spaces. For further reading find beginner's books on Linear Algebra.
There are two keywords to what follows: boolean system and 9-dimensional vector space. Every checkbox may be in one of two states: it's either checked or unchecked. The notion is quite suggestive but does not yet make it to the class of boolean numbers as they are commonly understood.
What makes numbers numbers is their relationship to other numbers. For example, one would expect to be able to add and multiply two numbers. Boolean arithmetic is extremely simple and is based on the following two tables:
|
|
The second table is unexceptional and only means that 0 times any number gives 0 whereas 1 times a number gives that same number. The first table brings one surprise though, viz.,
1 + 1 = 0.
As with all other number systems we also have
1 - 1 = 0.
Now, a 9-dimensional vector is a sequence v = (v1, v2, ..., v9). Vector v is boolean if all its components vi, i = 1, 2, ..., 9, are either 0 or 1. But again calling a sequence a vector only makes sense if it's done in its relationship to other similar entities.
Thus let there be two vectors v, as above, and u defined similarly:
u = (u1, u2, ..., u9)
Their addition u + v is defined componentwise, i.e.,
(u + v)i = ui + vi.
Multiplication by a number s is also defined componentwise:
(su)i = sui.
Returning to the game, let enumerate all 9 squares from left to right and from the top row downwards:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
Both the original and target square configurations could then be described using 9-dimensional boolean vectors where in the i'th position stands 1 if the corresponding box is checked and 0 otherwise. Let us call this vectors vo and vT, respectively. Clicking the checkbox #1 on the right board adds to vo the vector (1, 1, 0, 1, 1, 0, 0, 0, 0). As another example, clicking on the box #6 adds the vector (0, 0, 1, 0, 0, 1, 0, 0, 1). Thus, one may construct nine vectors, say, v1, ..., v9 each corresponding to a click on one of the checkboxes in the right square. The problem of solving the game might then be reformulated as:
Find boolean s1, s2, ..., s9 such that vT = vo + s1v1 + ... + s9v9
where si = 1 if and only if the box #i must be clicked on in order to solve the problem. This is a system of 9 linear equations that could be rewritten as
vT - vo = vT + vo = s1v1 + ... + s9v9
And in matrix notations it will look like vT + vo = sV where 9x9 matrix V is composed of vectors vi. Finally,
s = (vT + vo)V-1.
I computed inverse V-1 using MathCAD 6.0 which is a pleasure to use due to its power and abundance of various features. Sure enough, the result was a rational 9x9 matrix which is too cumbersome to cite. However, it brings one important point. Boolean operations may actually be viewed as operations in modulo 2 arithmetic. Then 1 + 1 = 0 is interpreted as the fact that the sum of two odd numbers is even. Other entries in the tables above may be interpreted in a similar fashion. If you ever get V-1, the following remark will help you reduce it to the boolean one below.
Remark
Since in the arithmetic modulo 2, 1 + 1 + 1 + 1 + 1 = 1,
one may claim that 1/5 = 1.
Here then the promised boolean inverse of the matrix V:
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
The fact that the above matrix is invertible is equivalent to the assertion that vectors v1, ..., v9 form a basis in the 9-dimensional space. A simpler basis is formed by nine vectors each sporting a single 1 in a different position. Selecting a basis of vectors with binary coordinates generates a different game. As an example, I coded three games that are played by different rules.
Further details can be found in
Don Pelletier, Merlin's Magic Square, The American Mathematical Monthly, v94, n2, 1987, p143-150.
P.S. You can check your understanding of the above material by trying to solve the following
Problem
In a 4x4 chessboard, all squares are colored white or black. Given an
initial coloring of the board, we are allowed to recolor it by changing the
color of all squares in any 3x3 or 2x2 subboard. Is it possible to get
every possible recoloring of the board from the "all-white" coloring by
applying some number of these "subboard recolorings"?
I picked it up from Tangents, a delightful Harvard University student publication. I enjoyed several articles in this interactive magazine that also offers a problem column.
Solution
| 28680680 |  |
|