Tip:
Highlight text to annotate it
X
In a previous video
we saw how we could set up a system of linear equations
that will solve Lights Out.
And for the 3-by-3 version,
the system in matrix form will look like this.
Recall that each column represents
the action of pressing the corresponding square.
So if you look at column 1,
it corresponds to pressing square 1, which is the top left square.
And the squares that are affected are square 1, square 2, and square 4.
Those entries have the value 1 in the column.
So we are trying to solve this system
where the right-hand side b values correspond to the configuration of lights.
In this case, squares 2, 4, 5, 7, and 8 have their lights on, so
b_2, b_4, b_5, b_7, b_8 will have value 1
and the rest will be 0.
So we're going to solve this system using row reduction.
And we'll solve it for the general values b_1 up to b_9.
So I'm not going to fix them to a particular set of values.
So what that means is, at the end, I'll have solved 3-by-3 version of Lights Out
for all possible configuration of values.
And you might find that after watching this video,
all the fun of playing this game would have been taken away.
So let me go ahead.
And I'm going to form the augmented matrix.
And I've left some extra space on the right most column because
this column is going to get big.
Let me move this Lights Out out of the way.
And, what we're going to do is add row 1
to row 2.
So row 2 is replaced with row 2 plus row 1.
And remember that this system is over GF(2). So 1 + 1 is 0.
So if I add row 1 to row 2, I'll get
0 here, 0 here,
1 here, and
b_1 + b_2 over here.
The next operation that I'm going to perform
is to replace row 1 with row 1 plus row 4.
That will give me
0 here
and 0 here
a 1 here
and a 1 here.
And this will be b_1 + b_4.
Now the next...
the next operations that we're going to perform are the following:
i'm going to replace row 3 with row 3 plus row 1.
And replace row 5 with row 5 plus row 1.
Ok. So I'm adding row 1 to row 3 and row 5 as well.
So if I add it to row 3, this will become 0
this will become 1
and that will become 1.
And over here, I'll have b_1 + b_3 + b_4.
And if I add row 1 to row 5,
this will be zero0
and this here will be 0
this will be 1
and this will be now b_1 + b_4 + b_5.
Now, the next operations that we're going to perform are
replacing row 2 with row 2 plus row 3
and replace row 6 with row 6 plus row 3.
So I'm adding row 3 to row 2 and row 6.
And adding row 3 to row 2
will give me 0 here
0 here, a 1 here
and a 1 here.
Now I have to add the right-hand sides.
So b_1 + b_1 becomes 0.
So I'm left with b_2 + b_3 + b_4.
And now adding row 3 to row 6... so row 6 is down here...
I get
0 here
0 here
0 here
and 1 here.
And I get b_1 + b_3 + b_4 + b_6 on the right-hand side.
The next operations that we're going to do is i'm going to take row 7
and add it to row 2, 4 and 5.
So that will clear the 1's up here
and adding row 7 to row 2, I have
0 here
0 here
and 1 here.
And this will just add b_7 to the right-hand side.
Now adding row 7 to row 4, I have a 0 here
a 0 here and a 1 here
and that will add b_7
to the right-hand side.
And finally
adding row 7 to row 5, I get a zero here,
a 0 here, and a 0 here, and
we'll have to add b_7 to the right-hand side.
Now one nice thing about
row 5 is it already tells you that x_6
has to be equal to b_1 + b_4 + b_5 + b_7.
So we have successfully isolated one variable.
And let's continue.
So the next operations that we're going to perform are
replacing row 1 with row 1 plus row 8
row 3 with row 3 plus row 8
and row 4 with row 4 plus row 8.
So if we do, we will clear out all the 1's here.
So row 8 added to row 1 will give me a 0 here
and a 0 here
a 1 and a 1 here.
And I'll have to add b_8 to the right-hand side.
Now if i add row 8 to row 3, I'll get a 0 here
I get a 0 here, and 1 get a 1 and a 1 here.
And I have to add b_8 to the right-hand side.
And finally, adding row 8 to row 4 will give me 0 here.
a 1 here, a 0 here,
and a 1 here. And
b_8 is added to the right-hand side.
Let's move on to the next column.
And this time, I'm going to
use row 5
and add it to rows 2, 3, and 9.
So row 2 to is replaced by row 2 plus row 5
row 3 is replaced with row 3 plus row 5
and row 9 is replaced with row 9 plus row 5.
So adding row 5 to row 2, I get a 0 here
and everything else stays the same.
Now row 5 add that to row 2
will have a b_1, a b_2, a b_3, now b_4 goes away
and b_5,
and b_7 goes away.
So I'll have b_1 + b_2 + b_3 + b_5.
And that will be my right-hand side.
Now adding row 5 to row 3,
we get 0 here and everything else stays the same.
Now b_1 and b_4 go away.
And so we're left with
b_3 + b_5 + b_7 + b_8
And now, adding row 5 to row 9,
I get a zero here, everything else stays the same.
And I'm going to have b_1 + b_4 + b_5 + b_7 + b_9
on the right-hand side.
Now, we are going to add row 6
to rows 4, 7 and 8.
So row 6 added to row 4 will give me zero and zero up here
and I'll have a b_1, a b_3, b_4 will be gone
but b_6, b_7, and b_8 will appear on the right-hand side as well.
So b_1 + b_3 + b_6 + b_7 + b_8.
And now adding row 6 to row 7
I get 0 here and
a 1 here
and that will give me
b_1 + b_3 + b_4 + b_6 + b_7 on the right-hand side.
And now, adding row 6 to row 8, I get a 0 here
and a 0 here,
and the right-hand side will have b_1 + b_3 + b_4 + b_6 + b_8.
Now, we are going to add row 9 to row 1
to row 3
and to row 7. So
adding row 9 to row 1 will give me 0's up here
and now b_1, b_4 will go away
so what's left is b_5, b_7, b_8, and b_9.
Adding row 9 to row 3 will give me 0's here.
Sp what we'll have is b_1 + b_3 + b_4 + b_8 + b_9.
And adding row 9 to row 7
these will turn to 0's.
b_1 and b_4 and b_7 will go away.
So I'll have b_3 + b_5 + b_6 + b_9.
Now I'm going to add
row 2 to row 8
and row 2 to row 9
and that will clear out the 1's here.
So adding row 2 to row 8 will give me a 0 here
and b_1 and b_3 will be gone
so I will have b_2 + b_4 + b_5 + b _6 + b_8.
And adding row 2 to row 9
will give me a 0 here
and b_1 will be gone, b_2 b_3 will be here
and b_5 will be gone as well.
So that will give me b_2 + b_3 + b_4 + b_7 + b_9.
And finally, I'm going to add
row 9 to row 6.
So doing that will give me a zero here. And
b_3 and b_4 will go away. So I'll have b_1 + b_2 + b_6 + b_7 + b_9
on the right-hand side.
Now if you look at this matrix
every column has exactly one 1
and the rest of the entries are 0.
And the same goes for every row.
From this, we can actually write down the solution.
So x_1 will have to be given by
b_1 + b_ 3 + b_6 + b_7 + b_8.
x_2 will have to be given by b_5 + b_7 + b_8 + b_9
and x_3 will be given by b_1 + b_3 + b_4 + b_8 + b_9
and so on.
So we can actually read out the solution for x_1 up to x_9.
And let's do that.
Let's write out x_1 up to x_9 in terms of these b's.
And i'll have to make this a little smaller.
So x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 x_9
will be equal to...
so x_1 will be b_1 + b_3 + b_6 + b_7 + b_8.
x_2 will be b_5 + b_7 + b_8 + b_9.
x_3 is b_1 + b_3 + b_4 + b_8 + b_9
x_4 is b_3 + b_5 + b_6 + b_9
x_5 is b_2 + b_4 + b_5 + b_6 + b_8
and x_6 is b_1 + b_4 + b_5 + b_7
x_7 is b_1 + b_2 + b_6 + b_7 + b_9
and x_8 is b_1 + b_2 + b_3 + b_5.
Finally, x_9 is b_2 + b_3 + b_4 + b_7 + b_9.
So that's the solution in terms of the b's. Now let's bring back this
configuration of lights here.
In this configuration,
b_2 = b_4 = b_5 = b_7 = b_8 = 1
the rest are zeros. So we'll just have to plug it in and see what the solution is.
Ok. So if you look at the solution, I have to press
square 2, square 4, square 6, and square 9.
So square 2
square 4,
square 6,
and square 9.
And as you see, I have solved the puzzle.
So there you go.
I have solved 3-by-3 Lights Out completely.
No matter what configuration of lights you give me
I can tell you using this solution here
which squares you need to press in order to solve the puzzle.
Now i encourage you to try this with a 4-by-4 board
and you'll notice something rather interesting if you go through all the work.
Clearly you have to do more work
but it's not impossible.
And after a couple hours, you'll have a solution and you'll have totally demystified
the game.
Good luck.