My friend was playing Dragon Age II recently and found a section of puzzles. Knowing that I really like doing puzzles, being a mathematician and everything, they asked me for some help

The puzzle is as follows, you have a $5\times 5$ grid of squares that currently has no picture on it and you want to turn it into a picture of Duke Prosper de Montfort by flipping the tiles. The problem is you can't just flip any tiles you want, whenever you flip a tile, all tiles adjacent to it flip too

When I first saw this puzzle I relatively quickly figured out how to come to a solution by using the method I will write out in this document. Unsatisfied with that however, I tried to figure out the solution without high-level theory and instead just fiddling with drawing on the grid. Two sides of A4 later and my friend giving up and going to google I decided to just do the mathematicians solution

The solution

Writing the grid as a matrix, we want to see which transformations we are allowed to do and then see which of these transformations create our desired solution, we'll say that a picture is showing if the entry is $1$ and not if the entry is $0$, doing this for some random moves

$ \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix} \to \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & \mathbf{1} & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix} \to \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & \mathbf{1} \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix} \to ... $

We see that by flipping some tile, what we're doing is adding some matrix that looks like $$ \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & \mathbf{1} & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{pmatrix} $$ but if we add to a position twice, they cancel to zero. Essentially we're adding mod $2$

This tells us that order doesn't matter and reduces our problem, letting $$ \mathcal{B} = \left\{\begin{pmatrix} \mathbf{1} & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \begin{pmatrix} 1 & \mathbf{1} & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix},... \right\} \subset \mathbb{F}_2^{5\times 5} $$ Our puzzle is now how to write $$ \mathbb{I} := \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{pmatrix} $$ As some linear combination of elements of $\mathcal{B}$

import numpy as np
import numpy.linalg as la
import galois
from itertools import *
import itertools

GF = galois.GF(2)

n = 5

At this point we don't really care that the board states are matrices, since we're just looking at linear combinations we want to think of them as just vectors in $\mathbb{F}_2^{25}$ and we want to write $\mathbb{I} = \sum_{v_i \in \mathcal{B}}a_i v_i$, writing this as a matrix equation, $$ \begin{pmatrix} \vert & \vert & & \vert \\ v_1 & v_2 & ... & v_{25} \\ \vert & \vert & & \vert \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_{25} \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \end{pmatrix} $$

#Conversion Code
def vec_to_mat(row):
    A = np.zeros((n,n))
    for i in range(n):
        for j in range(n):
            A[j][i] = row[i*n+j]
    return A

def mat_to_vec(mat):
    A = np.zeros(n*n)
    for i in range(n*n):
        A[i] = mat[i%n][int((i-i%n)/n)]
    return A

Now to me this is now a solved problem, but python is annoying and cant solve this problem unless the matrix is invertable. Annoyingly for us...

A = GF.Zeros((n*n,n*n))

for j in range(len(A)):
    A[j][j] = 1

    #adding a one in the adjacent places if they exist
    if (j+1) % n == j % n + 1:
        A[j+1][j] = 1
    if (j-1) % n == j % n - 1:
        A[j-1][j] = 1
    if j+n < n*n:
        A[j+n][j] = 1
    if j-n >= 0:
        A[j-n][j] = 1

#print(A)

print(la.matrix_rank(A))

23

So this matrix has rank $23$ not $25$ so it isn't invertable, luckily we can trick python into finding us a solution. We can rewrite the equation as $$0=\sum_{v_i \in \mathcal{B}} a_i v_i - \mathbb{I}$$ writing this as a matrix we get $$ \begin{pmatrix} \vert & \vert & & \vert & \vert\\ v_1 & v_2 & ... & v_{25} & \mathbb{I} \\ \vert & \vert & & \vert & \vert \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_{25} \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \end{pmatrix} $$ So what we want to find is the kernel of this new matrix and then restrict the kernel to those with a $-1$ at the end, although since we're in $\mathbb{F}_2$, $-1=1$ so we will actually look for those with a $1$ at the end

M = GF.Zeros((n*n,n*n+1))

for j in range(n*n):
    M[j][j] = 1
    if (j+1) % n == j % n + 1:
        M[j+1][j] = 1
    if (j-1) % n == j % n - 1:
        M[j-1][j] = 1
    if j+n < n*n:
        M[j+n][j] = 1
    if j-n >= 0:
        M[j-n][j] = 1

for j in range(n*n):
    M[j][n*n] = 1

print(M)

[[1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1]
 [0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1]]

And now we're essentially done, we just want to find the kernel of this matrix.

N = M.null_space()

print(len(N))

3

Since the kernel is 3 dimensional with basis N we have the whole kernel being $\{0, n_1, n_2, n_3, n_1+n_2, n_2+n_3, n_1+n_3, n_1+n_2+n_3\}$, for generality however I'll just make a function to give me the whole thing nomatter what

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return tuple(chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1)))

def generate_vector_space(basis):
    A = []
    for subset in powerset(basis):
        V = GF.Zeros(n*n+1)
        for vector in subset:
            V += vector
        A.append(V)
    return A

kernel = generate_vector_space(N)

for vec in kernel:
    if vec[len(vec)-1] == 1:
        print('=============')
        print(vec_to_mat(vec))
        print('=============')

=============
[[0. 0. 0. 1. 1.]
 [1. 1. 0. 1. 1.]
 [1. 1. 1. 0. 0.]
 [0. 1. 1. 1. 0.]
 [1. 0. 1. 1. 0.]]
=============
=============
[[0. 1. 1. 0. 1.]
 [0. 1. 1. 1. 0.]
 [0. 0. 1. 1. 1.]
 [1. 1. 0. 1. 1.]
 [1. 1. 0. 0. 0.]]
=============
=============
[[1. 1. 0. 0. 0.]
 [1. 1. 0. 1. 1.]
 [0. 0. 1. 1. 1.]
 [0. 1. 1. 1. 0.]
 [0. 1. 1. 0. 1.]]
=============
=============
[[1. 0. 1. 1. 0.]
 [0. 1. 1. 1. 0.]
 [1. 1. 1. 0. 0.]
 [1. 1. 0. 1. 1.]
 [0. 0. 0. 1. 1.]]
=============

So there we have our solutions, just click the tiles where there's a one and you should reveal the smug face of Duke Prosper de Montfort