# Exact Method for Generating Strategy-Solvable Sudoku Clues
## 2 Preliminaries
### Strategies  
There is a set of techniques (called _strategies_) that humans use in solving Sudokus by hand [1]. Typically strategies are if-then rules: If a strategy is applicable to the current grid, then it might rule out digits as candidates or might determine digits as those to be finally placed. Throughout the following explanation, let \(n\) be a non-zero digit and \((i,j)\) be a cell.  
A _naked single_ is a strategy that places \(n\) in \((i,j)\) if no other candidate but \(n\) remains at \((i,j)\). For example, let us look at the gray cell \((4,7)\) in the left grid of Figure 3. Since all digits but 5 appear in either group having \((4,7)\), these digits must be ruled out and only 5 remains. Hence, 5 is placed in \((4,7)\). Starting with the left grid of Figure 3, one can reach the right grid using only naked singles, but cannot proceed any more because of two or more candidates over all empty cells.  
A _hidden single_ is a strategy that places \(n\) in \((i,j)\) if there is a group \(G\) having \((i,j)\) such that no cell in \(G\setminus(i,j)\) has \(n\) as a candidate. For example, let us look at the right grid of Figure 3. For the row of index 1, we can observe that every cell in the row except for the gray cell \((1,6)\) does not have 7 as a candidate. Indeed, for any such cell, 7 already appears in another cell of the same column. Hence, a hidden single strategy determines 7 in \((1,6)\). In this way, by applying hidden singles repeatedly, the grid can be completed.  
Let \(A,B\) be groups such that \(|A\cap B|=3\). A _locked candidate_ is a strategy that rules out \(n\) over all cells in one difference set \(B\setminus A\) if no cell in the other difference set \(A\setminus B\) has \(n\) as a candidate. For example, let us look at the right grid of Figure 3. Let \(A\) be the column of index 7, and let \(B\) be the  
Figure 3: Starting with the partially completed grid on the (**left**), one can reach the grid on the (**right**) using only naked singles but cannot proceed any more.  
block adjacent, on the right, to the center block. No empty cell in \(A\setminus B\) has \(3\) as a candidate because for each such cell, there is another cell in the same row to which \(3\) is already placed. Hence, \(3\) is ruled out for all empty cells in \(B\setminus A\). Because of this, \(2\) becomes a unique candidate at \((3,6)\). It is determined as the digit at \((3,6)\) by a naked single. In this way, the grid can also be completed using locked candidates as well as naked singles.  
Figure 4 is an example of a grid showing that locked candidates are independent of the combination of naked singles and hidden singles. Actually, none of the empty cells can be determined using naked singles and hidden singles, but if locked candidates are allowed in addition, then there is an empty cell that can be filled in.  
To see this, look at cell \((8,4)\) in Figure 4. All candidates except \(5\) are removed by applying locked candidates. Indeed, let \(A\) be the \(6\)-th row and \(B\) be the block to which \((8,4)\) belongs. Since no cell in \(A\setminus B\) has \(4,8\), and \(9\) as candidates, these digits are removed from candidates at \((8,4)\), and only \(5\) remains. Hence, by applying naked singles to this cell, \(5\) is determined. In this way, this grid can be completed, which shows that locked candidates are independent of the combination of naked singles and hidden singles.