Black and White
What is the game about?
This game involves generating different patterns on a
square board by pressing some squares on it. When one
presses a square, the colours of some squares will be
changed according to the rules or operations described
below. The goal is to produce certain assigned patterns.
How to play this game?
There is a board with n x n squares on it. All the squares
are either white or black in colour. At the beginning,
all of them are white.
After pressing a square, the squares with sides adjacent
to it, including itself, will be changed to another colour.
In this game, you are required to produce on a computer,
by pressing a number of times of these squares, a particular
pattern on the square board.
Can one produce all the possible patterns?
The answer depends on the operations we defined for
the game. To see why, let's represent the square
board as an n x n matrix, with entries '0' and '1'
representing the white and black squares respectively.
Any operation of changing the colour of a square and
its adjacent squares can also be represented by an n x n
matirx, which is called an operation matrix. The entries
of this matrix are '1' if the corresponding squares are
going to be changed, and '0' otherwise.
Now applying an operation is the same as adding the
corresponding operation matrix to the original matrix
and we use the binary addition here.
The question now becomes whether any matrix can be
represented by a linear combination of the operation
matrices. If this can be done, then we can press the
corresponding squares to obtain any particular pattern
we want. To answer this question, it suffices to know
whether the operation matrices generate all the n x n
elementary matrices, which form a basis for the vector
space of all n x n matrices.
One can show that the operation matrices can generate
all the elementary matrices by trial and error or by
solving systems of linear equations. Solving systems
of linear equations manually can be a tedious job.
However, with the help of some computer software, it
becomes a rather easy task.
Other variations for this game
The game shown here is quite simple, as it only involves
two colours. To increase the difficulty of this game,
more different colours can be used and other rules upon
pressing the squares can be set. In such cases, the
operations matrices will be different and solving the
problems will be more complicated. However, the underlying
principle will still be the same.
| 
