The 10^{th} International Congress on Mathematical Education, July 4-11, 2004, Copenhagen, Denmark
TSG4: Activities and Programs for Gifted Students
ACTIVITY OF A GIFTED STUDENT WHO FOUND LINEAR ALGEBRAIC SOLUTION OF BLACKOUT PUZZLE
Sang-Gu Lee (Sungkyunkwan Univ. KOREA) |
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 ).
[ This is a Math problem : Find such ]
(1,1) (1,2) (1,3) (2,1) (2,2) (2,3)
, that is,
(3,1) (3,2) (3,3) Initial Goal
(1,1) (1,2) (1,3) (2,1) (2,2) (2,3)
(or )
(3,1) (3,2) (3,3) Goal Initial
[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
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.
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
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
[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,
[4]
JAVA
program by CJ entertainment Inc.,
Movie: The Beautiful Mind, Blackout puzzle (2002), http://www.cjent.co.kr/beautifulmind/
Thank you!