The purpose of this book is to teach you how to write computer programs to solve and generate Sudoku puzzles. This chapter introduces you to the Solver and the Generator programs and describes the notation I use throughout the book for Sudoku puzzles and how I represent Sudoku grids in C.

Solving a Puzzle

Each blank cell in a Sudoku puzzle offers nine possible candidates. You solve a Sudoku by applying a series of strategies that let you remove candidates from the puzzle’s cells. The solution is complete when only one candidate remains in each cell.

Some strategies are simple. Perhaps the simplest one of all is that once you have solved one cell with a particular number, you can safely remove that number from all other cells that belong to the same row because you know that each number between 1 and 9 can only appear once in each row.

Other strategies are significantly more complex. Your ability to recognize the patterns that let you apply difficult strategies is what makes you an accomplished Sudoku solver.

I just searched the Web for “sudoku strategy” (without double quotes) and Google returned about 3,350,000 links. How many strategies are there? Many, but some of them are so difficult that no unaided human mind would probably be able to apply them. Also, beyond a certain level of complexity, the distinction between a “logical” strategy and a “trial and error” strategy becomes blurred.

In this book, I describe the 15 strategies that I believe an extremely capable human solver might be able to use with only the help of pencil and paper. To be honest, I doubt that I would be able to apply them all. But then, that’s just me.

The Solver implements all 15 strategies.

Some of the strategies belong to “families” of strategies. That is, they are conceptually identical but apply to increasing numbers of candidates in cells, numbers of rows, or other quantities. Once you have familiarized yourself with the code, you should be able to extend the Solver by adding more complex strategies to one or more of the “families.”

If the Solver runs out of strategies before completing the solution, it uses a 16th strategy, “backtracking,” which is an elegant name for “trial and error,” also called “brute force.” Thanks to backtracking, the Solver is guaranteed to solve any puzzle.

Generating a Puzzle

When generating a Sudoku puzzle, you must satisfy two criteria: it must be solvable and the solution must be unique.

The first criterion requires some qualifications, as the term “solvable” is too broad.

Obviously, you can solve any valid puzzle (i.e., without internal inconsistencies) by trial and error, but the key question is, which puzzles require it? The better you are at solving Sudoku, the fewer are the puzzles that force you to guess.

In the section “Solving a Puzzle,” I stated that there are 15 strategies that, in my opinion, an expert player can possibly be able to apply. It therefore makes sense to define as solvable, or, more precisely, “analytically solvable,” all and only the puzzles that the Solver program can complete without resorting to backtracking.

The second criterion, uniqueness is pretty obvious: if you generate a puzzle and provide its solution, you don’t want anybody to come up with a different one.

To generate a puzzle, the Generator starts by filling up a 9 x 9 Sudoku grid with random numbers in such a way that no number appears twice in any row, column, or box.

It then proceeds to remove clues (i.e., clear cells) according to your preferences (see below) and checks that the puzzle, using the remaining clues, admits a unique solution.

When executing the Generator, you can decide how many clues you want to remove (or eliminate as many as possible). You can also choose to remove clues individually or, to generate pleasingly symmetrical puzzles, two or four at a time.

For simplicity, the Generator uses brute-force approaches whenever possible. For example, to fill in the initial grid, which represents the solved puzzle, it just inserts one random number (1 to 9) at a time and keeps trying until it finds a valid combination.

It would have been possible to optimize the choices and obtain a valid grid more efficiently, but why bother? To save a fraction of a second in computing time?

After completing the removal of the clues, the Generator checks the uniqueness of the solution (see Chapter 15 for a detailed explanation of how to do that).

What the Generator doesn’t do is determine how difficult the new puzzle is. For that, you need to run the puzzle through the Solver. There is another way of applying a brute-force approach: generate hundreds or thousands of puzzles and then run the Solver “in batch” to measure their difficulties.

Modeling the Puzzle

A Sudoku puzzle is a partially filled grid of 9 x 9 cells. Therefore, the obvious way of representing it is to define a matrix of nine rows by nine columns, as in

char grid[9][9];

Figure 1-1 shows how you identify each cell with a pair of numbers indicating row and column. As in C, the indices start with zero, so grid[3][6], as an example, refers to the seventh cell of the fourth row.

You might wonder why, when defining cells, I use the type char instead of int. After all, we are talking about integer numbers, aren’t we? It is true, but the type char is stored in a single byte, consisting of eight bits. This is more than enough to contain the 1 to 9 Sudoku numbers, which only require four bits, and I have learned that being economical often leads to better programs.

Usually, there is a trade-off between memory and speed. It could be that defining everything of type int would result in slightly faster processing, but, in practical terms, it would also probably be irrelevant, as we are talking anyway about a small amount of data. On the other hand, arrays of characters have the advantage that you can initialize them more easily. It’s almost a matter of taste more than of anything else.

Anyhow, the simple grid with one character per cell will not do. The reason is that a Sudoku cell contains a single number only when you have solved it. In general, while you are in the middle of solving the puzzle, each cell contains a number of candidates. This means that a Sudoku program must be able to store more than one number in each cell. Figure 1-2 shows an example of a partially solved Sudoku with all its candidates.

For example, cell (7,7) has four candidates: 5, 6, 7, and 9. The maximum number of candidates, as unlikely as it can be, is nine, when you have no clue at all about the number that solves the cell.

The simplest solution to keep track of the candidates is to replace a single character with an array of characters, as in

char grid[9][9][10]

There are many ways in which you could use an array to memorize what candidates are present. I have chosen to use each element of the array as a flag, with 1 meaning that the candidate is present and 0 that the candidate is not present. For example, assuming that you already have initialized the array to all zeroes, to memorize the two candidates of cell (7,4), you could write the following two lines of code:

grid[7][4][6] = 1;
grid[7][4][9] = 1;

Additionally, I decided to use the first element (i.e., the 0th) of the array to store the number of candidates in the cell. You would do this with the following assignment statement:

grid[7][4][0] = 2;

I could have used the array as a list of candidates rather than a list of flags in fixed positions. If I had done so, you would record the two candidates as follows:

grid[7][4][1] = 6;
grid[7][4][2] = 9;

There is nothing wrong with that, but it would force you to compact the list every time a strategy removes candidates. For example, for a cell containing the candidates 3, 5, 7, and 9, the array would contain 4, 3, 5, 7, 9 in its first five elements, where the 4 in first position tells you the number of valid numbers that follow. If you then needed to remove, say, the 5, you would have to change the array to 3, 3, 7, 9. It means that you would have to copy the third number to the second position and then the fourth number to the third position. Not elegant.

But there is also another reason for using flags. With flags, if you need to check for the presence of a candidate in a cell, you only need to see whether the corresponding flag is set. For example, in the statement

 if (grid[r][c][5]) { },

the block following the if condition only executes if the 5 is a valid candidate for the cell in row r and column c. Quite neat! Remember that in C, any integer different from zero is considered to be true. With the list-based solution, you would have to scan the list every time.

You could use a bit instead of a character, but this would force you to use bit operations, which are less readable. Moreover, you would no longer have the possibility of using the 0th element to count the candidates. The candidate counter is very useful to check whether a cell has been solved or not: you only need to check whether grid[r][c][0] is set to 1.

So far so good, but you are not yet done with defining your Sudoku grid. The reason is that in Sudoku there are three types of groups of cells that you must consider: rows, columns, and 3 x 3 boxes. They are generically referred to as units. To make the programming of solving strategies easier, you need to be able to identify a generic unit, so that you can use a single function to operate indifferently on a row, on a column, or on a box. In other words, it would be a badly designed piece of software if you had to develop three separate functions to check whether a candidate of a cell is unique within its row, its column, or its box.

Before I explain how you can resolve that issue, though, it is appropriate that you are 100% clear on how you identify the boxes. For that, please refer to Figure 1-3.

As you can see, you identify the boxes with numbers between 0 and 8, like you do with rows and columns. So, for example, the cell (3,5) belongs to box 4. Sometimes, in the course of this book, I will identify a cell with three coordinates (row,column,box) instead of only two (row,column). Obviously, the third coordinate is redundant and you could easily calculate it from the first two, but additional information (as long as it is consistent with the rest!) sometimes makes things more clear.

Here is how you calculate the box ID of a cell for which you know the row and column:

box = row / 3 * 3 + column / 3;

This calculation takes advantage of the fact that in C, when you divide an integer by another integer, the result is truncated (not rounded) to an integer value. So, for example, the box ID of the cell (7,2) is calculated as 7/3*3 + 2/3 = 2*3 + 0 = 6.

To avoid having to develop unit-specific code, you can use arrays to index the Sudoku grid, as shown in Listing 1-1.

Listing 1-1. Indices of Rows, Columns, and Boxes

char grid[9][9][10];
char row[9][9][2];
char col[9][9][2];
char box[9][9][2];
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      row[k][j][0] = k;
      row[k][j][1] = j;
      col[j][k][0] = k;
      col[j][k][1] = j;
      box[k/3*3+j/3][k%3*3+j%3][0] = k;
      box[k/3*3+j/3][k%3*3+j%3][1] = j;
      }
    }

To understand how it works, concentrate first of all of the lines highlighted in bold, which refer to the rows. The outermost loop, with control variable k, goes through all the rows, while the innermost loop, with control variable j, goes through the columns (i.e., the cells) of the current row. The statements row[k][j][0] = k and row[k][j][1] = j will save the row and column ID of the cell (k,j) in the row array. It means that the jth element of row k identifies the cell with coordinates (k,j). Now, this will probably seem trivial and useless: why should you use the two elements of row[k][j] to affirm that the coordinates of the cell are indeed (k,j)? If you only had rows, you would be right. But look at what happens when you examine the column-related statements. This time, the row ID (i.e., k) is stored in col[j][k][0], while the column ID (i.e., j) is stored in col[j][k][1]. That is, the indices in the matrix col are swapped compared to those we used for the matrix row. In plain language, this means that the kth element of column j is the cell with coordinates (k,j).

Perhaps you find the use of k and j confusing. But this code lets us treat a row and a column the same way, without even knowing whether you are dealing with a row or with a column. To see how this works, let’s look at an example. Suppose that you want to check whether number x has been found within a particular row. I know, it is not an exciting example, but it will serve our purpose. To do the check, you could create a function called x_found(), as shown in Listing 1-2.

Listing 1-2. Example: x_found()

int x_found(int x, char unit[9][2]) {
  int result = 0;
  for (int i = 0; i < 9 && !result; i++) {
    int iR = unit[i][0];
    int iC = unit[i][1];
    char *cands = grid[iR][iC];
    result = cands[0] && cands[x];
    }
  return result;
  }

To find out whether, say, the number 5 has been found in row 3, you would then execute the function x_found() as follows:

int yes = x_found(5, row[3]);

The code of the function is pretty straightforward: you loop through all the elements of the row (control variable i), determine the row and column and use those values to access the corresponding element of the grid. If the number of candidates is 1 and the flag for x (i.e., 5 in the example) is set, it means that the number has been found. At that point, you break out of the loop and return to the calling function.

Now, what if you want to check column 6 instead of row 3? Easy: you just execute the following:

int yes = x_found(5, col[6]);

The function also works with boxes. If you go back to Listing 1-1, you see that as you go through all the cells of a box, from left to right and from top to bottom, the second index of the matrix box goes from 0 to 8. Let’s look, for example, at box 5. It consists of the cells (3,6), (3,7), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), and (5,8). If you calculate the second index of the matrix box, you obtain the following:

Therefore, to check whether, say, digit 7 has been found in box 4, you can execute the following:

int yes = x_found(7, box[4]);

Now, if you are familiar with C, you will be probably asking yourself why I didn’t use pointers. For example, I could have defined the following arrays:

char row[9][9][10];
char *col[9][9];
char *box[9][9];

and then initialized col and box with the addresses of the appropriate elements of the row. Initially I actually did it like that, but I couldn’t get it to work properly, because the compiler treated, say, row[3] and col[6] differently when I passed them to a function. I kept getting compile-time warnings, and I want my code to be warning free. If you find a way to do it without getting warnings, please let me know!

You might argue that C++ could have made it simpler to define Sudoku puzzles. You could have defined Row, Column, and Box as subclasses of a Unit class. It is true, but I also wanted to write a book that people without extensive knowledge of programming would be able to fully understand. Unfortunately, as schools are still in the process of introducing computing as a core subject, most people have some difficulties in getting around OO concepts (despite the fact that OO programming more closely reflects how we think). Plain C, given its availability and its widespread use, was the most appropriate choice.

Summary

In this chapter, I introduced you to the Solver and the Generator and described how to identify the rows, columns, and boxes of a Sudoku puzzle. I also explained how you can represent a Sudoku in C and warned about alternative solutions that would cause problems. In the next chapter, I describe all the strategies used by the Sudoku Solver.