The MAGIC Puzzle

contributed by Bill McLean

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 25

In response to our request for functions, W.W. McLean (Dunoon, Argyll) contributes two games — the first is called MAGIC and involves manipulation of a 3 x 3 matrix, and the second is the well-known OXO or noughts-and-crosses (tic-tac-toe) game.

Magic¶

The instructions for this game are provided as an option in the function. A randomly selected matrix of 0s and 1s is presented, and the player is asked to select from a standard set of matrices (also 0s or 1s). The selected matrix is used to complement some of the values in the original matrix. The aim is to get a matrix of 1s with a lone 0 in the centre.

The instructions are printed after the function for convenience.

    ∇ MAGIC;A;GRID;K;L;LINE;LINE1;LINE4;M;MARGIN;NOS;WIN
[1]        ⎕←GRID← 3 3 ⍴((?9⍴2)-1) ⋄ GRID← 3 3 ⍴0 ⋄ GRID[2;1]←1
[2]        WIN← 3 3 ⍴ 1 1 1 1 0 1 1 1 1
[3]        A← 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 0 0
[4]        A←A, 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0
[5]        A←A, 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 1
[6]        NOS← 9 3 3 ⍴A
[7]        'Would you like instructions?  Y/N'
[8]        →('YN'=⍞)/INSTR,START
[9]  INSTR:
[10]       ''
[11]       ''
[12]       ''
[13]       ''
[14]       MARGIN← 3 6 ⍴' '
[15]       ⎕←LINE← 1 27 ⍴' '
[16]       ⎕←K←(⍕NOS[1;;]),[2]MARGIN,(⍕NOS[2;;]),[2]MARGIN,[2](⍕NOS[3;;])
[17]       ⎕←LINE
[18]       ⎕←LINE1← 1 27 ⍴' 1          2          3  '
[19]       ⎕←LINE
[20]       ⎕←L←(⍕NOS[4;;]),[2]MARGIN,(⍕NOS[5;;]),[2]MARGIN,[2](⍕NOS[6;;])
[21]       ⎕←LINE
[22]       ⎕←LINE4← 1 27 ⍴' 4          5          6  '
[23]       ⎕←LINE
[24]       ⎕←M←(⍕NOS[7;;]),[2]MARGIN,(⍕NOS[8;;]),[2]MARGIN,[2](⍕NOS[9;;])
[25]       ⎕←LINE
[26]       ⎕←LINE4← 1 27 ⍴' 7          8          9  '
[27]       ⎕←LINE
[28]       'By pressing any number (1 - 9), you can see which group of boxes,'
[29]       'marked 1''s, will be complemented: 0 to 1, 1 to 0.'
[30]       'The object is to get a centre 0 surrounded by 1''s'
[31]       ⎕←WIN
[32]       ' '
[33]       ⎕←GRID
[34] START:'WHICH KEY? 1 - 9'
[35]       ⎕←GRID←(NOS[⎕;;]≠GRID)
[36]       →(∧/,(WIN=GRID))/END
[37]       →START
[38]   END:' GOOD! A WIN!'
    ∇

Instructions¶

 1 1 0       1 1 1       0 1 1
 1 1 0       0 0 0       0 1 1
 0 0 0       0 0 0       0 0 0

  1           2           3

 1 0 0       0 1 0       0 0 1
 1 0 0       1 1 1       0 0 1
 1 0 0       0 1 0       0 0 1

  4           5           6

 0 0 0       0 0 0       0 0 0
 1 1 0       0 0 0       0 1 1
 1 1 0       1 1 1       0 1 1

  7           8           9

By pressing any number (1 - 9), you can see which group of boxes,
marked 1's, will be complemented: 0 to 1, 1 to 0.
The object is to get a centre 0 surrounded by 1's
 1 1 1
 1 0 1
 1 1 1

Example Game¶

 0 0 0
 1 0 0
 0 0 0
WHICH KEY? 1 - 9
⎕:
      7

 0 0 0
 0 1 0
 1 1 0
WHICH KEY? 1 - 9
⎕:
      1

 1 1 0
 1 0 0
 1 1 0
WHICH KEY? 1 - 9
⎕:
      6

 1 1 1
 1 0 1
 1 1 1
GOOD! A WIN!

Any offers of an algorithm (in APL of course) to solve MAGIC problems?

OXO (Noughts and Crosses)¶

Mr McLean’s second game is already designed to be played against the computer. The positions on the noughts-and-crosses board are labelled:

1 2 3
4 5 6
7 8 9

The player (human) plays X and the computer plays O. You are offered the choice to play first or second, and the board is displayed after each move.

The variable REFTABLE contains all the possible winning positions:

This is used to index other arrays. The BOTH array fills up with 1s (for the human i.e. X) or 10s (for the computer i.e. O)

The algorithm used by the computer is simple. It first checks whether it can win (a row in 8 3 ⍴BOTH[REFTABLE] which adds up to 20). If a computer win is not possible, it checks for a human win (a row adding up to 2) and blocks if necessary. Otherwise the computer prefers to play the centre (if it gets the chance), a random empty corner, or just any square available.

The computer does not always win. Any offers of a better algorithm?

  ∇ GO;BOARD;BOTH;COMPUTER;HUMAN;KK;M;NEWBOARD;P;Q;RANDOMC;RC;REFTABLE;ROW;T;Z
[1]    SETUP
[2]    'WHO PLAYS FIRST? (H)uman or (C)omputer or (Q)uit?'
[3]    KK←⍞
[4]    →(KK='HCQ')/L1,L2,L3
[5]  L1:INPUT
[6]  L2:DEFENSE
[7]    →L1
[8]  L3:→
    ∇

    ∇ SETUP
[1]   BOARD←⍳9
[2]   COMPUTER←HUMAN←BOTH←9⍴0
[3]   NEWBOARD←9⍴'.'
[4]   REFTABLE←1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 1 5 9 3 5 7
    ∇

    ∇ DEFENSE
[1]   'MY MOVE'
[2]   ''
[3]   ⍝ CHECK 20
[4]   T←+/Z←8 3⍴BOTH[REFTABLE]     ⍝ Index into 1's and 10's. Add rows.
[5]   P←T⍳20                       ⍝ Any sum of 20: which row?
[6]   M←T∊20
[7]   →((∨/M)=0)⍴L6
[8]   ROW←(8 3⍴REFTABLE)[P;]
[9]   Q←(+/ROW)-+/(8 3⍴((COMPUTER+HUMAN)[REFTABLE]))[P;]
[10]  →END
[11] L6: ⍝ CHECK2
[12]  T←+/8 3⍴BOTH[REFTABLE]
[13]  P←T⍳2
[14]  M←T∊2
[15]  →((∨/M)=0)⍴L7
[16]  ROW←(8 3⍴REFTABLE)[P;]
[17]  Q←(+/ROW)-+/(8 3⍴((COMPUTER+HUMAN)[REFTABLE]))[P;]
[18]  →END
[19] L7: ⍝ CENTER
[20]  →(NEWBOARD[5]≠'.')/L8
[21]  Q←5
[22]  →END
[23] L8: ⍝ ANY CORNER
[24]  RANDOMC←4?4
[25]  RC←(1 3 7 9)[RANDOMC]
[26]  T←NEWBOARD[RC]∊'.'
[27]  Q←1↑T/RC
[28]  →(Q=0)⍴L9
[29]  →END
[30] L9: ⍝ Any square left
[31]  Q←NEWBOARD⍳'.'
[32] END: ⍝ Assign to chosen position
[33]  COMPUTER[Q]←Q
[34]  BOTH[Q]←10
[35]  NEWBOARD[Q]←'O'
[36]  ''
[37]  SBWC
    ∇

    ∇ INPUT
[1]   'YOUR MOVE!'
[2]   Q←⎕
[3]   →((Q>0)∧(Q<10))⍴L2     ⍝ Q is between 1 & 9
[4]   'TRY AGAIN'
[5]   →1
[6]  L2:
[7]   →(BOTH[Q]=0)⍴L3        ⍝ Square is not occupied
[8]   'TRY AGAIN'
[9]   →1
[10] L3:BOTH[Q]←1
[11]  HUMAN[Q]←Q
[12]  NEWBOARD[Q]←'X'
[13]  SHOWBOARD
[14]  WINCHECK     ∇

    ∇ SBWC
[1]   SHOWBOARD
[2]   WINCHECK
    ∇

    ∇ SHOWBOARD
[1]   3 3⍴NEWBOARD
    ∇

    ∇ WINCHECK;K;L
[1]   K←(1=(,BOTH))/⍳9
[2]   L←(,REFTABLE)∊K
[3]   L←+/(8 3⍴L)
[4]   →(∨/(L=3))⍴L11
[5]  L5:K←(10=(,BOTH))/⍳9
[6]   L←(,REFTABLE)∊K
[7]   L←+/(8 3⍴L)
[8]   →(∨/(L=3))⍴L13
[9]   →(∧/(NEWBOARD≠'.'))⍴L15
[10]  →0
[11] L11:'YOU WIN'
[12]  →
[13] L13:'I WIN'
[14]  →
[15] L15:'A DRAW'
[16]  →
    ∇