Implementing “Hidden” Strategies
The two “hidden” strategies, hidden pair and hidden triple, have the same general design: first, they build lists of the cells containing each candidate number; then, they analyze the lists to see whether pairs or triples are hidden inside the lists.
As it is done for the naked strategies described in Chapter 5, you implement each hidden strategy with two functions, one applying the strategy to a unit and one executing the unit function for each row, column, and box of the Sudoku. Again, as with the naked strategies, you will find that the two general functions for pairs and triples (Listing 6-1 and 6-2) are almost identical.
Listing 6-1. hidden_pair.c
/* hidden_pair.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "hidden_pair.h"
#include "hidden_pair_unit.h"
int hidden_pair() {
#ifdef LOG_IN_OUT
printf("--- hidden_pair >>> ");
#endif
int result = FALSE;
for (int k = 0; k < 9 && !result; k++) {
if ( hidden_pair_unit("row", row[k])
|| hidden_pair_unit("column", col[k])
|| hidden_pair_unit("box", box[k])
) {
result = TRUE;
}
}
#ifdef LOG_IN_OUT
printf("<<< hidden_pair --- ");
#endif
return result;
}
Listing 6-2. hidden_triple.c
/* hidden_triple.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "hidden_triple.h"
#include "hidden_triple_unit.h"
int hidden_triple() {
#ifdef LOG_IN_OUT
printf("--- hidden_triple >>> ");
#endif
int result = FALSE;
for (int k = 0; k < 9 && !result; k++) {
if ( hidden_triple_unit("row", row[k])
|| hidden_triple_unit("column", col[k])
|| hidden_triple_unit("box", box[k])
) {
result = TRUE;
}
}
#ifdef LOG_IN_OUT
printf("<<< hidden_triple --- ");
#endif
return result;
}
The first part of hidden_pair_unit() (see Listing 6-3) builds lists of cell coordinates for each candidate number.
Listing 6-3. hidden_pair_unit.c–Part 1
/* hidden_pair_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 "hidden_pair_unit.h"
#include "remove_candidate.h"
int hidden_pair_unit(char *what, char unit[9][2]) {
#ifdef LOG_IN_OUT
printf("--- hidden_pair_unit (%s) >>> ", what);
#endif
int result = FALSE;
int n[10] = {0};
int coords[10][2][2];
for (int j1 = 0; j1 < 9; j1++) {
int kR = unit[j1][ROW];
int kC = unit[j1][COL];
char *elem = grid[kR][kC];
if (elem[0] > 1) {
for (int i = 1; i <= 9; i++) {
if (elem[i] != FALSE) {
if (n[i] < 2) {
coords[i][n[i]][ROW] = kR;
coords[i][n[i]][COL] = kC;
}
n[i]++;
} // if (elem[i]..
} // for (int i..
} // if (elem[0]..
} // for (int j1..
The array coords stores the row and column IDs of the cells that contain each candidate, while the vector n counts the cells. To make it clear, refer to the example in Figure 6-1.
Figure 6-1. Box with hidden pairs
The first cell you process is (6,3). It results in the following assignments:
coords[3][0][0] = 6;
coords[3][0][1] = 3;
n[3] = 1;
coords[5][0][0] = 6;
coords[5][0][1] = 3;
n[5] = 1;
coords[6][0][0] = 6;
coords[6][0][1] = 3;
n[6] = 1;
That is, the coordinates of (6,3) are saved for all three candidates it contains. (6,4) is skipped, and (6,5) results in the following assignments:
coords[3][1][0] = 6;
coords[3][1][1] = 5;
n[3] = 2;
coords[6][1][0] = 6;
coords[6][1][1] = 5;
n[6] = 2;
Now, when you process (7,3), things go differently.
n[3] = 3;
coords[5][1][0] = 7;
coords[5][1][1] = 3;
n[5] = 2;
n[6] = 3;
coords[8][0][0] = 7;
coords[8][0][1] = 3;
n[8] = 1;
coords only has space for the coordinates of two cells, and the candidates for 3 and 6 have already appeared twice before. Therefore, although you increment the counters of cells containing candidates for 3 and 6, you do not save the coordinates of the cells.
This happens again when you process (7,4).
n[3] = 4;
n[5] = 3;
You skip (7,5), and while processing (8,3), you make the following assignments:
n[3] = 5;
n[5] = 4;
n[6] = 4;
coords[7][0][0] = 8;
coords[7][0][1] = 3;
n[7] = 1;
coords[8][1][0] = 8;
coords[8][1][1] = 3;
n[8] = 2;
coords[9][0][0] = 8;
coords[9][0][1] = 3;
n[9] = 1;
You skip (8,4) and then complete the unit by processing (8,5).
n[3] = 6;
n[6] = 5;
coords[7][1][0] = 8;
coords[7][1][1] = 5;
n[7] = 2;
n[8] = 3;
coords[9][1][0] = 8;
coords[9][1][1] = 5;
n[9] = 2;
Figure 6-2 summarizes the end result of the assignments.
Figure 6-2. Listing cells per candidate number
Although the table shows the coordinates of two cells for all unsolved numbers, only 7 and 9 appear in two cells because only for them n equals 2 . Further, as they appear in the same two cells, they form two pairs. If they were the only two candidates in those two cells, they would be naked pairs, but as you know that (8,3) and (8,5) also contain other candidates, they are hidden pairs.
Incidentally, in this list, n cannot ever be 1 because by the time the Solver attempts to use hidden pair, unique has already removed all candidates that appear only once.
Now, you have just to see how hidden_pair_unit() arrives to the same conclusions and what happens when it does. For this, you have to refer to Listing 6-4.
Listing 6-4. hidden_pair_unit.c–Part 2
for (int i = 1; i <= 9; i++) {
if (n[i] == 2) {
int log_printed = FALSE;
for (int ii = i+1; ii <= 9; ii++) {
if (n[ii] == 2
&& coords[i][0][ROW] == coords[ii][0][ROW]
&& coords[i][0][COL] == coords[ii][0][COL]
&& coords[i][1][ROW] == coords[ii][1][ROW]
&& coords[i][1][COL] == coords[ii][1][COL]
) {
for (int kCell = 0; kCell < 2; kCell++) {
int kR = coords[i][kCell][ROW];
int kC = coords[i][kCell][COL];
char *elem = grid[kR][kC];
if (elem[0] > 2) {
result = TRUE;
#ifdef LOG_HIDDEN_PAIR
if (log_printed == FALSE && !silent) {
printf("hidden_pair_unit: %d and %d"
" are only in (%d,%d) and "
"(%d,%d) of the same %s ",
i, ii, coords[i][0][0],
coords[i][0][1],
coords[i][1][0],
coords[i][1][1], what
);
log_printed = TRUE;
}
#endif
for (int iii = 1; iii <= 9; iii++) {
if ( elem[iii] != FALSE
&& i != iii
&& ii != iii
) {
remove_candidate("hidden_pair_unit",
iii, kR, kC
);
}
}
} // if (elem[0]..
} // for (int kCell..
} // if (n[ii]..
} // for (int ii..
} // if (n[i]..
} // for (int i..
#ifdef LOG_IN_OUT
printf("<<< hidden_pair_unit (%s) --- ", what);
#endif
return result;
}
The outermost for-loop, with control variable i, goes through the numbers, and the if immediately inside the loop limits the processing to the candidate numbers that appear in exactly two cells. The for-loop with control variable ii ensures that i and ii together form all theoretically possible pairs, but, again, you only consider the iis that appear in exactly two cells. The second if does something more, though: it checks that the coordinates of the cells in which i and ii appear have identical coordinates. As a result, if the second if succeeds, you know that you have found a double pair of candidates.
The only thing that is left to do is to see whether the two cells containing your pairs also contain additional candidates, which you will then be able to remove (if they don’t, you have found a naked pair, rather than a hidden one). You do this by checking whether the elem[0] of each one of the two cells (indexed by the value of kCell) exceeds 2.
In the case of the example in Figure 6-1, it turns out that we can eliminate the candidates for 3, 5, 6, and 8 from (8,3) and the candidates for 3, 6, and 8 in (8,5). The log entries are very satisfying.
hidden_pair_unit: 7 and 9 are only in (8,3) and (8,5) of the same box
hidden_pair_unit: removed 3 from (8,3)
hidden_pair_unit: removed 5 from (8,3)
hidden_pair_unit: removed 6 from (8,3)
hidden_pair_unit: removed 8 from (8,3)
hidden_pair_unit: removed 3 from (8,5)
hidden_pair_unit: removed 6 from (8,5)
hidden_pair_unit: removed 8 from (8,5)
You have certainly noticed that, whenever you need to access the Sudoku grid, you use a variable called elem (which stands for “element”). There is actually no compelling reason for doing so. For example, you could replace the three statements in bold in Listing 6-4 with the following two:
if (grid[kR][kC][0] > 2) {
...
if (grid[kR][kC][iii] != FALSE && i != iii && ii != iii) {
But elem makes the code more readable. The same consideration applies to kR and kC, which are not absolutely necessary. Some programmers might actually find that by “hiding” grid[kR][kC] behind elem, you actually make the code less readable. Ultimately, it is just a matter of taste.
The only significant difference between hidden_triple_unit() and hidden_pair_unit() is that in hidden_triple_unit() (see Listing 6-5) you need to look for three triplets of candidates instead of two pairs.
Listing 6-5. hidden_triple_unit.c
/* hidden_triple_unit.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "hidden_triple_unit.h"
#include "remove_candidate.h"
int hidden_triple_unit(char *what, char unit[9][2]) {
#ifdef LOG_IN_OUT
printf("--- hidden_triple_unit (%s) >>> ", what);
#endif
int result = FALSE;
int n[10] = {0};
int coords[10][3][2];
for (int j1 = 0; j1 < 9; j1++) {
int kR = unit[j1][ROW];
int kC = unit[j1][COL];
char *elem = grid[kR][kC];
if (elem[0] > 1) {
for (int i = 1; i <= 9; i++) {
if (elem[i] != FALSE) {
if (n[i] < 3) {
coords[i][n[i]][ROW] = kR;
coords[i][n[i]][COL] = kC;
}
n[i]++;
} // if (elem[i]..
} // for (int i..
} // if (elem[0]..
} // for (int j1..
for (int i1 = 1; i1 <= 9; i1++) {
if (n[i1] == 3) {
int log_printed = FALSE;
for (int i2 = i1+1; i2 <= 9; i2++) {
if (
n[i2] == 3
&& coords[i1][0][ROW] == coords[i2][0][ROW]
&& coords[i1][0][COL] == coords[i2][0][COL]
&& coords[i1][1][ROW] == coords[i2][1][ROW]
&& coords[i1][1][COL] == coords[i2][1][COL]
&& coords[i1][2][ROW] == coords[i2][2][ROW]
&& coords[i1][2][COL] == coords[i2][2][COL]
) {
for (int i3 = i2+1; i3 <= 9; i3++) {
if (
n[i3] == 3
&& coords[i1][0][ROW] == coords[i3][0][ROW]
&& coords[i1][0][COL] == coords[i3][0][COL]
&& coords[i1][1][ROW] == coords[i3][1][ROW]
&& coords[i1][1][COL] == coords[i3][1][COL]
&& coords[i1][2][ROW] == coords[i3][2][ROW]
&& coords[i1][2][COL] == coords[i3][2][COL]
) {
for (int kCell = 0;
kCell < 3;
kCell++
) {
int kRow = coords[i1][kCell][ROW];
int kCol = coords[i1][kCell][COL];
char *elem = grid[kRow][kCol];
if (elem[0] > 3) {
result = TRUE;
#ifdef LOG_HIDDEN_TRIPLE
if ( log_printed == FALSE
&& !silent
) {
printf("hidden_triple_unit: %d, "
"%d, and %d are only in "
"(%d,%d), (%d,%d), and "
"(%d,%d) of the same"
"%s ", i1, i2, i3,
coords[i1][0][0],
coords[i1][0][1],
coords[i1][1][0],
coords[i1][1][1],
coords[i1][2][0],
coords[i1][2][1], what
);
log_printed = TRUE;
}
#endif
for (int ki = 1; ki <= 9; ki++) {
if ( elem[ki]
&& ki != i1
&& ki != i2
&& ki != i3
) {
remove_candidate(
"hidden_triple_unit",
ki,
kRow, kCol
);
}
}
} // if (elem[0]..
} // for (int kCell..
} // if (n[i3]..
} // for (int i3..
} // if (n[i2]..
} // for (int i2..
} // if (n[i1]..
} // for (int i1..
#ifdef LOG_IN_OUT
printf("<<< hidden_triple_unit (%s) --- ", what);
#endif
return result;
}
The first loop, where you list the cells for each number, is almost identical to the corresponding loop of hidden_pair_unit(). The only difference is that you save the coordinates of the first three cells instead of the first two.
In the second part of the function, the difference is that you have to look for all possible triples of numbers instead of all possible pairs. As a result, you need to replace the two for-loops controlled by i and ii with three loops controlled by i1, i2, and i3. This also implies that, instead of comparing the coordinates of two cells for two numbers ([i][0] with [ii][0] and [i][1] with [ii][1]), you have to compare the coordinates of three cells for three numbers ([i1][0] with [i2][0] and [i3][0]; [i1][1] with [i2][1] and [i3][1]; and [i1][2] with [i2][2] and [i3][2]).
Also, obviously, you need to expand the log entries accordingly.
Summary
In this chapter you learned how to implement the hidden strategies; in Chapter 7 you will learn another level 1 strategy: box-line.