# Exact Method for Generating Strategy-Solvable Sudoku Clues
## 1 Introduction
It seems that strategy-solvability has been recognized intuitively, and no formal  
Figure 2: Clue positions (**left**) and clues solvable with naked singles only (**right**). treatment has been given so far. In this paper, we introduce a rigorous framework to discuss solvability for Sudoku instances with respect to strategies and define the notion of strategy-solvable Sudoku clues. This allows us to handle not only known strategies but also general strategies under a few reasonable assumptions. We then propose an exact method for determining strategy-solvable Sudoku clues for a given set of clue positions that is solvable with a given set of strategies. The key is a reduction to a constraint satisfaction problem (CSP). Our method is able to benefit from the power of state-of-the-art CSP solvers. Pruning techniques of CSP solvers are expected to be effective for the first issue above. Moreover, as long as any complete CSP solver is utilized, it is guaranteed that if a set of clue positions is not strategy-solvable, our method eventually recognizes the unsolvability; otherwise, our method eventually finds strategy-solvable clues. This is the first exact method except for a trivial brute-force search. As strategies allowed in completing Sudokus, this paper employs naked singles, hidden singles, and locked candidates [1], which are quite basic yet powerful enough to complete many Sudokus. Indeed, we have confirmed that the combination of the three strategies allows for solving as many as 37,373 of the 49,151 minimum Sudokus (i.e., Sudokus with 17 clues) collected by [PERSON] [5]. Here we remark that our CSP formulation is almost independent of specific strategies. In order to allow other strategies, it is sufficient to formulate the corresponding logical constraints and add them with a minor modification of the strategy-independent part. Besides the clue generation, we present an application of our method to the problem of determining the minimum number of Sudoku clues that are solvable with a given set of strategies. We demonstrate that our method is easily customized for this problem with a small modification in the CSP constraints. It is well-known that there is no proper Sudoku with 16 or less clues [6]. There are many Sudokus with 17 clues that are solvable with basic strategies such as hidden singles. Interestingly, this may not be the case for naked singles, arguably one of the most basic strategies, as we have confirmed that no grid solvable with only naked singles is included in the minimum Sudoku collection. This poses an open problem of whether there is a gap between the minimum numbers for strategy-solvable Sudokus and proper Sudokus. Our method will be useful in tackling this problem thanks to the ability of determining unsolvability. We conduct experiments to compare our method with the generator of Zama and Sasano [2], using grids varying the position and the number of clues at random. From the results, we observe that our method terminates within 1 min for many instances, showing our method being stable in terms of running time. However, as the number of clues gets closer to 20, the running time rapidly increases and exceeds a time limit. On the other hand, the generator of Zama and Sasano can often find solutions much faster even with close to 20 clues, while the performance sharply deteriorates around 45 clues and exceeds the time limit for all grids with more clue positions. Perhaps this is due to the exponential blow-up of the search space (in other words, the exponential decline in the density of solutions). We also evaluate our method for several instances with 17 clue positions taken from known minimum Sudokus to see the efficiency for deciding unsolvability. The main contributions of the present paper are to formulate the concept of strategy-solvability, to establish an exact method for the strategy-solvable Sudoku clues problem, and to demonstrate the flexibility of the CSP-based approach. It remains as future work to improve our method for less clues.