Implementing “Unique”
The “unique” strategy looks for candidates that are unique within a unit. This happens when all other candidates for the same number are removed from the unit (see Figure 4-1).
Figure 4-1. “Unique” within a row
If Solver, while applying another strategy, happens to remove the candidates for 5 from cells 7 and 8 of Figure 4-1, the 5 in cell 4 becomes unique within the row and, as a result, the candidates for 4 and 8 in cell 4 can be removed.
To be consistent, the name of this strategy should have been hidden single, but I started with the name unique and then couldn’t bring myself to rename all the modules and the references to the strategy. It doesn’t really matter, though.
To implement the strategy, you need three functions that call each other: unique_loop(), unique(), and unique_unit(). The following sections go through them beginning with the innermost function.
This is where the whole work is done. It checks for unique candidates within a unit (see Listing 4-1).
Listing 4-1. unique_unit.c
/* unique_unit.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "cleanup_around.h"
#include "def.h"
#include "remove_candidate.h"
#include "unique_unit.h"
int unique_unit(char *what, char unit[9][2]) {
#ifdef LOG_IN_OUT
printf("--- unique_unit (%s) >>> ", what);
#endif
int result = FALSE;
int r[10];
for (int i = 0; i < 10; i++) { r[i] = -1; }
int c[10];
for (int j1 = 0; j1 < 9; j1++) {
int kR = unit[j1][0];
int kC = unit[j1][1];
char *elem = grid[kR][kC];
if (elem[0] > 1) {
for (int i = 1; i <= 9; i++) {
if (elem[i] != FALSE) {
if (r[i] == -1) {
r[i] = kR;
c[i] = kC;
}
else {
r[i] = -2;
}
} // if (elem[i]..
} // for (int i..
} // if (elem[0]..
} // for (int j1..
for (int i = 1; i <= 9 && !problem_found; i++) {
if (r[i] >= 0) {
result = TRUE;
int kR = r[i];
int kC = c[i];
#ifdef LOG_UNIQUE
if (!silent) {
printf("unique_unit: %d in (%d,%d) is unique"
" within the %s ", i, kR, kC, what
);
}
#endif
char *elem = grid[kR][kC];
for (int ii = 1;
ii <= 9 && !problem_found;
ii++
) {
if (elem[ii] != FALSE && i != ii) {
remove_candidate("unique_unit", ii, kR, kC);
}
}
if (!problem_found) cleanup_around(kR, kC);
} // if (r[i]..
} // for int i..
#ifdef LOG_IN_OUT
printf("<<< unique_unit (%s) --- ", what);
#endif
return result;
}
To find unique candidates, unique_unit() relies on two vectors (i.e., one-dimensional arrays): r is used to store row IDs, and c to store column IDs. Each vector contains ten elements, and the elements of the r vector are initially set to -1. In a first pass, unique_unit() goes through the cells of the unit and stores into the two vectors the coordinates of the first candidate of each number—that is, the first candidate it encounters. For example, suppose that unique_unit() is processing the box shown in Figure 4-2.
Figure 4-2. “Unique” within a box
To build up the r and c vectors, after skipping (3,0) because it is already solved and checking that the relevant elements of the r vector contain the value -1, unique_unit() processes (3,1) by doing the following:
r[1] = 3;
c[1] = 1;
r[5] = 3;
c[5] = 1;
r[7] = 3;
c[7] = 1;
unique_unit() then processes (3,2). Before saving the row and column IDs of the candidate for 1, it checks the values stored in r[1] and discovers that it is not set to -1. This means that the candidate for 1 in (3,2) is not the first one encountered in the scan. It cannot therefore be unique within the unit. unique_unit() therefore sets r[1] to -2 and proceeds to the next candidate of (3,2), which is a 3. After completing the processing of (3,2), the two vectors r and c look as follows:
0 1 2 3 4 5 6 7 8 9
r: -1 -2 -1 3 -1 -2 -1 -2 -1 -1
c: -1 1 -1 2 -1 1 -1 1 -1 -1
unique_unit() then checks (4,0), skips (4,1) and checks (4,2), (5,0), (5,1), and (5,2). At the end of the checks, r and c look as follows:
0 1 2 3 4 5 6 7 8 9
r: -1 -2 -1 -2 -1 -2 -2 -2 -2 4
c: -1 1 -1 2 -1 1 0 1 0 2
Element 0 was never meant to be set, because the Sudoku numbers are 1 to 9, and has remained untouched. It is only there to avoid having to subtract 1 when indexing the numbers 1 to 9. Elements 2 and 4 have also remained set to their initialization values of -1, because the corresponding numbers were already solved before executing unique_unit(). The row IDs of 1, 3, 5, 6, 7, and 8 were set to -2 when unique_unit() found further candidates after the first one. The corresponding column IDs were set when the first candidate was found and not changed after that. Only the element of r for the number 9 is set to a non-negative value. This is because the 9 of cell (4,2) is indeed unique within the unit.
unique_unit() in the for-loop with control variable i goes through the r vector as you have just done, and removes the candidates for 5 and 8 from (4,2).
This function (see Listing 4-2) executes unique_unit() for each row, column, and box of the whole Sudoku. As you saw in Chapter 3, the Solver restarts from level 0 strategies as soon as the application of any strategy of any higher level of difficulty removes (or solves) one (or more) candidates. But unique is a level 0 strategy. Therefore, Solver keeps attempting it as long as it produces a result. That’s why unique() applies unique_unit() to all 27 possible units (9 rows, 9 columns, and 9 boxes) and, as you will see shortly, unique_loop() keeps doing it as long as unique numbers exist.
Listing 4-2. unique.c
/* unique.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "unique.h"
#include "unique_unit.h"
int unique() {
#ifdef LOG_IN_OUT
printf("--- unique >>> ");
#endif
int result = FALSE;
for (int k = 0; k < 9; k++) {
result |= unique_unit("row", row[k]);
result |= unique_unit("column", col[k]);
result |= unique_unit("box", box[k]);
}
#ifdef LOG_IN_OUT
printf("<<< unique --- ");
#endif
return result;
}
This function (see Listing 4-3) keeps executing unique() as long as it succeeds in removing candidates.
Listing 4-3. unique_loop()
/* unique_loop.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "unique.h"
#include "unique_loop.h"
int unique_loop() {
#ifdef LOG_IN_OUT
printf("--- unique_loop >>> ");
#endif
int found;
int something = FALSE;
do {
found = unique();
something |= found;
} while (found && !problem_found);
#ifdef LOG_IN_OUT
printf("<<< unique_loop --- ");
#endif
return something;
}
Summary
In this chapter, you have learned how to implement the level 0 unique strategy. In the next chapter, I explain how to implement the “naked” strategies: “naked pair” at difficulty level 1 and “naked triple” and “naked quad” at level 2.