# Exact Method for Generating Strategy-Solvable Sudoku Clues
## 1 Introduction  
Sudoku is a popular number placement puzzle. In an ordinary Sudoku (Figure 1), given a partially completed 9 \(\times\) 9 grid, the goal is to fill in all empty cells with digits from 1 to 9 in such a way that each cell has a single digit, and each digit appears only once in every row, column, and 3 \(\times\) 3 subgrid. Sudokus that appear in books, newspapers, and so on often have the following characteristics:  
1. The arrangement of initial digits (called _clues_) forms a regular pattern. 2. The level of difficulty is moderate. Figure 1: Sudoku clues (**left**) and its solution (**right**). Regarding 1, for example, the left grid of Figure 1 has reflection symmetry on the two diagonal axes. It may also have the shape of a number, a letter, or a symbol. Regarding 2, completing Sudokus generally requires backtracking, which is amenable to computers. On the other hand, 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. A _strategy-solvable Sudoku_ is a partially completed grid that can be completed by applying strategies repeatedly. Here, the strategies must be selected from a set of predetermined ones. Since there is no need to guess, strategy-solvable Sudokus (at least for a few basic strategies) might be referred to as Sudokus having a moderate level of difficulty for humans. Making new Sudoku instances having these characteristics is not an easy task. There is a public software (The generator of Zama and Sasano [2][[http://www.cs.ise.shibaura-it.ac.jp/2016-GI-35/SudokuGenerator.tar.gz](http://www.cs.ise.shibaura-it.ac.jp/2016-GI-35/SudokuGenerator.tar.gz)]([http://www.cs.ise.shibaura-it.ac.jp/2016-GI-35/SudokuGenerator.tar.gz](http://www.cs.ise.shibaura-it.ac.jp/2016-GI-35/SudokuGenerator.tar.gz)), accessed on 26 May 2020) that is able to generate Sudokus from a given set of clue positions so that they are solvable with some known strategies. However, it is still hard to generate those with 20 or less clues and those with around 45 or more clues. For such instances, there might be no other choice but to rely on human intelligence involving the intuition, the inspiration, and the experience of enthusiasts. In this paper, we consider a method for determining Sudoku clues in specified positions such that all empty cells can be filled in with a specified set of strategies (see Figure 2). Almost all Sudoku generators simply output proper Sudoku instances (i.e., partially completed grids having unique solutions). Clue arrangements and strategies necessary for solving are uncontrollable. To the best of our knowledge, the only exception is the generator of Zama and Sasano mentioned earlier. Their generator is based on the generate-and-test method, which repeats the following steps until the test is passed or the number of trials exceeds a predetermined limit:  
1. Generate clues in specified positions. 2. Test whether all other cells are completed using specified strategies only. A similar idea is also mentioned in [3; 4]. Since the test step can be done quickly, the key is to devise a criterion for the generation step so that the number of trials is as small as possible. Since the generate-and-test method examines only a limited portion of the vast search space, it has the drawbacks listed below:  
* The lower the density of solutions (i.e., strategy-solvable clues) over the whole search space becomes, the harder it becomes to find a solution. * If a set of clue positions happens to be not strategy-solvable, it is unable to recognize it no matter how much time passes. * Even for a strategy-solvable set of clue positions, there is no guarantee for being able to find a solution in a finite amount of time. To tackle these issues (in particular the last two), we consider it necessary to formulate the concept of strategy-solvability.