2
$\begingroup$

This question concerns a problem I ran into when trying to design a puzzle for someone. Although I could design one of these puzzles with some reasoning, I was bothered by being unable to come up with a method to describe the problem properly to design puzzles of arbitrary complexity. I've come up with somewhat of a solution but I'm not sure how to apply it practically, any help would be appreciated. :)

Problem statement

The problem is related to a classic puzzle format that appears often in games, namely the following:

Given is a setting with N lights and N levers. In the starting position all lights are off. Each lever is connected to at least 1 light. If a lever is flipped, all the connected lights switch state. The goal of the player is to flip the levers such that all the lights are on.

An example of a setup can be seen in the image below

enter image description here

The problem for the designer then is to, given N and a desired solved state of the levers, find find any or all sets of connections which would result in a puzzle where the desired lever states will uniquely result in the win condition. (Finding the entire set would be interesting as it would allow to for instance choose harder puzzles with more connections)

Attempt at solution

One way to approach the problem could be to describe the desired state as a binary vector $\vec{s}$ and the connections as a matrix $C$, where the $C_{i,j}=1$ if lever $i$ is connected to lamp $j$. For the shown problem this would give

$$\vec{s}=\begin{bmatrix} 1 & 0 & 1 & 1 & 1 \end{bmatrix}$$

$$C = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

I've at least derived the following requirements on the connections:

  • If $C$ contains duplicate rows or otherwise dependent rows, multiple solutions will be possible, and each column and row must contain at least one entry. Therefore $C$ must be full rank for the puzzle to have a unique solution.
  • In order for the desired lever state to be a solution to the puzzle, all lights must be on when the levers are pressed, so it must receive an odd number of signals. Then for each column the sum of the entries on rows for which the solution has a 1 must be odd. Thus, all entries of $\vec{s}{C}$ must be odd. In case of the example: $$\vec{s}{C} = \begin{bmatrix} 3 & 1 & 1 & 1 & 3 \end{bmatrix}$$

My question now is how to use these constraints to find the set of matrices $C$ that solve the problem, if at all possible. Are these constraints correct and sufficient to do this?

Perhaps to take it a step further - what could some algorithm to generate these matrices randomly look like?

$\endgroup$
5
  • $\begingroup$ Is this just lights out? It is nothing but a system of linear equations over $\Bbb F_2$. $\endgroup$
    – WhatsUp
    Oct 9, 2021 at 0:03
  • $\begingroup$ lights out seemed distinctly different to me since the buttons only alter adjacent lights, aside from it taking place on a 2D grid. $\endgroup$ Oct 9, 2021 at 0:09
  • $\begingroup$ The principal is the same, you still have linear equations over $\Bbb F_2$ (assuming you know what that means). $\endgroup$
    – WhatsUp
    Oct 9, 2021 at 0:12
  • $\begingroup$ I see how it is a linear system of equations, I'm just not sure how to choose (or generate at random) a system of linear equations that both leads to $C$ being full rank and the constraint on the product $\vec{s}C$ $\endgroup$ Oct 9, 2021 at 0:13
  • $\begingroup$ The question then boils down to "how to generate linearly independent binary vectors" I suppose. That could be done by just generating random binary vectors and discarding them if they are dependent. For the odd sum I'd only need to consider the $M<N$ rows for which the entry in $\vec{S}$ is 1. The only worry then is if it is possible to somehow end up with a situation where the first independent vectors make it impossible (or very unlikely) for the last vector to complete the odd sum and be independent. Don't know if there's anything math related to say about that. $\endgroup$ Oct 9, 2021 at 0:27

1 Answer 1

2
$\begingroup$

When the number of levers is equal to the number of lights, the constraint on $C$ (which you added to make sure that the solution is unique) also guarantees that a solution exists. If the matrix is full rank modulo $2$, then no two positions of levers result in the same configuration of lights. There are $2^n$ positions of levers and $2^n$ configurations of lights, so this means that some position of the levers turns all the lights on.

To find the vector $\vec s$ that solves the problem, we just solve the system of equations $\vec s C = \vec 1$ modulo $2$ (in other words, working over $\mathbb F_2$). This works just like ordinary Gaussian elimination, except $1+1 = 0$.

The condition "$C$ is full rank modulo $2$" is equivalent to the condition "the determinant of $C$ is an odd integer". So one way to pick a random puzzle is to pick a completely random $C$ (flipping a coin for each entry), find its determinant, and if the determinant is even, start over.

A different approach is iterative, going lever by lever. The idea here is to have a collection $\mathcal B$ of "bad sets of lights": sets of lights that the next levers should not control.

  1. Initially, $\mathcal B$ consists of just the empty set $\emptyset$: we should not have a lever that controls no lights. The first lever can control any of the other $2^n-1$ subsets.
  2. After we've chosen the outputs of $k$ levers, $\mathcal B$ consists of all the $2^k$ sets of lights that we can flip by toggling those $k$ levers. The next lever should not toggle a set of lights that we can already toggle with the existing $k$ levers; we can choose any of the $2^n - 2^k$ sets not in $\mathcal B$.
  3. Repeat until we've chosen all $n$ levers.

We see that there are $$ \prod_{k=0}^{n-1} (2^n - 2^k) = (2^n - 1)(2^n-2)(2^n-4) \dotsm (2^n - 2^{n-1}) $$ possible puzzles we can get in this way. (We can get every valid puzzle, so that's also the number of valid puzzles that there are.) As $n \to \infty$, this approaches an approximately $0.288$ fraction of the $2^{n^2}$ total puzzles that there are (valid or not). So in fact the pick-a-random-$C$ method from earlier also has a better than $\frac14$ chance of working every time we try it.

$\endgroup$
3
  • $\begingroup$ The condition "C is full rank modulo 2" is equivalent to the condition "the determinant of C is an odd integer". This is excellent, thank you. Just for my understanding with ,"full rank modulo 2" you mean to specify that this holds here because we're using a matrix with binary entries, but does not hold in general for non-binary matrices? $\endgroup$ Oct 9, 2021 at 0:46
  • $\begingroup$ By "full rank modulo $2$" I mean that we're checking for linear independence modulo $2$. For example, the matrix $\begin{bmatrix}1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1\end{bmatrix}$ is full-rank over $\mathbb R$, but not modulo $2$, because its rows add up to $\begin{bmatrix}0 & 0 & 0\end{bmatrix}$ modulo $2$. $\endgroup$ Oct 9, 2021 at 0:53
  • $\begingroup$ That makes sense, thanks again. $\endgroup$ Oct 9, 2021 at 1:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .