# Nine squares puzzle : is it possible to move from any configuration to a winning one?

I'm a person who is preparing graduated school in Korea. My English may be not enough.
This site is my only hope.

I'm trying to solve this question.(with MATLAB)
But, I couldn't figure out the second question (b).
The question is like this.
(Question from "Linear Algebra - A modern introduction" by David Poole 2nd Edition, 2.4 - Question Number 29)

==========(Question)=========== Fig. 1 Fig. 2

The array is composed of $$3 \times 3$$ squares that can be either white or black.
When I choose a square, the status of this square and some adjacent squares are affected.
To explain more specificaly, see the second figure.
When a square is selected (signaled by a circle), the status of neighboring squares with "*" is changed. (black -> white or white -> black)

The objective of this puzzle is to make every square black.

(a) If initial status is like figure 1, show that this game is won, and explain the process.

(b) No matter what the initial status, show that the game is always won.

==========(Question)===========
To solve this question, I made a $$9 \times 9$$ matrix explaining how squares change their status.
For example, if I choose square #1, then #1,#2,#4,#5 will change their status. I render this under the form of a vector.
[1 1 0 1 1 0 0 0 0]
Number 1 means : status is changed and 0 means status is kept.
If instead of square #1, I choose another square, I'll get another vector. I gather these vectors into a $$9 \times 9$$ matrix.
I'll call this matrix "Action Matrix".

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 1 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 1 1 0
0 0 0 0 0 0 1 1 1
0 0 0 0 1 1 0 1 1

And I made another matrix which represents status of square, and this is a $$1 \times 9$$ matrix. If square is black, I express with number 1, if square is white, I use number 0.
(For example, the status of figure 1 is expressed like this [1 0 0 0 1 0 0 0 1])
I'll call this matrix "Status Matrix".

For question (a), In order to make every square black, I considered the squares that need to be changed, and I made a new Status Matrix like below.
[0 1 1 1 0 1 1 1 0]
After transposing this matrix, combine Action matrix and Status matrix to make a new augmented matrix. After that, I just solve this augmented matrix using MATLAB.
Then MATLAB gives me the answer like below.

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

So, if I choose square #3, #7, I can win.
I think that I have solved this question.
But the problem is (b).

If I can show that every single square is changed by some actions, I think that I prove this question.

But the result is different from my expectation.
I made Status matrices which express change of only one square about each 9 squares.

Then MATLAB gave me answers with rational number and negative.
I think that this result means "impossible change".
Because we can't choose 0.4 times or -0.6 times.
But, the question implies me this puzzle always be won.

Am I wrong ? or is the book wrong?

Actually, it is hard for me to ask question in English.
But I want to know answer.
I think that many geniuses here can help me.

Thank you for reading this word.
Have a nice day~

• I have included your figures into the text of your question. – Jean Marie Dec 6 '18 at 21:52
• Thank you so much. This question is my first question here. I wasn't good enough. I'll be more careful from now on. – Y H Kang Dec 7 '18 at 13:35
• I have taken the liberty to modify your title and some parts of your text, trying to improve its style. In this way, this very interesting question is more readable, and thus reaches more readers. I wish you see it positively. – Jean Marie Jan 31 '19 at 9:14
• I have also enriched the "tag list" : I have added "puzzle" and "matlab" – Jean Marie Jan 31 '19 at 9:20

A first remark is that it is a variant of "Lights Out" Puzzle https://gaming.stackexchange.com/q/11123 http://perfectweb.org/ddo/solver/vale_puzzle.html

The $$3 \times 3$$ board can be in $$2^9=512$$ possible "status" (plural of "status" looks to be ... "status"), each status being encoded by a $$9$$ bits column vector (with your convention $$0\to$$"white" and $$1\to$$"black").

The mathematical framework for studying this game is vector space $$\mathbb{F}^9$$ over finite field $$\mathbb{F}=\{0,1\}$$ ; its additive operation $$\oplus$$ that is called "xor" (exclusive or), alias "adding mod $$2$$" accounts for toggling operation ($$0 \leftrightarrow 1$$).

More precisely, "toggling" operation can be described as "adding $$1$$", i.e., by using implicitly transformation $$x \to x \oplus 1$$ which changes $$0 \to 1$$ and $$1 \to 0$$ .

In this way, a move from status $$s_1$$ to another $$s_2$$ under a certain action (for example the first one) "a" fits into this framework :

$$s_1+a=s_2 \ \ \iff \ \ \begin{pmatrix}1\\0\\0\\1\\0\\0\\0\\0\\0\end{pmatrix}\oplus \begin{pmatrix}1\\1\\1\\0\\0\\0\\0\\0\\0\end{pmatrix}= \begin{pmatrix}0\\1\\1\\1\\0\\0\\0\\0\\0\end{pmatrix}$$

The matrix of "actions" will then be presented columnwise (instead of linewise as you did) as the gathering of actions $$a_1,a_2,\cdots a_9$$ under the form of a matrix :

$$A=\begin{pmatrix} 1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 1&0&1&0&1&0&1&0&1\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1 \end{pmatrix}.$$

The following solution is based on a double interpretation of the product $$AV$$ of matrix $$A$$ and any vector $$V$$ with $$9$$ coordinates $$0/1$$.

Proposition 1 : $$A_1,A_2,...A_9$$ constitute a basis of $$\mathbb{F}^9$$.

Proof : $$\det(A)=1$$ (technically, using for example Matlab, we have to do it in two steps $$\det(A)=5$$, then mod$$(\det(A),2)=1$$). This determinant is not $$0$$, thus all actions are linearly independent ; as there are $$9$$ actions and the dimension of vector space $$\mathbb{F}^9$$ is $$9$$, they constitute a basis. $$\square$$

Thus, in particular, any "position" vector can be expressed as a linear combination of $$A_1, A_2, ... A_9$$, moreover in a unique manner.

These linear combinations have an interpretation as successive actions ; for example, combining actions $$A_1$$ and $$A_4$$ is the same as the linear combination :

$$1A_1+0A_2+0A_3+1A_4+0A_5+0A_6+0A_7+0A_8+0A_9$$

(intuitive interpretation : coefficient 1 = I take, coefficient 0 = I don't take). But the expression above can be rendered as the application of matrix $$A$$ to the column vector $$V$$ with components $$1,0,0,1,0,0,0,0,0$$ as shown below :

$$AV=\begin{pmatrix} 1&1&0&1&0&0&0&0&0\\ 1&1&1&0&1&0&0&0&0\\ 0&1&1&0&0&1&0&0&0\\ 1&0&0&1&1&0&1&0&0\\ 1&0&1&0&1&0&1&0&1\\ 0&0&1&0&1&1&0&0&1\\ 0&0&0&1&0&0&1&1&0\\ 0&0&0&0&1&0&1&1&1\\ 0&0&0&0&0&1&0&1&1 \end{pmatrix}\begin{pmatrix} 1\\ 0\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}.$$

What we have done for this particular case can be extended to any $$V$$ with coordinates $$v_1, v_2, ... v_9 \in \mathbb{F}^9$$, otherwise said with all possible linear combinations :

$$v_1a_1+v_2a_2+...+v_9a_9 \ \ \text{where} \ \ v_i=0,1 \tag{1}$$

In this way, we can generate $$2^9$$ such linear combinations (no one is the same due to the unicity of decomposition onto a basis) ; we can represent all the possibilities by a binary tree with $$2^9$$ "leaves" as shown on figure 1. Fig. 1 : A way to consider $$\mathbb{F}^9$$ as a tree with $$2^9$$ (very agglomerate !) leaves, the traversal of this tree from left to right to a given leaf giving the decomposition of the leaf into the sum (= linear combination) of certain $$A_k$$s.

In this way, we cover the totality of vector space $$\mathbb{F}^9$$. We have thus proven the following proposition :

Proposition 2 : Each "status" of the $$3 \times 3$$ board can be written $$S=AV$$ for a certain (unique) $$V$$.

Proposition 3 : Being given two status represented by $$AV_1$$ and $$AV_2$$, one can always find a sequence of actions that change $$AV_1$$ into $$AV_2$$. Moreover this sequence is given by the "ones" coefficients in $$V_2-V_1$$. We have thus a winning strategy !

Proof : We are looking for a column vector $$W$$ such that $$AV_1+W=AV_2$$ ; i.e., we want to express

$$W=AV_2-AV_1 = A(V_1-V_2) \tag{2}$$

as a linear combination of $$V_1,V_2,...V_9$$ ; we know that this combination exists because $$V_1,V_2,...V_9$$ is a basis ; but looking at the last expression in (2), it is served on a tray taking Prop. 2 into account : in fact entries "$$1$$ "in $$V_2-V_1$$ indicate which "actions" are to be used... $$\square$$

Remark : Being given a status vector $$S$$, how can it be written under the form $$S=AV$$ ? Simply take $$V=BS$$ with $$B$$ being the inverse of matrix $$A$$.

Here is a very simple Matlab program implementing this method :

% The inverse of A (mod 2)(see Remark 3 above) :
B=[...
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];
% An example :
S1=[1 0 1 0 1 0 1 0 1]';
S2=[0 0 0 0 1 0 0 0 0]';
% meaning :
1 0 1            0 0 0
% S1 = 0 1 0  and  S2 = 0 1 0
1 0 1            0 0 0
mod(B*S2-B*S1,2)'
% answer : 1 0 1 0 0 0 1 0 1 ; looking at the positions of the "ones", the sequence
% of actions that transform S1 into S2 are : a1, a3, a7 and a9.


Other remarks :

1) The order of actions doesn't matter due to the commutativity of sum $$\oplus$$.

2) We have obtained a stronger result than the fact that status "$$111111111$$" can be reached : all status can be reached.

3) The inverse $$B=A^{-1}$$ (see program) has been obtained with the following composite instruction using the so-called "adjugate" matrix :

B =  mod(round(det(A)*inv(A)),2)


To be read in a second step : A very different method :

We have been lucky here that the vector space of configurations being $$9$$-dimensional, there are precisely $$9$$ rules (the same figure) with the further property that they are linearly independent and, moreover, that the toggling rule $$0 \leftrightarrow 1$$ is rendered by the "xor" operator.

If such had not been the case, I would have proposed you to switch to another data representation, i.e., an oriented graph with :

• $$2^9=512$$ vertices, each vertex corresponding to a possible "status" of your $$3 \times 3$$ board.

• two vertices $$(V_1,V_2)$$ being connected by an edge whenever $$V_2$$ results from $$V_1$$ by applying some of the given rules.

Now, the initial issue is converted into this one : show that the special vertex "$$111111111$$" ("all squares black", binary notation is very handy here) can be reached from any other vertex (or, in an equivalent way, reversing all orientations, can one proceed from vertex "$$111111111$$" to any other one).

• Thank you for your answer. Unfortunately, I'm not familiar with Graph Theory. Actually, it is first time to hear "Oriented graph"(In this context, is it same as "Directed graph"?). So, I've searched about it. It looks very nice and useful. But, I think I need more time to understand your suggestion. If you explain a little more, it would be very helpful. – Y H Kang Dec 7 '18 at 17:15
• I'm really impressed by your enthusiasm. But, I'm so sorry I was lazy. Actually, I was busy this weekend. Anyway, Now I'm studying your answer. And I want to use more time about this. I'll answer your question soon! – Y H Kang Dec 9 '18 at 11:31
• Your explanation is so detail and kind. Thank you very much. First of all, I saw your Matlab program works very well. (I learned "adjugate matrix" from you.) But I'm still not sure a point. I understand the process of obtaining matlab code. Before, I don't understand that how can be proven that every status is solvable. In order to check my understanding, I try to summarize your idea about proof. A_i (i = 1,2,3...,9) are linearly independent. So, they can make 2^9 actions, and they can be basis of F^9. – Y H Kang Dec 10 '18 at 5:17
• It means that every status can be reached using A_i. (because 2^9 is everything in F^9.) So, if each possible actions are linearly independant and can make basis of F^9, they can make all status. And if I want to know whether the problem is solvable using given actions, is it enough to check determinent of A(a matrix that includes every action vector)? ※ I'm worried that I might have missed something very clear and easy because of my English ability. If so, please understand. – Y H Kang Dec 10 '18 at 5:18
• Thank you so much. You are perfect! – Y H Kang Dec 14 '18 at 3:49

I am not 100% sure that I know what you did and that I'm interpreting things correctly, so if I am wrong, I apologize. I will state what I think is going on, and then what the correct answer is.

The rows of you "action matrix" are the squares that get toggled with different possible moves. To show that you can get to any state (from an initial state of all white, for example), you want to show that given state is a sum of those row vectors. But this isn't entirely correct, because if you do a move twice you end up with 2's and 0's and we need to interpret the 2's as having done nothing. What this means is that you don't want to do linear algebra over the rational numbers, but instead you want to do linear algebra over the field with 2 elements.

Your goal is to show that the action matrix is invertible, but being invertible over the rational numbers is not the same as being invertible over $$\mathbb Z_2$$. The same general ideas work in both cases. So, for example, you could row reduce your matrix, but after every step you reduce things mod 2 (so that even numbers become 0 and odd numbers become 1) and try to get to the identity matrix. Or you could take the determinant and reduce that mod 2. I don't know how to do the first thing in MATLAB, but the second thing just requires using the built in determinant function and seeing if the result is even or odd.

• Thank you very much. I think you pinpointed my mistake. And I did your second thing, and I confirmed that it works well. But, I also don't know about your first thing. I'm trying to find how to do row reduction with only 0,1. Thank you for your correct answer. – Y H Kang Dec 10 '18 at 5:49
• You're welcome. I found code for doing row reduction mod 2 in matlab. I have not tried it, but you may want to play with it: gist.github.com/esromneb/652fed46ae328b17e104 – Aaron Dec 10 '18 at 10:35
• Oh! That's nice. Thank you for your help. You seem that you know what I need to. – Y H Kang Dec 14 '18 at 3:51

You are off to a good start, but then seem to get lost. My first idea is the same as yours:

The state space of the board can be represented by $$\Bbb{F}_2^9$$, i.e. vectors of length $$9$$ with all entries equal to $$0$$ or $$1$$. The state of the $$k$$-th square is represented by the $$k$$-th coordinate being $$0$$ or $$1$$. You are given $$9$$ moves that switch the states of certain squares, which corresponds to adding a vector to the current state vector. These are precisely the rows of your action matrix.

This means that we have $$9$$ different vectors that we can keep adding to the initial state. The objective is to show that we can reach the state $$0\in\Bbb{F}_2$$. This is equivalent to showing that the initial state is in the span of the $$9$$ action vectors. So to show that every state is solvable, it suffices to show that the action vectors span the whole space $$\Bbb{F}_2^9$$.

This is not hard to do by hand; it can be done by Gaussian elimination of your $$9\times9$$ action matrix, keeping in mind that the coefficients are from the field $$\Bbb{F}_2$$, meaning that $$1+1=0$$.

A more ad hoc approach for those who don't know linear algebra:

• Switching $$2$$, $$4$$, $$5$$, $$6$$ and $$8$$ amounts to only switching $$5$$.
• Switching $$1$$, $$2$$, $$6$$, $$7$$, $$9$$ and only $$5$$ amounts to only switching $$7$$.
• By symmetry, we can switch only $$1$$, only $$3$$ and only $$9$$.
• Switching $$2$$, only $$1$$ and only $$3$$ amounts to only switching $$2$$.
• By symmetry, we can switch only $$4$$, only $$6$$ and only $$8$$.

This shows that we can switch every square separately, and hence reach every state.

• Thank you so much. I made a stupid mistake. I totally forgot that the elements of state matrix can be 0 and 1 only. This question has a "CAS" mark, so I tried to use MATLAB. I think I fell into a trap Because of using Matlab. Anyway, Really Thank you. – Y H Kang Dec 7 '18 at 17:26
• Interesting solution. – Jean Marie Dec 8 '18 at 6:04

When you turn field 3 (then 2,3,6 will turn black and 5 will turn white) and then turn field 7 (then 4,7,8 will turn black and 5 will toggle back to black) then all fields are black.

It is easy to see that each operation which we could apply is invertable and self-inverseand all are commutative. Furthermore the operations are symmetric wich respect to the diagonals. So it made sense to start with the operation which flips most of the white fields above the diagonal, and does not touch any field below the diagonal. There was nothing to care about changes on the diagonal (field 5) since the respective operation below the diagonal will flip them back.

• I am sorry but what do you finally prove ? – Jean Marie Dec 8 '18 at 6:06
• I'm sorry but I couldn't get your point. By the way, how about in case only field 5 is white? – Y H Kang Dec 10 '18 at 6:05