N lights, N levers puzzle design - finding interesting connections for a given solution

Question

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

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?

Answer 1

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.