The Solver program accepts a Sudoku string as an argument. This is OK when you want to solve a few Sudokus, but it is completely inadequate when you want to obtain statistical data on solving puzzles. For that, you need to be able to solve thousands of puzzles one after the other. The obvious solution is to store Sudoku strings in a file and let the Solver load them one at a time. You do it by adding the following define to the beginning of sudoku_solver.c  (see Listing 3-2, Listing 3-3, Listing 3-4, and Listing 3-5): #define USE_FILES. Then insert the code shown in Listing 14-1 immediately after checking the consistency of the strategy arrays (you can find  the code for this book in the Source Code/Download area of the Apress web site (www.apress.com)).

Listing 14-1. sudoku_solver.c–Reading Puzzles from a File

#ifdef USE_FILES

  char *infile = "puzzles.txt";
  char *outfile = "solutions.txt";
  FILE *fpr = fopen(infile, "r");
  FILE *fpw = fopen(outfile, "a");
  if (fpr == NULL) {
    printf("File "%s" failed to open
", infile);
    }
  else if (fpw == NULL) {
    printf("File "%s" failed to open
", outfile);
    }
  else {
    silent = TRUE;

    // Keep reading from file until you reach the EOF
    int n_lines = 0;
    int n_hints = 0;
    while (!feof(fpr) && n_hints >= 0) {
      char line[100];  // 90 would be enough, but...
      line[0] = '';
      (void)fgets(line, 99, fpr);
      if (line != NULL && strlen(line) > 80) {
        char sudoku_s[82];
        int seed;
        n_hints = -1;
        sscanf(line, "%s	%d	%d", sudoku_s, &seed, &n_hints);
        if (n_hints > 0) {
          fprintf(fpw, "%s	%d	%d", sudoku_s, seed, n_hints);
          init(sudoku_s);
          cleanup();
          solve();
          if (count_solved() < 81) {
            backtracking = TRUE;
            backtrack(0);
            backtracking = FALSE;
            }
          printf("%d
", n_lines);
          fprintf(fpw, "	%s	%d	%d",
             inconsistent_grid() ? "inconsistent" : "consistent",
             count_solved(),
             n_strats_used
             );
          for (int k = 0; k < n_strats_used; k++) {
            fprintf(fpw, "	%d", strats_used[k]);
            }
          fprintf(fpw, "
");
          n_lines++;
          } // if (n_hints..
        } // if (line..
      } // while (TRUE..
    } // if (fpr .. else ..
  if (fpr != NULL) fclose(fpr);
  if (fpw != NULL) fclose(fpw);

#else

Obviously, you also need to insert #endif before the return statement at the end of the module.

As you can see from the code, the Solver reads Sudoku strings from a file named puzzles.txt until it hits an EOF marker and writes lines of summary results in a file named solutions.txt.

You keep the code simple by doing the following: hard-code the file names rather than obtaining them from arguments; accept input lines with a fixed, TAB-separated format consisting of the Sudoku string, an identifier, and the number of clues in the puzzle; and, finally, perform only very basic checks on the validity of the input.

Before solving the puzzles, the Solver sets the silent flag to TRUE to suppress the log entries normally displayed. Instead, the Solver displays the puzzle identifier. By reducing the display to the bare minimum, you ensure that the execution proceeds as quickly as possible.

Following is an example of an output line:

200080010001902000450061020004000089060070000710000060040107008000009500070020034       116
        29       consistent     81      4       0       10      12      31

It starts with the information obtained from the input file (Sudoku string of the puzzle, identifier, and number of initial clues) and continues with either “consistent” or “inconsistent” (which you will never see with puzzles that the Generator program, described in Chapter 15, creates), the number of cells solved (not surprisingly, always 81, because backtrack() takes over when solve() fails), the number of strategies used (four in the example), and the list of strategies (0: unique; 10 = first strategy of level 1: naked pair, 12 = third of level 1 = box-line, and 31 = second of level 3 = XY-chain; backtrack, when used, is indicated with 40 + the maximum depth reached).

The Example of Minimum Sudokus

Minimum Sudokus are those with 17 clues. Nobody has mathematically proven that puzzles with 16 clues or less are impossible, but neither has anybody been able to find any of them. You can download the strings of 49,151 minimum Sudokus from http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php.

To solve them as a block with the Solver, you need first to append to each line an identifier and the number of clues. You can do this easily by loading the list into a spreadsheet program, adding a column with a sequence number, and adding a second column with 17. Then, all you need to do is save the workbook as a tab-separated text file named puzzles.txt.

Figure 14-1 shows what you obtain when you plot the number of puzzles vs. the number of strategies needed to solve them.

As you can see from Figure 14-1, you can solve the vast majority of puzzles that don’t require backtracking with five strategies or less. The actual figures are: 34,910 out of 47,233, or almost 3/4. Surprisingly, you can solve many fewer puzzles with two strategies (943) than with three (5,216). Note that this doesn’t depend at all on the type of strategies, as the number includes them all with the exception of cleanup and naked single.

This anomaly could be due to the fact that unique-loop, as the only strategy of level 0 being logged, distorts the result, even if it is not clear at all why it should be so. Call it a hunch! To check whether this is the case, you only need to duplicate the same statistic but ignoring unique-loop. If you do so, you obtain the “good behaved” distribution shown in Figure 14-2, thereby confirming the special role of unique-loop among the strategies.

The number of puzzles rapidly decreases with the number of strategies needed to solve them. Any further analysis would be far beyond the scope of this book. I can tell you that the decrease is fast!

Figure 14-3 shows what you obtain when you plot the number of puzzles vs. the highest level of difficulty of the strategies needed to solve them.

Level 2 strategies occurred as the most difficult strategies to solve the puzzles fewer times than the strategies of any other level. But irregularities in the distribution of strategy types should not surprise you, because the classification of strategies is purely based on my perception of their difficulties for human solvers.

Table 14-1 shows how many times the Solver used any particular strategy.

Naked quad never occurred, and lines-4, naked triple, and hidden triple were very rarely needed. The five most “useful” strategies turn out to be unique-loop, naked pair, box-line, hidden pair, and rectangle. But remember that this statistic applies to a very special category of puzzles: those with 17 clues. It could look substantially different with other selections of puzzles. In particular, it will be interesting to see what strategies are needed to solve the puzzles created with the Generator, described in Chapter 15.

Summary

In this chapter, you have learned how you can use the Solver to work on thousands of puzzles, and you’ve seen how a simple statistical analysis of the results can be intriguing. This concludes the part of this book dedicated to solving puzzles. In Chapter 15, you will start learning how to generate Sudokus, a challenge not to be underestimated.