The 10th International Congress on Mathematical Education,  July 4-11, 2004, Copenhagen, Denmark

TSG4: Activities and Programs for Gifted Students

 scarecrow.gif

ACTIVITY OF A GIFTED STUDENT WHO FOUND  LINEAR ALGEBRAIC SOLUTION OF BLACKOUT PUZZLE 

 

Sang-Gu Lee (Sungkyunkwan Univ. KOREA)

 sglee@skku.edu

 

Abstract

 

The purpose of this paper is to introduce an activity of student who found purely linear algebraic solution of the Blackout puzzle which was introduced in the official homepage of movie "Beautiful mind". It shows how we can help and work with gifted students. We also introduce a software which veryfies this solution. This process and algorithm can be extended to the fullsize Go board problem.

 

 Key words

Blackout puzzle, linear algebra, basis, algorithm, mod 2 arithmetic.

  

0. Introduction

 

    Gifted students often see some aspects that others don’t see.

   

We were talking on the movie "A Beautiful Mind", starring Russell Crowe as Nobel Laureate John F. Nash, Jr. (2001) that Nash was playing Go game with his friend.

  Some of my students told me, they played "the Blackout puzzle" from the official website of the movie. (http://www.cjent.co.kr/beutifulmind/ )

 

 <Fig 1> Blackout puzzle

 

  Some student asked me "Can we find an optimal solution for the game? and further  "Is there any possibility that we can not win the game if the given setting is fixed?"

 One of my student,  Jong Bin Park, told me  a purely linear algebraic approach on the Blackout puzzle.

 

    We made a Mathematical model of the game and gave a mathematical proof of it. And the model is fully based on the very Basic knowledge of Linear algebra.  I found it is beautiful because it opens  other area of  works as well such as  a technology and  a generalization.

   


I. Background of Blackout puzzle

 

(1) Introduction


Blackout  puzzle is a one-person strategy game and   the Blackout board is a grid of any size. Each square takes on one of  two colors. The player click any square one at a time.
The selected square and all squares that share an edge with it change colors.

 

<Fig 2> Blackout game

 

 The object of the game is to get all squares on the grid(tile) to be the same color (Black or White).


When you click on a tile (the highlighted tile icons) will change or "flip" from its current state to the opposite state.  Remember, the goal is to change all of the tile icons to black (or white).

<Fig 3> The end of the game

 Hence we gave the name "Blackout puzzle".

 

  The easiest way to learn how to play the game is to start a new game at a low level, maybe level 2 or 3, and click on the hint button.  You will be told which tile to click on.  Once you've played it a little you'll get the hang of it.

  

(3) How to Solve Any 3×3 Game

 

Optimal Solution Tree

 

The diagram below illustrates the shortest sequence of moves for resolving possible scenarios on a 3x3 board.

 

 

(4) Understanding the Diagram

 

Although there are 512 total board positions for a 3x3 Blackout grid, symmetry reduces that number to the 51=3+8+15+13+8+3+1 tactically unique layouts pictured above. In this diagram, the black dots indicate which square the player should choose. Arrows point to resulting board configurations. The numbers indicate the minimum number of moves required to solve any position on a given row.

 

  (We made our solution without knowing the above information. And our method only used basic LA to find the optimal solution.)

 

II. Main questions

  

  Q 1.   "Is there any possibility that we can not win the game if the given setting is fixed?"   

 

  Q 2.  "Can we find an optimal solution for the game always?

 

  Q 3.  "Can we make a program to give us an optimal solution?"

  

       We answer for all three!!

 

III Our Solution of the Blackout puzzle

 

  There are patterns of    blackout grid.

 

  Among these 512 patterns, there are   patterns that we can win the game with only One more click as following. (Twice of the following basic 9 patterns as we ex-change all colors.)

<Fig. 4> Basic 9 patterns (times 2)

 We tried to use the process that Saunders Mac Lane suggested in Bull of AMS(1994),

intuition(visualization) - trial - error - speculation - conjecture - proof (explanation)

(Uhl, Jerry & Davis, William, 1999).

 

 So, we checked several examples and had enough trial and error to convince to answer the first question with any given initial condition.

 

(Example) Assume the following initial condition

<Fig.  5>

 This setting is not one of the above = 18 patterns, but the following 3 clicks make it all white.

<Fig. 6>

 Our first step to find a winning strategy was to recognize these 18 patterns.

  

   Now we try to make a Mathematical Model from this game.

 

Only actions that we can take are only 9 clicks because we only have 9 stones on the board.

We assume "the white stone   1 and black stone 0". Then we can classify effects of each action as an addition of one vector (or 3x3 matrix), then any series of our actions are the linear combination of these. Now we use modular 2 arithmatic to make the Zero vector or all 1's vector (or matrix, resp.) to finish the game. (i.e. or ).

<Fig. 6>

 

 So we now have the following 9 vectors  as an effect on our action on each grid.

 

 

 

[Modelling example]   If we have 5 black(blue) stones and 4 white(red) stones in    board as below.

 

          

<Fig. 7>

 

Then the given matrix is and then we can click some of 9 positions to take action on it. And this can be represented by

 

=

 

So, our problem is  to find some . so   = (or ).

 

    anib11.gif  [  This is a Math problem : Find  such      mark4_6.gif

 

 

 

                 [Method ]

 

We can use either MATHEMATICA, MATLAB or JAVA tool  to solve.  (Recently we made JAVA tool shows answers in quotient form. )

http://matrix.skku.ac.kr/newMatrixCal/Test.html  

   ()

 

But we only need integer vector x, so

and

                 x '     mod 2.   ( or   )

    

      We only need 0 and 1    because cliking of one stone is same as clicking once, and cliking of one stone is same as doing nothing.  So

 x ' x'  (mod 2)

 

So,    our answer is     

 

What this shows is if we click (1, 1) (1, 3), (2, 1), (3, 2) position,  we will have all white stones on the board with only 4 clicks.

 

In the following Figure, the command "마법사(Wizard) 실행" tells us "1 3 4 8" that indicate  which 4 stones we have to click to win.

And "총 수행 횟수 4" shows we won with 4 clicks(MOVE).

 

             

<Fig. 8>

  <Our Program Down> Run die_whitebg.gif

 

And this always work.    Why this happens?  So our next question is ;

 (We can run the program  from  http://matrix.skku.ac.kr/sglee/blackout_win.exe )

 

  Q 2.  "Can we find an optimal solution for the game always?

 

 [ Proof ]  From the 9 matrices

,,,,,,,,.

 

make nine column vectors with the above, and make a symmetric matrix  (because of the symmetry in the board) whose columns are these vectors.

 Then we have a linear system of equations to find x.

      ( or   , where is a given (condition) matrix.

Then  and .  So there are linearly independent. And This system has a unique solution.

 

(Furthermore all this process can be done in Modular 2 arithmetic.)

 

  , where .

   Let

 

   Given                     (1,1)             (1,2)                (1,3)                 (2,1)              (2,2)         

 or

           (2,3)                 (3,1)                (3,2)               (3,3)             Goal 1         Goal 2

Is there ,

 or

Goal 1        Given          Goal 2         Given

is the Zero matrix of mod 2 for any ?

 

Answer: Yes!!

 

  Existence part :  

       

 Let

            Given                  (1,1)                 (1,2)               (1,3)              (2,1)               

≡    

            (2,2)               (2,3)                   (3,1)                (3,2)              (3,3)

 

 

         [Recall   :    Ax =  -B  is consistence     iff    ]

 Let    0 ,   j

 

Case 1.  If is a zero matrix, it is done because those (mod 2) make a solution.

 

Case 2. If is not a zero matrix, then it is clear that

               and

 

In any cases, the LSE      ( or    is consistent.  

 

  So, for given  , x, 0, j, and b,

,

x,

0,

j ,

and the vector b  came from the given (0,1)-matrix .  

 

Ax  +  b  =    0     (or   j ) has a solution.

 

 And x is obtained as             x  =   0 -   b  (or x   =   j  -   b )   

where               

 

Let   x'   x  (mod 2)

Then x' be a real optimal winning strategy vector(matrix) which can be deduced from x.        square36_gray.gif  

 

Now each entries of x' are all  0 or 1 as is in real game situation and we can always find a (0,1) matrix as  a real optimal winning strategy vector(matrix).

 

With this idea, one of my student made a computer program on this algorithm with C++ as following

 

 

  

which tell us an optimal strategy to win.  This software also verified our conjecture, and showed the proof was valid.

 As a generalization, we can use the same algorithm to make a Program that gives an optimal winning strategy for real Go board of size .

 

We can download and use from http://matrix.skku.ac.kr/sglee/blackout_win.exe .

  <Our Program Down> Run die_whitebg.gif

 

 

III Conclusion

  

    This kinds of practical approach to a real world problem of gifted students and leading teacher gave a stimulating mathematical creativity for both.

 

   From this process, I found the importance of helping gifted students, so their ideas can be made as a nice and concrete scientific work.

 

 

References

REFERENCES

[1]         Park, H.-S., Go Game With Heuristic Function , Kyongpook Nat. Univ. Elec. Tech Jour. V15, No.2 pp. 35-43, 1994

[2]         Park, J.-B. (2003), Software http://matrix.skku.ac.kr/MT-04/blackout_win.exe 

[3]         Uhl, J.  & Davis, W., Is the mathematics we do the mathematics we teach?, Contemporary issues in mathematics education, Volume  36, pp. 67-74, Berkeley: MSRI Publications,1999

[4]         JAVA program by CJ entertainment Inc., Movie: The Beautiful Mind, Blackout puzzle (2002),  http://www.cjent.co.kr/beautifulmind/

 

 

 

                             Thank   you!

 

 

 

 

 christmas.gif