This is an ipython (jupyter) worksheet with code from the lecture notes for the course Permutation Puzzles: A Mathematical Perspective, by Jamie Mulholland
Coures webpage: http://www.sfu.ca/~jtmulhol/math302
Course notes booklet: http://www.sfu.ca/~jtmulhol/math302/notes/302notes.pdf
Here is an example of using SageMath to solve the linear system: $$ \begin{bmatrix} 1 & 0 & 2\\ 3 & 2 & 5 \end{bmatrix} \boldsymbol{x} = \left[\begin{array}{c} 3\\ 0 \\ \end{array} \right] $$
M=matrix(QQ,[[1,0,2],[3,2,5]])
b=vector(QQ,[3,0])
M.solve_right(b)
(3, -9/2, 0)
# Definition of the matrix for Lights Out
# input = integer n (where lights out board is nxn)
# output = lights out matrix A which is nxn
def lights_out(n):
A = identity_matrix(GF(2),n*n) # initialize A with ones along diagonal
for i in range(n):
for j in range(n):
m = n*i+j
if i > 0 : A[(m,m-n)] = 1 # I block below diagonal
if i < n-1 : A[(m,m+n)] = 1 # I block above diagonal
if j > 0 : A[(m,m-1)] = 1 # C block below diagonal
if j < n-1 : A[(m,m+1)] = 1 # C block above diagonal
return A
lights_out(3)
[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] [0 1 0 1 1 1 0 1 0] [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]
The lights out matrix for a 5x5 boaard would be a 25x25 matrix. SageMath won't print this out by default.
lights_out(5)
25 x 25 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
#current game configuration (i.e. buttons that are lit)
b=vector(GF(2),[1,1,0,0,1, 1,1,1,0,0, 1,0,0,0,1, 0,0,1,1,1, 1,0,0,1,1]);
print "starting configuration: "
print matrix(GF(2),5,5,b.list())
#solving the game
x=lights_out(5).solve_right(b);
#now put the solution x in a nice matrix form so we can see what buttons to press
button_press_matrix = matrix(GF(2),5,5,x.list()) # convert vector to a list then a matrix
print "solution: "
button_press_matrix
starting configuration: [1 1 0 0 1] [1 1 1 0 0] [1 0 0 0 1] [0 0 1 1 1] [1 0 0 1 1] solution:
[0 0 1 0 0] [1 0 1 1 1] [0 1 0 1 0] [1 1 1 0 1] [0 0 1 0 0]
# Definition of the solution function for Lights Out
# input = integer n (where lights out baord is nxn), and b is the configuration vector
# output = a matrix x indicating which buttons to press for a solution
def lights_out_solver(n,b):
x=lights_out(n).solve_right(b);
button_press_matrix = matrix(GF(2),n,n,x.list())
return button_press_matrix
b=vector(GF(2), [1,1,0,0,1, 1,1,1,0,0, 1,0,0,0,1, 0,0,1,1,1, 1,0,0,1,1])
lights_out_solver(5,b)
[0 0 1 0 0] [1 0 1 1 1] [0 1 0 1 0] [1 1 1 0 1] [0 0 1 0 0]
A lit button configuration $\boldsymbol{b}$ is solvable if the corresponding linear system $A\boldsymbol{x}= \boldsymbol{b}$ has a solution. From linear algebra we know
$$A\boldsymbol{x}= \boldsymbol{b} \text{ is solvable for every } \boldsymbol{b} \quad \iff \quad \text{$A$ is invertible} \quad \iff \quad \det(A)\ne 0.$$The lights out matrix (for $5\times 5$ game) has determinant $0$. Therefore, there do exist unsolvable configurations $\boldsymbol{b}$.
lights_out(5).determinant()
0
Example of an unsolvable configuration and how SageMath will let you know with a traceback error.
b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])
lights_out_solver(5,b)
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-19-491bae57dc08> in <module>() 1 b=vector(GF(Integer(2)),[Integer(1),Integer(0),Integer(1),Integer(0),Integer(1), Integer(0),Integer(0),Integer(0),Integer(0),Integer(0), Integer(0),Integer(0),Integer(0),Integer(0),Integer(0), Integer(0),Integer(0),Integer(0),Integer(0),Integer(0), Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)]) ----> 2 lights_out_solver(Integer(5),b) <ipython-input-15-2e660d04caea> in lights_out_solver(n, b) 3 # output = a matrix x indicating which buttons to press for a solution 4 def lights_out_solver(n,b): ----> 5 x=lights_out(n).solve_right(b); 6 button_press_matrix = matrix(GF(Integer(2)),n,n,x.list()) 7 return button_press_matrix /opt/sage/src/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.solve_right (/opt/sage/src/build/cythonized/sage/matrix/matrix2.c:7149)() 401 402 if self.rank() != self.nrows(): --> 403 X = self._solve_right_general(C, check=check) 404 else: 405 X = self._solve_right_nonsingular_square(C, check_rank=False) /opt/sage/src/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix._solve_right_general (/opt/sage/src/build/cythonized/sage/matrix/matrix2.c:8296)() 519 # Have to check that we actually solved the equation. 520 if self*X != B: --> 521 raise ValueError("matrix equation has no solutions") 522 return X 523 ValueError: matrix equation has no solutions
Could use try and except for error proofing.
b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])
try:
lights_out_solver(5,b)
except:
print "Current state has no solution."
Current state has no solution.
The set of solvable configurations is the column space of the lights out matrix $A$, $\text{col}(A)=\text{span}(\boldsymbol{t}_{1,1}, \boldsymbol{t}_{1,2},\ldots,\boldsymbol{t}_{5,5})$, and the dimension of $\text{col}(A)$ is called the rank of $A$, denoted $\text{rank}(A)$.
lights_out(5).rank()
23
Therefore only $23$ buttons are required to solve any configuration, and if each one can either be pressed or not, then there are $2^{23}$ solvable configurations, out of a possible $2^{25}$ configurations. Therefore the probability that a random configuration is solvable is 1/4.
There exist sequences of button presses that will leave the lights unchanged. These are known as quiet patterns. Such a sequence x is a solution to the homogeneous equation $A\boldsymbol{x}= \boldsymbol{0}$. That is, x is in the null space of $A$, denoted by $\text{nul}(A)$. Since $A$ has rank 23 then it has nullity 2 and so $\text{nul}(A)$ contains 4 vectors:
\begin{align*} \text{nul}(A)& = \text{span}(\boldsymbol{d}_1,\boldsymbol{d}_2) = \{ r_1\boldsymbol{d}_1+r_2\boldsymbol{d}_2 \ |\ r_1, r_2 \in \mathbb{F}_2\}\\ &=\{ \boldsymbol{0}, \boldsymbol{d}_1, \boldsymbol{d}_2, \boldsymbol{d}_1+ \boldsymbol{d}_2 \}. \end{align*}lights_out(5).right_kernel()
Vector space of degree 25 and dimension 2 over Finite Field of size 2 Basis matrix: [1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1] [0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0]
If $\boldsymbol{s_1}$ and $\boldsymbol{s_2}$ are both solutions of a configuration $\boldsymbol{b}$ then $A\boldsymbol{s_1}=A\boldsymbol{s_2}=b$ so $\boldsymbol{s_1}-\boldsymbol{s_2}$ is in the null space of A.
Therefore, all solutions for $\boldsymbol{b}$ are $\boldsymbol{s_1}+\text{nul}(A)$:
$$\{ \boldsymbol{s_1}, \boldsymbol{s_1}+\boldsymbol{d}_1, \boldsymbol{s_1}+\boldsymbol{d}_2, \boldsymbol{s_1}+\boldsymbol{d}_1+ \boldsymbol{d}_2 \}$$First we define a function which counts the number of 1's in a vector.
# Function: number_of_presses
# input = a vector x of dimension 25 with 0,1 entries
# output = the number of times 1 appears as an entry
def number_of_presses(x):
counter=0; # initialize counter, which is our variable to count 1's
for i in range(0,25): # recall python indexes lists from 0, not 1
if x[i]==1: counter=counter+1 # check if the ith entry is 1, increment counter
return counter
b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])
number_of_presses(b)
3
Could also do it by converting the vector from GF(2) to $\mathbb{Q}$ then summing entries.
b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])
bQ = vector(QQ,b.list()) # change field to rationals
sum(bQ)
3
Now we'll find all 4 solutions to Example 24.1.
b=vector(GF(2), [1,1,0,0,1, 1,1,1,0,0, 1,0,0,0,1, 0,0,1,1,1, 1,0,0,1,1])
x=lights_out(5).solve_right(b) # one solution
nulsp = lights_out(5).right_kernel()
for d in nulsp:
print x+d, number_of_presses(x+d)
(0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0) 12 (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1) 8 (0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0) 8 (1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1) 20
An optimal solution is (1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1), which contains 8 presses.
# Definition of the matrix for Lights Out
# input = integer n (where lights out board is nxn)
# output = lights out matrix A which is n^2 x n^2
def lights_out(n):
A = identity_matrix(GF(2),n*n) # initialize A with ones along diagonal
for i in range(n):
for j in range(n):
m = n*i+j
if i > 0 : A[(m,m-n)] = 1 # I block below diagonal
if i < n-1 : A[(m,m+n)] = 1 # I block above diagonal
if j > 0 : A[(m,m-1)] = 1 # C block below diagonal
if j < n-1 : A[(m,m+1)] = 1 # C block above diagonal
return A
# Function: number_of_presses
# input = a vector x of dimension 25 with 0,1 entries
# output = the number of times 1 appears as an entry
def number_of_presses(x):
counter=0;
for i in range(0,25):
if x[i]==1: counter=counter+1
return counter
# Function: optimal_solution
# input = a strategy vector x
# output = an equivalent strategy vector which uses the minimum number of button presses
def optimal_solution(x):
op_button_presses=x
n=number_of_presses(x)
nul=lights_out(5).right_kernel()
for d in nul:
if number_of_presses(x+d)<n:
op_button_presses=x+d # update variable
n=number_of_presses(x+d) # update variable
return op_button_presses
# Function: lights_out_solver
# input = b the configuration vector of lights on 5-by-5 game
# output = a matrix which solve the puzzle using the least number of button presses
def lights_out_solver(b):
x=lights_out(5).solve_right(b); # one solution
x=optimal_solution(x) # exchanges x for an optimal solution
button_press_matrix = matrix(GF(2),5,5,x.list())
return button_press_matrix
# Example
b=vector(GF(2),[0,0,0,0,0, 0,0,0,0,0, 1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0]);
lights_out_solver(b)
[1 0 1 0 1] [1 0 1 0 1] [0 0 0 0 0] [0 0 0 0 0] [0 0 0 0 0]
I25=MatrixSpace(GF(2),25,25).identity_matrix() # 25x25 identity matrix
A=lights_out(5);
(A-I25).nullity()
5