A program able to create puzzles must first of all be able to solve them, and to grade puzzles it is necessary to have a large number of solved puzzles. Therefore, the first step is to write a sudoku solver. There are many around, but for me part of the fun is to write the program. Years ago, I already wrote at least two sudoku-solving programs in Java. They were OO programs, but I was never particularly happy with the implementation. For this latest attempt, I have decided to ditch OO and use plain old “C” as a programming language.
In this post, I will describe a strategy that I call ‘rectangle’. It is sometimes called ‘hollow rectangle’ (you will later understand why). I intend to describe the strategy and then provide some development notes. To display the examples, I shall use snapshots of the program “Sudoku Training Software 1.1”, which runs under Windows. You can freely download it by clicking here. This is the first program I found on the Web for generating the snapshots. I use it only for that and I have no idea whether its other functions are good or bad. If you would like to suggest some other application, perhaps for the Mac, please tell me.
Notation
A sudoku table consists of 81 cells arranged in a 9x9 matrix. I identify a cell through a pair of (row,column) coordinates from 0 to 8. I call a block of 3x3 cells with the top-left cell in position (0,0), (0,3), (0,6), (3,0), (3,3), (3,6), (6,0), (6,3), (6,6) a ‘square’. In summary, the indices of row, column, and square are as follows:
The numbers in the middle of the squares are the square indices (or identifiers). So, for example, square 5 consists of the cells (3,6), (3,7), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), and (5,8), which are indexed within the square in that order, from 0 to 8.
In general, the elements within a group are indexed by the numbers 0 to 8.
Example 1: element 6 of row 3 is the cell (3,6).
Example 2: element 6 of column 3 is the cell (6,3).
Example 3: element 6 of square 3 is the cell (5,0).
A ‘candidate’ is a digit between 1 and 9 that can occupy a cell. I say that a ‘candidate solves a cell’ when it is the only possible candidate for that cell.
Strategy
If the cells containing a particular candidate outline a rectangle with its vertices in four different squares, the vertices cannot contain the candidate. For example (only the 5 candidates are shown):
If (1,0) contains a 5, then (1,4) cannot. Therefore, (2,5) must. Then, in square 7 there can only be a 5 in (7,4), and in square 6 there can only be a 5 in (6,0). But, as column 0 would end up with two 5s, our premise must be wrong, and (1,0) cannot contain a 5. Similarly, (7,0) cannot contain a 5 either.
Notice that there can be many more 5 candidates but, for the strategy to apply, the candidates in the four squares containing the vertices must be on the edge of the rectangle, as highlighted in the following example:
Actually, that is not entirely true, as shown in the following example:
I have moved the candidate from (6,0) to (6,1), but the 5 candidate in (7,0) can be removed although (6,1) is inside the rectangle. However, notice that the 5 candidate in (1,0) can no longer be removed.
The following example shows that there exist some cases in which a 5 candidate can be outside the rectangle without invalidating the strategy:
The 5 candidate in (7,1) can be removed although there are nine 5 candidates outside the rectangle: (0,1), (0,5), (6,0), (6,5), (7,0), (8,0), (8,1), (8,2), and (8,5).
Program
I initially thought that I could define a sudoku table by rows, as in
char row[9][9][10];
with the first index indicating the row, the second index indicating the column, and the third index containing flags to identify the presence of or absence of candidates, using the first value (with index 0) to store the number of candidates. For example, if the cell in position (3,2) has only the candidates 3, 6, and 9, the ten values of the array row[3][2] would be 3, 0, 0, 1, 0, 0, 1, 0, 0, 1. Simple and easy.
Then, to access columns and squares with ease, I thought I could simply define the following two arrays:
char *col[9][9];
char *square[9][9];
and set them up at initialisation time. Then, for example, the list of candidates possible for the middle cell of the bottom row could be addressed in any of the following ways:
row[8][4]
col[4][8]
square[7][7]
The idea was that I could write some function operating on the nine elements of a group without caring whether it was a row, a column, or a square. A kind of poor man’s OO-inheritance for a procedural language. Unfortunately, I ran into problems when I tried to pass groups as arguments to functions. I still believe that it should have worked, but the compiler kept issuing warnings, and I always want to develop warning-free programs, unless it is really impossible. After wasting some time to find a solution, I decided to switch from pointers to indices. Obviously, being C, they are not safer than pointers, but at least I can declare rows, columns, and squares in the same way.
So, now I have:
char table[9][9][10];
char row[9][9][2];
char col[9][9][2];
char square[9][9][2];
with [9][9][0] used for the row indices and [9][9][1] used for the column indices. As a result, the initialisation of the arrays is done as follows:
for (int k = 0; k < 9; k++) {
for (int j = 0; j < 9; j++) {
table[k][j][0] = 9;
for (int i = 1; i <= 9; i++) {
table[k][j][i] = i;
}
row[k][j][0] = k;
row[k][j][1] = j;
col[j][k][0] = k;
col[j][k][1] = j;
square[k/3*3+j/3][k%3*3+j%3][0] = k;
square[k/3*3+j/3][k%3*3+j%3][1] = j;
}
}
at the beginning, once and for all.
To program the rectangle strategy, it is necessary to check all possible rectangular patterns and follow the chain around the four squares. The number of combinations of squares is limited: (0,1,4,3), (0,2,5,3), (0,1,7,6), (0,2,8,6), (1,2,5,4), (1,2,8,7), (3,4,7,6), (3,5,8,6), and (4,5,8,7). Therefore, the top strategy function can simply loop through the nine patterns and execute a function that handles an individual pattern. rectangle.c can be as simple as follows:
int result = FALSE;
int pattern[9][4] = {
{0,1,4,3}, {0,2,5,3}, {0,1,7,6},
{0,2,8,6}, {1,2,5,4}, {1,2,8,7},
{3,4,7,6}, {3,5,8,6}, {4,5,8,7}
};
for (int k = 0; k < 9; k++) {
result |= rectangle_pattern(pattern[k]);
}
A simple loop over the possible patterns. rectangle_pattern.c is in principle also quite simple:
for (int kS = 0; kS < 4; kS++) {
int seq[4];
for (int k = 0; k < 4; k++) {
int kk = (kS + k) % 4;
seq[k] = pattern[kk];
}
int sID = seq[0];
for (int kE = 0; kE < 9; kE++) {
int kR = square[sID][kE][0];
int kC = square[sID][kE][1];
if (table[kR][kC][0] > 1) {
result |= rectangle_cell(seq, kR, kC);
}
}
}
It executes rectangle_cell() for each cell of each one of the four squares of the pattern. The little for-loop with ‘k’ as control variable, ‘rotates’ the pattern, so that the squre from which we start the chain is always in the first square of the ‘seq’ list. Notice that I skip cells that have already been solved (cells with table[kR][kC][0] == 1). To speed up the process, I also check in advance (not shown) whether the pattern contains a square that has already been completely solved, in which case I simply return.
rectangle_cell() contains a loop on all candidates of the initial cell. Again, the core of the function is quite simple:
int result = FALSE;
char *elem = table[kR][kC];
for (int i = 1; i <= 9; i++) {
if (elem[i] != FALSE) {
int res = rectangle_step(seq, 0, kR, kC, i, kR, kC);
if (res == 0) {
table[kR][kC][i] = FALSE;
table[kR][kC][0]--;
if (table[kR][kC][0] == 1) {
cleanup_around(kR, kC);
}
result = TRUE;
}
}
}
The function rectangle_step() is where the real work is done, as we’ll see in a minute. It returns 0 if the chain cannot be completed because it leads to an inconsistency, a positive value if the chain could be completed, and -1 if the chain had to be aborted (e.g., because the digit has already been solved in one of the squares of the pattern). If the chain leads to an inconsistency, it means that the candidate can be removed from the initial cell. That is what we are hoping for!
cleanup_around() is a function that I execute whenever I solve a cell. It removes the candidate that solved the cell from all cells on the same row, column, and square.
The arguments of rectangle_step() are:
Sequence of squares, starting from that containing the initial cell of the chain (int seq[4])
Current square within the chain, initially 0 and then 1, 2, and 3 (int kSeq)
Coordinates of the current cell within the chain (int kR, int kC)
Candidate/digit we are looking for (int kN)
Coordinates of the initial cell of the chain (int iR, int iC)
The first thing I do in rectangle_step() is to make a list of cells of the next square which contain the digit we are after and are NOT aligned with the current cell of the chain:
int result = 0;
int kS = seq[kSeq+1];
if (kSeq == 3) {
kS = seq[0];
}
int n = 0;
int rows[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
int cols[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
for (int kE = 0; kE < 9 && result >= 0; kE++) {
int kkR = square[kS][kE][0];
int kkC = square[kS][kE][1];
char *elem = table[kkR][kkC];
if (elem[0] == 1) {
if (elem[kN] != FALSE) {
result = -1;
}
}
else if (elem[kN] != FALSE && kkR != kR && kkC != kC) {
rows[n] = kkR;
cols[n] = kkC;
n++;
}
}
Notice that at the very beginning, if the current square is the last one of the sequence, I set the next square (kS) to the initial square. Also notice that if the digit has been solved in the next square (i.e., if
elem[0] == 1
and
elem[kN] != FALSE
I abort the search by setting the result to -1.
The rest of the function is where everything happens:
if (n > 0 || kSeq == 3) {
if (kSeq < 3) {
for (int k = 0; k < n && result >= 0; k++) {
int res = rectangle_step(seq,kSeq+1,rows[k],cols[k],kN,iR,iC);
if (res < 0) {
result = res;
}
else {
result += res;
}
}
}
else { // if original cell is not in the list of possible one...
for (int k = 0; k < n && result == 0; k++) {
if (rows[k] == iR && cols[k] == iC) {
result = 1;
}
}
}
}
else if (n == 0 && result != -1) { // pointing-line
result = -1;
table[kR][kC][kN] = FALSE;
table[kR][kC][0]--;
if (table[kR][kC][0] == 1) {
cleanup_around(kR, kC);
}
}
Let’s look first at the else if at the bottom. If ‘n’ is equal to zero, it could mean that the digit we are looking for has already been solved in the next square, but this is not the case if ‘result’ is set to -1. The only possibility we are left with is if all the cells of the next square that contain the candidate we are looking for are aligned with the cell we are considering in the current square. But as each square must have every digit, it means that we can remove the candidate from the current cell. This is actually a strategy called pointing-line (or something like that). Look at following example, where only the 5 candidates are shown:
The current square is shown in yellow, and the next one in turquoise. The current cell is the one with the candidate in red. When the program scans the next square looking for candidates, it finds two 5s, but it doesn’t save them in the list of cells, because the test
kkR != kR && kkC != kC
fails. Therefore, ‘n’ remains set to zero. Clearly, (5,2) cannot contain a 5, otherwise square 4 would remain without 5s.
Now let’s see what the function does when n > 0. We examine first the case in which the next square is NOT the last one. If the loop
for (int k = 0; k < n && result == 0; k++) {
if (rows[k] == iR && cols[k] == iC) {
result = 1;
}
}
finds that that there is at least one cell, it means that the chain can continue. Therefore, we return 1. And not to the juiciest bit, when the current cell is in the last square and the the next square is the one with started the chain from:
for (int k = 0; k < n && result >= 0; k++) {
int res = rectangle_step(seq,kSeq+1,rows[k],cols[k],kN,iR,iC);
if (res < 0) {
result = res;
}
else {
result += res;
}
}
We go through the list of cells of the next square that contain our candidate and execute on them rectangle_step() recursively, taking care that kSeq is incremented. That’s it. As soon as one of the recursive calls returns a negative number, we return the same, so that the chain is aborted. Otherwise, we sum the returned values of all recursive calls and return that. The only case in which rectangle_cell() ends up with a zero and removes the original cell occurs when ALL recursive executions of rectangle_step() return 0. This means that, no matter what path you choose to chain around the four squares, you always arrive to a contradiction, which then allows you to remove the candidate from the initial cell.
What I have removed from the functions are logging messages, which I use to keep track of what the program does (as well as to check that it doesn’t screw up...)
I just love to use recursive functions. Don’t you? The only risk is to run out of stack space, either because you have underestimated the levels of recursion (but here they are only four), or you have failed to build a stop clause and the function tries to keep recurring forever.
The fact that I check for res < 0 and I always check for FALSE (i.e., 0) instead of TRUE (i.e., 1) are bits of defensive coding. The res < 0 is because one day (as unlikely as it can be) I might introduce a possible return value in addition to -1. The check for TRUE protects me from the case in which something goes astray and a variable which is supposed to be either 0 and 1 ends up being something else. It would still pass the test for TRUE. Once I even wrote a short report titled “The Third Boolean Alternative”, in which warned about using TRUE and FALSE in C as if they were truly exclusive possibilities.
OK. Let’s see a real example. I tried to use my program to solve a sudoku developed by Andrew C. Stuart that I found on the Internet. After applying the standard/simpler strategies, I got stuck. That is what motivated me to develop a function for the rectangle strategy. It is described in a PDF titled “Sudoku Creation and Grading”.
WARNING: THE FOLLOWING EXAMPLE SHOWS SOME RESULTS.
If you want to attempt to solve the sudoku, you might like to read the rest of this post later.
I have highlighted all the cells that contain 9 candidates. Do you recognise the pattern? When I executed the program, I got the following log:
rectangle_cell: 9 in (1,5) leads to contradiction when chained through the squares [1,2,8,7]
rectangle_cell: removed 9 from (1,5)
cleanup_group [row of (1,5)]: removed 6 in (1,4)
cleanup_group [row of (1,5)]: removed 6 in (1,7)
cleanup_group [column of (1,5)]: removed 6 in (6,5)
cleanup_group [column of (1,5)]: removed 6 in (7,5)
cleanup_group [square of (1,5)]: removed 6 in (0,4)
rectangle_cell: 6 cannot solve (7,7) because all the 6s in square 7
are aligned with it (pointing-line strategy)
rectangle_cell: removed 6 from (7,7)
rectangle_cell: 9 cannot solve (7,4) because all the 9s in square 1
are aligned with it (pointing-line strategy)
rectangle_cell: removed 9 from (7,4)
cleanup_group [row of (7,4)]: removed 6 in (7,0)
sudoku: the table now contains 50 solved cells
Success! The algorithm works! Well, it took me the best part of three days to get it to work correctly...
The sad story is that I still need some other sophisticated strategy for this puzzle, because with the strategies I have already implemented I haven’t managed to solve it. Here is what strategies I used (I know, I haven’t said anything about ‘unique’, ‘hidden-pair’, and ‘square-line’. Perhaps another time):
cleanup 29
loop_unique 44
hidden_pair 44
square_line 47
loop_unique 48
rectangle 50
loop_unique 53
square_line 53
I solved it by hand, but only by trying and backtracking, which is not satisfactory. The author claims that it can be solved without random choices...
No comments:
Post a Comment