# Exact Method for Generating Strategy-Solvable Sudoku Clues
## 7 Experiments
### Running Time Comparison  
We compared our CSP-based method (CSP) with the generator of Zama and Sasano [2] (ZS). The time limit was set to 600 s. In both methods, only naked singles, hidden singles, and locked candidates were allowed to be used. Although other strategies are implemented in the generator of Zama and Sasano, we restricted the program to the three strategies by modifying their program.  
We made a total of 100 input instances (i.e., sets of cells) by repeating the following procedure: select a number \(n\) from 20 to 79 at random, and generate distinct \(n\) cells at random. Table 1 shows the distribution of input instances with respect to the number of clues. All instances are confirmed to be strategy-solvable.  
In preliminary experiments we confirmed that the brute force algorithm exceeded the time limit (600 s) for all instances. Moreover, the implementation of a naive generate-and-test method (Clues for specified positions were randomly generated and it was tested in a straightforward way whether the set of the clues is strategy-solvable. The \"naive\" means that no elaborated heuristic is used in the generation step) could solve only 4 instances within the time limit. As will be described in Section 8, the naive generate-and-test method falls into one of the four major methods for Sudoku clue generation (called a forward search), which admit both a strategy-solvability aspect and a geometric constraint aspect. Both codes are made publicly available on our website.  
Figure 6 shows a cactus plot of running time comparison. Each point is plotted so that the \(x\)-coordinate is the number of instances solved within the time specified in the \(y\)-coordinate. The points for our method (CSP) and the generator of Zama and Sasano (ZS) are indicated with \(+\) and \(\times\), respectively. The curve formed by the points for the same method shows an increase in the number of solved instances over time.  
Our method solved 95 of a total of 100 instances within the time limit, while the generator of Zama and Sasano solved 65 instances. The curve of our method shows a linear increase up to around 90 in the \(x\)-axis, which indicates the number of solved instances. All such instances are solved within about 1 minute. The curve grows rapidly after 90. All instances taking more than 1 min including those exceeding the time limit have 25 or less cells.  
On the other hand, the generator of Zama and Sasano can often find solutions much faster even in near 20 cells, as the curve of Zama-Sasano almost overlaps the \(x\)-axis up to near 60, which indicates the number of solved instances. The number of clue cells in such solved instances is 45 or less. After that, the performance drops significantly as the curve sharply increases. All instances with 50 or more cells cannot be solved within the time limit.  
\begin{table}
\begin{tabular}{l c c c c c c} Range of the number of clues & 20–29 & 30–39 & 40–49 & 50–59 & 60–69 & 70–79 \\ Number of input instances & 19 & 30 & 20 & 10 & 11 & 10 \\ \end{tabular}
\end{table}
Table 1: Distribution of input instances with respect to the number of clues.