Buggy Switches


Game Description

We have some switches in the game. Some of the switches are closed and the others are open at the initial condition, and game is succesfully completed whenever all switches become open.

But unfurtunately these switches are kind of buggy. All switches are implicity one-way connected to some other switches and whenever some switch toggles, it also toggles all other switches that are connected to it.

Given n number of switches with their status at initial condition, and other switches that are connected to them, find the quickest way to make all switches open from initial condition.


An Example Demonstration

There are three switches \(s_1, s_2, s_3\).
\(s_1\) is connected to \(s_2\) and \(s_3\),
\(s_2\) is connected to \(s_1\),
\(s_3\) is connected to \(s_2\).

At the initial state, \(s_1\) is closed, \(s_2\) and \(s_3\) are open:




Let's toggle \(s_1\). Also \(s_2\) and \(s_3\) will be toggled because \(s_1\) is one-way connected to \(s_2\) and \(s_3\):




Now if we toggle \(s_3\), then \(s_2\) is toggled as well:




Eventually all switches have become open and we succesfully completed the game.


Formal Definition

In order to algorithmically solve the problem, we need to formalize it.

There are \(n\) number of switches such as \(s_1, s_2, \dots, s_n \in S\).

For any time \(t\), the state of the board is denoted by \(q_t\), and \(t = 0\) is the initial state.
\(q_t\) is the set of values \(v_1^t, v_2^t, \dots, v_n^t\), i.e. \(q_t = \{ v_n^t \}\),
where \(v_n^t\) denotes the value of \(s_n\) at time \(t\).

\(v_n^t = 0 \iff s_n \text{ is open at time } t \)
\(v_n^t = 1 \iff s_n \text{ is closed at time } t \)

At initial state \(q_0\), some of the \(v \in q_0\) are equal to \(0\), and the others are equal to \(1\).
After \(m\) number of finite steps, game is successfully completed.
\(\forall v \in q_m, v=0\)

Each switch \(s_n\) is one-way connected to zero or more other switches.
\(C(n)\) is the set of all switches such that if \(n\) is toggled, all switches in \(C(n)\) will be also toggled.
Notice that \(C(n)\) also contains \(n\) itself.
\(C(n) = \{ s_i | s_i=s_n \text{ or } s_n \text{ is connected to } s_i \}\)

\(f(q, s):Q\to Q\) is a toggle function such that, \(f(q, s)\) is the new state after \(s\) switch is toggled in state \(q\).


The Solution

After formal description, we can find the solution.

Proposition 1. \(f(f(q, s), s) = q\)
i.e if we toggle some switch two times consecutivly, nothing changes obviously.

Lemma 1. \(f(f(q, s_a), s_b) = f(f(q, s_b), s_a)\)
i.e \(f\) is commutative.

Proof.
At time \(t\) board is in \(q\) state. For a switch \(s_n\), \(C(s_a)\) and \(C(s_b)\) may or may not contain \(s_n\). There are 4 cases in this manner:
Case 1: \(s_n \notin C(s_a) \text{ and } s_n \notin C(s_b) \)
  In this case no change occurs obviously.
Case 2: \(s_n \in C(s_a) \text{ and } s_n \notin C(s_b) \)
  If we first toggle \(s_a\) and then \(s_b\), \(v_n^{t+2} = v_n^{t+1} = \neg v_n^{t}\)
  If we first toggle \(s_b\) and then \(s_a\), \(v_n^{t+2} = \neg v_n^{t+1} = \neg v_n^{t}\)
  Either case \(v_n^{t+2}\)'s are the same.
Case 3: \(s_n \notin C(s_a) \text{ and } s_n \in C(s_b) \)
  This case is the same with Case 2. \(s_a\) and \(s_b\) can be replaced without loss of generality.
Case 4: \(s_n \in C(s_a) \text{ and } s_n \in C(s_b) \)
  This holds obviously by Propositon (1).
Therefore \(f\) is commutative. □

Corollary 1. Switches can be toggled in any order. The final state will not be changed. By Lemma (1).

Definition 1. \(D_n = \{ s_m | s_n \in C_m \}\)
i.e. \(D_n\) is the set of all switches such that toggling one of those switches will cause \(s_n\) to be toggled also.

Definition 2. \(d_n = |D_n|\)
i.e. \(d_n\) is the cardinality of \(D_n\).

Definition 3. \(T_n\) is the set of all switches that are toggled manually from \(t=0\) to \(t=m\).
By Proposition (1) and Corollary (1), such a set will be necessary and sufficient description of the game movements.

Definition 4. \(x_n\) is total number of times that \(s_n\) is toggled manually.

Solution Modeling
Now we are modeling the solution as a linear equation system over a finite field \(GF(2)\).
For each \(s_i \in S\) there is exactly one equation such that:
\[x_{k_1} + x_{k_1} + \dots + x_{k_n} = v_n^0 \] where \({k_1} , {k_1} , \dots , {k_n}\) are the indices of the switches \(s_k \in D_n\)

Such a reduction to linear equation system has complexity of \(\mathcal{O}(n^2)\), and solution of that system is \(\mathcal{O}(n^3)\).


Applying Solution to Example Game

Remember the example game instance above.
We have 3 switches: \(s_1, s_2, s_3\).

\(v_1^0 = 1, v_2^0 = 0, v_3^0 = 0\)

\(C_1 = \{ s_1, s_2, s_3 \}\)
\(C_2 = \{ s_1, s_2 \}\)
\(C_3 = \{ s_2, s_3 \}\)

\(D_1 = \{ s_1, s_2 \}\)
\(D_2 = \{ s_2, s_3 \}\)
\(D_3 = \{ s_2, s_3 \}\)

Hence we have the equation system: \[x_1 + x_2 = 1\] \[x_1 + x_2 + x_3 = 0\] \[x_1 + x_3 = 0\]

With solutions:
\(x_1 = 1, x_2 = 0, x_3 = 1\)
Therefore, one should toggle \(s_1\) and \(s_3\) in order to complete the game.


Uniqueness of The Solution

The solution is not necessarily unique. For example game configuration may lead to a equation system such as: \[x_1 + x_2 = 1\] \[x_1 + x_2 = 1\] Obviously there are two possible solutions in this case.
\((x_1, x_2) = \{(0, 1), (1, 0)\}\)
However solution which has the minimum number of \(1\)'s in it is always optimal.


Proof of Optimality

The proposed solution is trivially optimal, because the system is defined over a finite field \(GF(2)\), and therefore values of the \(x_n\) is either zero or one. That is, there is no redundancy by Proposition (1).

Also if there is more than one solution of the equation system, the optimal solution of the equation system is the optimal solution of the game.


Existence of The Solution

The game instance has a solution if and only if generated linear equation system over a finite field \(GF(2)\) has a solution.