This article might contain pre-Unicode character-mapped APL code.
See here for details.
The MAGIC Goes Away - Opening the Boxes
Introduction
A year ago Bill McLean brought the game of MAGIC to the pages of Education Vector, Vector Vol.9, No.1 (pp.25-29). In the next issue, 9.2, Dave Ziemann discussed the game, and presented a method for solution and a set of APL*PLUS II functions to do the job. It was a quite brilliant treatment, but as Dave said, “I am left with the feeling that there’s probably a very simple way of knowing what key to press from any given state, but it eludes me for the moment.” Here is one way of doing just that. I want to share it with you because it throws light on some aspects of A-level-ish Mathematics. The APL is quite neat as well.
In case you don’t remember, in MAGIC you are given a starting 3×3 matrix or “box” of random 0s and 1s. You are asked to pick one or more of nine given standard boxes – I’ll call them MagicBoxes – to complement the starting box to achieve the target box, which we call win.
Bill’s article described a program to interact with the player, presenting the random starting box and showing the current position. Dave responded to his invitation to readers to provide solution algorithms.
Like Dave Ziemann, I’ve developed my solution mostly in terms of direct definition, but using first generation APL*PLUS version 8. I’ve also developed an analogous solution in J(4.1) rather to my surprise.
Representation
As in Dave’s treatment, I take a global zero index origin. I don’t want to rewrite all those parts of Dave’s article that apply here as well. He showed that it’s useful to be able to enumerate the 512 different possible states in a natural way as either decimal numbers 0 to 511 or as binary numbers 0 to 111111111 using some simple functions.
I’ve cribbed his functions DB and BD :
DB:1=(9⍴2)⊤ ⍵ BD:2⊥ ⍵ BD 0 0 1 1 1 1 0 1 1 123 DB 123 0 0 1 1 1 1 0 1 1
The functions SHOWBool and SHOWDec show states as 3×3 boxes:
sym ← '01' ⋄ blk ← ' ' SHOWBool: 3 0 ↑blk:0≠×/⍴ ⍵ :sym[3 3 ⍴⍉ ⍵ ],blk,SHOWBool 0 1 ↓ ⍵ SHOWDec:SHOWBool DB, ⍵ SHOWBool 9 1 ⍴ 0 0 1 1 1 1 0 1 1 ⍝ FN expects a matrix argument 001 111 011 SHOWDec 123 001 111 011
But I’m more interested in the method of solution than in presentation.
Why use McLean’s MagicBoxes?
The specified set of building blocks or MagicBoxes is
SHOWBool MagicBoxes 110 111 011 100 010 001 000 000 000 110 000 011 100 111 001 110 000 011 000 000 000 100 010 001 110 111 011
Dave Ziemann presents a “short MAGIC game”. Firstly, the function SetVars sets the scene, including choosing which boxes to play with – in this case MagicBoxes.
SetVars: key←BD⍎boxes←⍵ ⋄ sym←'01',blk←' '⋄ win←495 ⋄ ⍵←0↑⎕EX'BaseToKey' SetVars 'MagicBoxes' ⋄ 32 SHOWPATH win 0 5 6 110 001 000 110 001 110 000 001 110 000 110 111 111 100 010 011 101 000 000 001 111
BaseBoxes
But suppose we had a different set of boxes; one I call BaseBoxes:
SHOWBool BaseBoxes 100 010 001 000 000 000 000 000 000 000 000 000 100 010 001 000 000 000 000 000 000 000 000 000 100 010 001
We can easily see that the same problem can be solved – in more steps in this case:
SetVars 'BaseBoxes' ⋄ 32 SHOWPATH win 0 1 2 5 6 7 8 100 010 001 000 000 000 000 000 000 000 001 000 000 000 000 000 000 000 100 010 001 000 100 110 111 111 111 111 111 100 100 100 100 101 101 101 101 000 000 000 000 000 100 110 111
It is pretty obvious with this set of building blocks that we never need use more than nine moves. You can probably see quite easily that there is only one starting state for which nine is the minimum number of boxes, namely the complement of win,
SetVars 'BaseBoxes' ⋄ 16 SHOWPATH win 0 1 2 3 4 5 6 7 8 100 010 001 000 000 000 000 000 000 000 000 000 100 010 001 000 000 000 000 000 000 000 000 000 100 010 001 000 100 110 111 111 111 111 111 111 111 010 010 010 010 110 100 101 101 101 101 000 000 000 000 000 000 000 100 110 111
We can use more than the minimum number of moves for any solution, but only by adding some box 2 or 4 or 6 or any positive even number of times more than necessary.
Solution with BaseBoxes
The solution is intuitively obvious when we use BaseBoxes to provide the building blocks. We can also express it mathematically.
Given:
BD START ← 0 0 0 1 0 0 0 0 0 32 BD WIN ← 1 1 1 1 0 1 1 1 1 495 +BD ⎕← DIFF ← ADD START, [0.5] WIN 1 1 1 0 0 1 1 1 1 463
where
ADD: ≠ / ⍵
So we can easily solve a MAGIC puzzle using the unofficial set called BaseBoxes. But how do we solve a real puzzle with Bill McLean’s set, MagicBoxes?
Plus and Times for Boolean Numbers
We can think of ≠ for “Booleans” as equivalent to + (and ⍲ as well) for ordinary decimal numbers, since (for <=> read ‘is equivalent to’):
x ≠ y <=> 2 | x + y <=> 2 | x - y
The dyadic operation ≠ is the “sum” for the “Vector Space” to which the Binary representations of puzzle states belong.
It is obvious with either BaseBoxes or the original MagicBoxes that you can add them together any number of times, but that all even numbers are equivalent to doing nothing, while all odd numbers are just the same as only adding once. So we are discovering a system for “scaling” Boolean vectors x with integer numbers k such that
x + k y <=> x if 0 = 2 | k <=> x ≠ y if 1 = 2 | k
Suppose we know x and k and that
x <=> k z
What is z?
If k is odd, i.e. 1 <=> 2 | k, then
z <=> x
However, if k is even, both x and z must be null vectors. k cannot be even for non-zero x. This is not quite the same as when
X = 0 Z implies that Z is infinite unless X = 0.
We can in fact extend our system of scalar multipliers to include “rational numbers” of the form (p/q) where p and q are integers. If p/q is reduced to its lowest terms, p/q <=> 1 if both p and q are odd, <=> infinity if either is even.
Using BaseBoxes as a Basis
Let’s now return to our two sets of boxes. When we don’t use the SHOWBool function they appear as two 9×9 Boolean matrices:
(⍕MagicBoxes),(9 10⍴' '),⍕BaseBoxes 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1
Consider the third column of MagicBoxes
SHOWBool 9 1⍴ ⎕ ← MagicBoxes[;2] 0 1 1 0 1 1 0 0 0 011 011 000
This Boolean vector may be seen as signifying that the third Magic Box consists of the following elements of BaseBoxes:
0 1 1 0 1 1 0 0 0 / ⍳ 9 1 2 4 5 SHOWBool 9 1⍴ ≠ / BaseBoxes [; 1 2 4 5] 011 011 000
So we now know – trivially really – how to express MagicBoxes in terms of sums of BaseBoxes. And if we have a number of MagicBoxes – e.g. 0 5 6 as in Dave’s first example game – we can take their sum
≠ / MagicBoxes [; 0 5 6] 1 1 1 0 0 1 1 1 1
It is equivalent to the sum of BaseBoxes numbers 0 1 2 5 6 7 8 as we saw earlier:
≠ / BaseBoxes [; 0 1 2 5 6 7 8] 1 1 1 0 0 1 1 1 1
Using MagicBoxes as a Basis
We now need to be able to INVERT the process. Instead of expressing combinations of MagicBoxes in terms of BaseBoxes, we need to express BaseBoxes in terms of MagicBoxes. For example, starting from the knowledge that the set 0 1 2 5 6 7 8 of BaseBoxes solves a problem, how can we deduce that the set 0 5 6 of MagicBoxes does the same job?
Well, the 9×9 matrix MagicBoxes is really a transformation matrix from a representation with respect to the basis MagicBoxes to one in terms of BaseBoxes. For example, the vector
m ← 1 0 0 0 0 1 1 0 0 ⍝ <=> take MagicBoxes 0 5 6
is transformed to the vector
b ← 1 1 1 0 0 1 1 1 1 ⍝ <=> take BaseBoxes 0 1 2 5 6 7 8
using a Boolean Matrix multiplication function MULT
MagicBoxes MULT m 1 1 1 0 0 1 1 1 1
We can define MULT either by
MULT: ⍺ ≠ . ^ ⍵ ⍝ using Boolean operations
or by
MULT: 2 | ⍺ + . × ⍵ ⍝ using numeric add and multiply
Boolean Matrix Inversion
So let’s find a Matrix Inverse for the array MagicBoxes – the usual APL ⌹ almost does the trick, but not quite.
The second form of definition for MULT suggests that if
x = M y , for Boolean x and y and using Boolean matrix multiplication
then X = M Y , for numeric X,Y, 2 ¦ X <=> x, 2 ¦ Y <=> y and ordinary matrix multiplication, (+.×).
If there is a Boolean inverse IM for M, then Y = IM X
so y = 2 ¦ (IM M)(y + 2W) for some integer W
i.e. y + 2 Z = (IM M)(y + 2W) for some integer Z.
But if IM = ⌹ M then this condition is met as (IM M) is an identity matrix. However IM can contain non-integer rationals:
+IM ← ⌹ M ← MagicBoxes ¯0.2 0.4 ¯0.2 0.4 0.4 ¯0.6 ¯0.2 ¯0.6 0.8 0.6 ¯0.2 0.6 ¯0.2 ¯0.2 ¯0.2 ¯0.4 0.8 ¯0.4 ¯0.2 0.4 ¯0.2 ¯0.6 0.4 0.4 0.8 ¯0.6 ¯0.2 0.6 ¯0.2 ¯0.4 ¯0.2 ¯0.2 0.8 0.6 ¯0.2 ¯0.4 ¯0.2 0.4 ¯0.2 0.4 ¯0.6 0.4 ¯0.2 0.4 ¯0.2 ¯0.4 ¯0.2 0.6 0.8 ¯0.2 ¯0.2 ¯0.4 ¯0.2 0.6 ¯0.2 ¯0.6 0.8 0.4 0.4 ¯0.6 ¯0.2 0.4 ¯0.2 ¯0.4 0.8 ¯0.4 ¯0.2 ¯0.2 ¯0.2 0.6 ¯0.2 0.6 0.8 ¯0.6 ¯0.2 ¯0.6 0.4 0.4 ¯0.2 0.4 ¯0.2
We now recall that any odd scalar multiple of a Boolean vector is equivalent to the vector itself in our nine-dimensional vector space. The same applies to matrices:
Let:
+IM1 ← ⌹ MagicBoxes ÷ 5 ¯1 2 ¯1 2 2 ¯3 ¯1 ¯3 4 3 ¯1 3 ¯1 ¯1 ¯1 ¯2 4 ¯2 ¯1 2 ¯1 ¯3 2 2 4 ¯3 ¯1 3 ¯1 ¯2 ¯1 ¯1 4 3 ¯1 ¯2 ¯1 2 ¯1 2 ¯3 2 ¯1 2 ¯1 ¯2 ¯1 3 4 ¯1 ¯1 ¯2 ¯1 3 ¯1 ¯3 4 2 2 ¯3 ¯1 2 ¯1 ¯2 4 ¯2 ¯1 ¯1 ¯1 3 ¯1 3 4 ¯3 ¯1 ¯3 2 2 ¯1 2 ¯1
The divisor 5 is in fact the determinant of the matrix MagicBoxes!
b 1 1 1 0 0 1 1 1 1 2 | IM1 +.× b ⍝ which just happens to be the same as 1 0 0 0 0 1 1 0 0 m ⍝ ! 1 0 0 0 0 1 1 0 0
Unfortunately I’ve cheated. While we could in general take the ordinary inverse and try different odd integer scalars until we light on the right one, we strictly ought to calculate either the determinant of MagicBoxes:
DET MagicBoxes 5
(It is interesting that the J 4.1 determinant (-/ . *) threatens to take over four hours on a portable PC (Toshiba 1850) for this problem.)
... or to gain perhaps even more insight by using a special-purpose function
BINV MagicBoxes 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1
I cobbled BINV together from Keith Smillie’s INV function in STATPACK2
∇BINV[⎕]∇ [0] b←BINV a;k;s;p;i;is;t;u;⎕IO [1] ⍝ INVERT a SQUARE BINARY MATRIX... AFTER KW SMILLIE's STATPACK2 [2] ⍝ NB REAL ADD/MINUS BOTH BECOME ≠ [3] ⍝ REAL TIMES BECOMES ^ [4] ⍝ REAL DIVIDE SHOULDN'T BE NECESSARY AS DIVISOR is 0 OR 1 [5] ⍝ [6] ⍝ AN ALTERNATIVE METHOD is TO TAKE 2 | (DETERMINANT a) × ⌹ a [7] ⍝ BUT THAT NEEDS a DETERMINANT FUNCTION OF SIMILAR COMPLEXITY [8] ⍝ [9] ⎕IO←1 ⋄ →((×/×/b=a←2|b←a)^(2=⍴⍴a)^=/⍴a)/OK ⍝ CHECK a is OK [10] [11] NOINV:'NO INVERSE!' ⋄ →~b←1 [12] [13] OK:p←is←⍳s←k←⌊/⍴a ⋄ a←a[;p,1] [14] [15] LOOP:a[;1+s]←2>is ⋄ i←t⍳⌈/t←a[⍳k;1] ⍝ FIND NEXT ROW [16] p[t←1,i]←p[u←i,1] ⋄ a[t;is]←a[u;is] ⍝ SWAP ROWS [17] →(0=a[1;1])/NOINV ⍝ SINGULAR MATRIX [18] ⍝ DONT NEED ... a[1;]←a[1;]÷a[1;1] DIVISOR ALWAYS UNITY IF REACH HERE [19] a←a≠(a[;1]^1<is)∆.^a[1;] ⍝ WAS a - (a[;1] × 1 < is)∆.× a[1;] [20] a←a[t←1+s|is;1+is,0] ⋄ p←p[t] ⍝ SHIFT ROWS AND COLUMNS [21] [22] →(0<k←k-1)/LOOP ⍝ [23] b←a[;p⍳is] ⍝ REORDER FOR ANSWER
It is of course very similar to Smillie’s original, just replacing all ‘×’ by ‘^’ and both ‘+’ and ‘-’ by ‘≠’. Note that I disabled the line involving division by the pivot cell, since we have seen that Boolean “division” yields either no change or an infinity – and we expect the argument to be non-singular as we are dealing with basis representations.
Solution
It just remains to fit the various elements together. The function PATH does the job.
PATH:(KEY ADD DB ⍵ , ⍺ )/⍳⍴key
The arguments ⍺ and ⍵ are the decimal representations of the start and target boxes. ADD DB ⍵ , ⍺ finds the solution in terms of BaseBoxes.
ADD DB win, 32 1 1 1 0 0 1 1 1 1
The function KEY multiplies this by the Boolean Inverse of MagicBoxes, BaseToKey, calculating it in the function BaseRepToKeyRep if it does not exist. (We see now why SetVars expunges BaseToKey – it is in case a new set of MagicBoxes is invoked as the building blocks.)
BaseRepToKeyRep:BaseToKey:0=⎕NC'BaseToKey':BaseToKey←BINV DB key KEY:BaseRepToKeyRep MULT ⍵ SetVars 'MagicBoxes' ⋄ +m ← KEY ADD DB win, 32 1 0 0 0 0 1 1 0 0
Finally, the resulting Boolean vector is used to select the MagicBoxes,
m/⍳⍴key 0 5 6 32 PATH win 0 5 6
The remaining functions are just utilities or display routines.
Conclusions
The game of MAGIC as presented confuses the issue (probably intentionally!) in being apparently a two-dimensional problem with 512 states. However, as Dave Ziemann showed, we really have a 9-dimensional set of Boolean vectors. The decimal representation is helpful to my mind only to make the notation more concise. It does not add to our understanding of the transitions as Dave found. I suspect that instructive analogies might be drawn with other systems.
For example, theoretical physicists describe representations of microscopic space-time in terms of multiple (11?) dimensional strings embedded in 4 “real” dimensions. A Boolean number is a numerical realisation of the smallest possible non-trivial commutative “group” of order 2, so that our MAGIC game problem is a little like a simple physics with 9 different quantum properties, each with 2 alternative states. I gather that elementary particle theory teems with interacting “symmetry” groups, mostly built up from simple subgroups of order 2 or 3.
Casting aside speculation, we have found a concise, quick method of solution for MAGIC puzzles. There are symmetries which I have not pursued – the two-dimensional view may after all be useful! – e.g. the solutions for decimal 1, 4, 64 and 256 are all identical apart from rotation. (There are four corner boxes and four edge boxes and one middle. Various symmetry groups – order four and order two – relate corners together and edges together.) It’s possible that consideration of these symmetries might lead to an improvement in performance of Dave’s algorithm, but my method is so quick and simple that I haven’t followed up this particular line.
Duncan Pearson wondered if a similar vector space treatment involving inversion of a transformation matrix could be applied to the N-Queens problem. I don’t think so – at least I haven’t found it – the reason probably being that you can’t realise a presumably N-dimensional basis corresponding to the operation of “adding” a Queen.
However, the ubiquitous not-equal scan does make an appearance, even if not providing as much of the solution as Gérard Langlet’s views on the power of this construction would lead us to believe (e.g. Vector 9, No 3).
APL Functions
Here is a listing of all the APL functions involved. It’s only those few listed under “SolutionFunctions” that actually find the answer. The others are to do with setting up the problem (SetVars) and displaying one or more states (SHOWBool and SHOWDec) or the whole problem (SHOWPATH).
My version of Direct Definition – it’s not part of APL*PLUS as supplied – allows local variables, x, y and z, in addition to the arguments ⍵ (and ⍺ if the function is dyadic). The direct definition interpreter expects its functions to produce results.
Utility Functions
LAM: ⍺ ,[⎕IO-0.5] ⍵ ⍝ LAMINATE IN NEW 1ST DIMENSION SetVars: key←BD ⍎ boxes←⍵ ⋄ sym←'01',blk←' ' ⋄ win←495 ⋄ ⍵ ←0↑⎕EX 'BaseToKey'
SolutionFunctions
ADD:≠/ ⍵ BaseRepToKeyRep:BaseToKey:0=⎕NC 'BaseToKey':BaseToKey←BINV DB key BD:2⊥ ⍵ DB:1=(9⍴2)⊤ ⍵ KEY:BaseRepToKeyRep MULT ⍵ MULT: ⍺ ≠.^ ⍵ PATH:(KEY ADD DB ⍵ , ⍺ )/⍳⍴key
Display Functions
KEYPath:(0, ⍵ )LAM ⍺ ,key[⍵ ← ⍺ PATH ⍵ ] SHOWBool: 3 0 ↑blk:0≠×/⍴ ⍵ :sym[3 3 ⍴⍉ ⍵ ],blk,SHOWBool 0 1 ↓ ⍵ SHOWDec:SHOWBool DB, ⍵ SHOWPATH:(SHP0 ⍵ [1 1 ⍴⎕IO;])⍪SHP1(⍵ ← ⍺ KEYPath ⍵ )[1+⎕IO;] SHP0:1⌽[1+⎕IO]2⌽(- 0 2 4 +⍴ ⍵ )↑ ⍵ ← 4 0 ⍕ 0 0 1 ↓ ⍵ SHP1:((3 4 ⍴blk),SHOWBool DB,1↓ ⍵ )LAM SHOWBool scanADD DB ⍵ scanADD:≠\ ⍵ ∇DET[⎕]∇ [0] z←DET m;i;j;n;a;b;⎕IO [1] ⍝ FIND THE DETERMINANT OF m [2] ⍝ A METHOD THAT WORKS ... NOT OPTIMAL BUT >> THAN RECURSION! [3] ⍝ DET m EQUIV DET m' WHERE m'[i;] = m[i;] - k × m[j;] [4] ⍝ TRIES TO GET ZERO'S IN LOWER TRIANGLE (OFF DIAGONAL) [5] [6] ⍝ DET OF A TRIANGULAR MATRIX IS JUST THE PRODUCT OF THE [7] ⍝ DIAGONAL ELEMENTS [8] [9] →(^/^/m=m+.×⍉m)/ENDI,⎕IO←1 [10] i←(0,n←¯1↑⍴m)[1] [11] LOOPI:→(n≤i←i+1)/ENDI [12] j←i↓⍳n[1] [13] →(1E¯20≥|m[i;i])/ZERO [14] m[j;]←m[j;]-m[a;]×m[j;b]÷m[a←i↓b;b←n[1]⍴i] [15] →LOOPI [16] ZERO:→(^/b←0=i↓m[;i])/LOOPI [17] m[i;]←m[i;]+,(<\~b)/[1](i,0)↓m [18] i←i-1 [19] →LOOPI [20] ENDI: [21] ⍝ m SHOULD BE IN UPPER TRIANGULAR FORM [22] z←×/ 1 1 ⍉m