# Exact Method for Generating Strategy-Solvable Sudoku Clues
## 3 Formulation  
Although some known strategies are introduced in the previous section and some solvable cases are explained using particular grids, there are still unclear points, such as what is a strategy in general and what operations are allowed for placing or ruling out digits. In this section, we thus introduce a rigorous framework to discuss solvability for Sudoku instances. This allows us to handle not only known strategies but also general strategies under a few reasonable assumptions. This also makes it clear that, for example, it is not allowed to temporarily place digits and then cancel them when a contradiction occurs. Such an inference would allow us to do backtracking, which nullifies the restriction of completion methods. A _state transition model_ of Sudoku is a tuple \((Q,R,I,F)\) such that \(Q\) is the set of all possible states, \(R\) is a state transition relation, \(I\) is the set of initial states, and \(F\) is the set of final states. We will explain each component below. Figure 5 shows how a grid evolves as strategies are applied, which will be used as an example in the succeeding explanation. A _state of grid_ (or a _state_ in short) is a pair \((f,g)\) of functions. The function \(f\) maps the set of cells to the set of digits, and \(f\left(i,j\right)=n\) means that if \(n\
eq 0\), then \(n\) is placed in \((i,j)\); otherwise, no digit is placed. The function \(g\) maps the set of cells to the powerset of the set of non-zero digits, and \(g\left(i,j\right)\) represents the set of all candidates at \((i,j)\). Here, by abuse of notation, \(f\left(i,j\right)\) and \(g\left(i,j\right)\) denote \(f\left((i,j)\right)\)  
Figure 4: Grid showing that locked candidates are independent of the combination of naked singles and hidden singles. and \(g\left(\left(i,j\right)\right)\), respectively. All states must satisfy the conditions \(S_{1}\) and \(S_{2}\) below: for all cells \(\left(i,j\right)\) and non-zero digits \(n\),  
\[S_{1} g\left(i,j\right)\
eq\emptyset,\] \[S_{2} n\
ot\in g\left(i,j\right)\text{ if there is a different non-zero digit $n^{\prime}$ from $n$ such that $f\left(i,j\right)=n^{\prime}$ or there is a different cell $\left(i^{\prime},j^{\prime}\right)$ from $\left(i,j\right)$ with both in a common group such that $f\left(i^{\prime},j^{\prime}\right)=n$.}\]  
We denote by \(Q\) the set of all states. The antecedent of \(S_{2}\) is a condition for digits \(n\) that can be safely ruled out whenever some digits are placed. Imposing \(S_{2}\) ensures that all such digits are ruled out. This is simply to make all states have a type of normal form, and it would not deduce any wrong consequence as long as decisions for number placements are correct, such as not violating the properness. In Figure 5 we can observe that all grids are in \"normal form\". A _state transition relation_ is a binary relation \(R\subseteq Q\times Q\). The \(\left(q,q^{\prime}\right)\in R\) (or \(qRq^{\prime}\) in infix notation) means that there are strategies by which \(q\) is changed to \(q^{\prime}\). We refer to \(q\) and \(q^{\prime}\) as the _source state_ and the _target state_ of the transition, respectively. All state transitions must satisfy that for any cell \(\left(i,j\right)\) and non-zero digit \(n\), if \(f\left(i,j\right)=n\) holds in the source state, it does also in the target state; if \(n\
ot\in g\left(i,j\right)\) holds in the source state, it does also in the target state. This simply means that once digits are placed or ruled out it cannot be cancelled afterward. We put one more assumption as follows. For any three states \(q_{1}=\left(f_{1},g_{1}\right)\), \(q_{2}=\left(f_{2},g_{2}\right)\), and \(q_{3}=\left(f_{3},g_{3}\right)\) with \(q_{1}Rq_{2}\) and \(q_{2}Rq_{3}\), if \(g_{1}=g_{2}\), then \(q_{2}=q_{3}\). We consider this assumption not so strong. Indeed, many strategies, such as naked singles and hidden singles, decide to place digits by examining only candidates.