Link’s Color Puzzle

I've just seen that this approach is not original ( @Piotr Idzik references a paper on it) but thought it might be interesting to add a different method to the discussion.

We'll work on the general $n \times n$ case, then look at a specific example.

Code the lights by their colour: use $1$ for blue lights and $0$ for red. Toggling a light's colour is equivalent to adding $1$ to its value, working modulo $2$ .

Define a "hit matrix" $\bold{H}$ by $H_{ij}=1$ if the light in position $(i,j)$ is hit, and $0$ otherwise. Define the starting checkerboard pattern as $\bold{C}$ , where $C_{ij} \equiv i+j+1 \pmod2$ . We can also define the final, all blue setup as $\bold{B}$ with all entries equal to $1$ .

The final colour of the light in position $(i,j)$ is given by $C_{ij}+H_{ij}+H_{i-1,j}+H_{i,j+1}+H_{i+1,j}+H_{i,j-1}$ , where we ignore indices outside the range $[1,n]$ . We want this to be congruent to $1 \pmod2$ for all $(i,j)$ .

The idea is to solve a linear equation in $\bold{H}$ to find a hit matrix that works. However, to do this, we need (I think) to rewrite the entries of $\bold{H}$ as a column vector, $\bold{H_v}=\left(H_{11},H_{12},\ldots,H_{1n},H_{21},\ldots,H_{nn} \right)^T$ . Because this column vector has $n^2$ entries, I'll discuss the $3 \times 3$ case first.

Let's start writing equations modulo $2$ . The first row of lights give:

$\begin{aligned} 1+H_{11}+H_{12}+H_{21} &\equiv 1 \\ 0+H_{11}+H_{12}+H_{13}+H_{22} &\equiv 1 \\ 1+H_{12}+H_{13}+H_{23} &\equiv 1 \end{aligned}$

Continuing this way, we get the following equation:

$\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 \\ 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\end{pmatrix} \bold{H_v} = \bold{M}\cdot \bold{H_v} \equiv \bold{B}-\bold{C}$

This looks daunting, but is linear. The determinant of $\bold{M}$ is odd, which means it has an inverse modulo $2$ . This means there is a unique solution to the equation!

We can solve the equation using Cramer's rule ; as expected, the final result is

$\bold{H}=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$

Now, of course, this result in itself just repeats the animation in the question. But we get the following useful information:

• any size grid can be encoded in this way; the pattern of the coefficient matrix $\bold{M}$ continues in the obvious way

• if the determinant of $\bold{M}$ is odd, there is a unique solution (so there is no question of the minimum number of hits, or even of the pattern)

• if the determinant of $\bold{M}$ is odd, we can use Cramer's rule to directly generate the solution

Now let's turn to the $5 \times 5$ case of the question. We can set all the matrices and $\bold{H_v}$ up in exactly the same way. And what do we find for $\det{\bold{M}}$ ?

It is, of course, even.

But this just means there is not a unique solution. If we reduce the matrix by removing the first two rows and first two columns, we get a matrix $\bold{M'}$ whose determinant is odd.

This matrix reduction means we have some freedom of choice; we can choose which of the first two lights (in positions $(1,1)$ and $(1,2)$ ) are hit - in other words, there are four solutions. But this is exactly what we expect! As shown in the other solutions, the winning matrix is

$\bold{H}=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

and its rotations. Each of the four rotations corresponds to a choice of which of the first two lights are hit.

So, without needing to analyse the $2^{25}$ different hit matrices, we have shown there is a unique solution with $\boxed{10}$ hits, up to rotation.

Some questions I have about this approach:

• is there a better method for solving the equations than Cramer's rule? If it's possible to compute $\bold{M}^{-1}$ easily, that would make the calculation much quicker

• how many degrees of freedom are there for each $n$ ? (ie, how many hits do we have to choose before we get to a non-singular matrix?) If there are multiple valid configurations, is there a quick way to determine which ones minimise the total number of hits?

• alternatively, which $n$ - like $n=3$ - have $\det{\bold{M}} \equiv 1 \pmod2$ (ie no degrees of freedom)?

• is it possible to set up the equations so that we solve for $\bold{H}$ directly in its matrix form? (This seems to involve pre- and post-multiplying coefficient matrices; we essentially get an equation of the form $\bold{AH}+\bold{HA} \equiv \bold{B}-\bold{C}$ , but I'm not sure how to solve these)

We need to hit the balls on the positions: ((0, 0), (0, 1), (0, 2), (2, 1), (2, 4), (3, 0), (3, 2), (3, 4), (4, 1), (4, 4)). Above sequence is also the shortest possible. Observe, that the order of hits does not matter.

It seems, that such problems all well known and that they are efficiently solved using some linear algebra (linear spaces over the field $\mathbb{Z}_2$ ). The game is called "Lights out". Cf. Marlow Anderson, Todd Feil (1998). "Turning Lights Out with Linear Algebra" . Mathematics Magazine. 71 (4): 300–303.

Besides that, I have written the following script to obtain a solution. It iterates through all of the possible hit lists (up to rotations/reflections/order of hits). It is a parallel code. But it is not really useful for bigger grids.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

"""
brute-fore solution of the problem:
https://brilliant.org/problems/links-color-puzzle/
"""
import time
import timeit
import copy
import itertools
from multiprocessing import Process, Queue, cpu_count

def make_hit(in_data, pos_vec):
    """
    performs a single ball hit on a given ball set
    """
    def inner(cur_data, in_x, in_y):
        if 0 <= in_x < len(in_data) and 0 <= in_y < len(in_data):
            cur_data[in_y][in_x] = not cur_data[in_y][in_x]
    out_data = copy.deepcopy(in_data)
    pos_x, pos_y = pos_vec
    inner(out_data, pos_x, pos_y)
    inner(out_data, pos_x+1, pos_y)
    inner(out_data, pos_x-1, pos_y)
    inner(out_data, pos_x, pos_y+1)
    inner(out_data, pos_x, pos_y-1)
    return out_data

def grouper(iterable, block_size, fillvalue=None):
    "Collect data into fixed-length chunks or blocks"
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
    args = [iter(iterable)]*block_size
    return itertools.zip_longest(*args, fillvalue=fillvalue)

def find_correct_hits(start_data, end_data, hit_list_data, res_queue):
    """
    finds the hits from hit_list_data, which lead from start_data to end_data
    """
    local_res = set()
    for cur_hit_list in hit_list_data:
        if cur_hit_list:
            tmp_data = copy.deepcopy(start_data)
            for cur_hit in cur_hit_list:
                tmp_data = make_hit(tmp_data, cur_hit)
            if tmp_data == end_data:
                local_res.add(cur_hit_list)
    for cur_res in local_res:
        res_queue.put(cur_res)

def gen_hit_list(data_size, hit_list_len):
    """
    generator;
    generates a sequence of all (up to rotation/reflection) hits of the length hit_list_len
    """
    def flip_x_hit_list(in_hit_list, sol_size):
        def proc_single_hit(in_hit):
            return (sol_size-1-in_hit[0], in_hit[1])
        return tuple(sorted((proc_single_hit(_) for _ in in_hit_list)))

    def flip_y_hit_list(in_hit_list, sol_size):
        def proc_single_hit(in_hit):
            return (in_hit[0], sol_size-1-in_hit[1])
        return tuple(sorted((proc_single_hit(_) for _ in in_hit_list)))

    def rotate_hit_list(in_hit_list, sol_size):
        def proc_single_hit(in_hit):
            return (sol_size-1-in_hit[1], in_hit[0])
        return tuple(sorted((proc_single_hit(_) for _ in in_hit_list)))
    generated_hits = set()
    all_pos_gen = itertools.product(range(data_size), repeat=2)
    all_hit_data_gen = itertools.combinations(all_pos_gen, hit_list_len)
    for cur_hit in all_hit_data_gen:
        was_before = False
        if cur_hit in generated_hits:
            was_before = True
        elif flip_x_hit_list(cur_hit, data_size) in generated_hits:
            was_before = True
        elif flip_y_hit_list(cur_hit, data_size) in generated_hits:
            was_before = True
        else:
            tmp_hit_list = rotate_hit_list(cur_hit, data_size)
            if tmp_hit_list in generated_hits:
                was_before = True
            else:
                tmp_hit_list = rotate_hit_list(tmp_hit_list, data_size)
                if tmp_hit_list in generated_hits:
                    was_before = True
                else:
                    tmp_hit_list = rotate_hit_list(tmp_hit_list, data_size)
                    if tmp_hit_list in generated_hits:
                        was_before = True

        if not was_before:
            yield cur_hit
            generated_hits.add(cur_hit)

def find_hit_list_given_len_all_par(start_data, end_data, hit_list_len, max_proc_num, max_block_size):
    """
    tries to find a sequence (of given length) of hits
    leading from the start_data to end_data
    """
    def count_running(in_proc_list):
        res = 0
        for cur_proc in in_proc_list:
            if cur_proc.is_alive():
                res += 1
        return res
    proc_list = []

    res_queue = Queue()
    for cur_hit_list_data in grouper(gen_hit_list(len(start_data), hit_list_len), max_block_size):
        cur_proc = Process(target=find_correct_hits,
                           args=(start_data, end_data, cur_hit_list_data, res_queue, ))
        cur_proc.start()
        proc_list.append(cur_proc)
        while count_running(proc_list) >= max_proc_num:
            time.sleep(0.1)
        proc_list = [_ for _ in proc_list if _.is_alive()]
    for cur_proc in proc_list:
        cur_proc.join()

    res = set()
    while not res_queue.empty():
        res.add(res_queue.get())
    return res

def sol_to_str(in_sol, sol_size=None):
    """
    returns a eye-friendly representation of a solution
    """
    if not sol_size:
        sol_size = max(max(_) for _ in in_sol)+1
    raw_str = [['+']*sol_size for _ in range(sol_size)]
    for (pos_x, pos_y) in in_sol:
        raw_str[pos_y][pos_x] = '*'
    return '\n'.join([''.join(_) for _ in raw_str])

def find_shortest_hit_list(start_data, end_data, max_proc_num, max_block_size):
    """
    fids all (up to rotation/reflection) of the shortest hit lists leading from
    start_data to end_data
    """
    sol_set = set()
    cur_len = 1
    while len(sol_set) == 0:
        start_time = timeit.default_timer()
        cur_sol_set = find_hit_list_given_len_all_par(start_data, end_data, cur_len,
                                                      max_proc_num, max_block_size)
        end_time = timeit.default_timer()
        print(f"runTime for {cur_len}: {end_time-start_time} [s]")
        if len(cur_sol_set) > 0:
            for cur_sol in cur_sol_set:
                print(f"{cur_sol} (length: {len(cur_sol)})")
                print(sol_to_str(cur_sol))
            sol_set = cur_sol_set
        cur_len += 1
    return sol_set

if __name__ == '__main__':
    TEST_N = 5
    DATA_A = [[False]*TEST_N for _ in range(TEST_N)]
    for (p_x, p_y) in itertools.product(range(len(DATA_A)), repeat=2):
        if (p_x+p_y)%2 == 1:
            DATA_A[p_x][p_y] = True
    DATA_B = [[False]*TEST_N for _ in range(TEST_N)]
    START_TIME = timeit.default_timer()
    ALL_SOL_DATA = find_shortest_hit_list(DATA_A, DATA_B, cpu_count(), 30000)
    END_TIME = timeit.default_timer()
    print(f"runTime: {END_TIME-START_TIME} [s]")

idk i just guess and got it right because i played that game on nintedo , so i know that

I got this right by just estimating in my head.