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?