Implementing “Box-Line”
As with most strategies, you implement “box-line” with two functions: one general that conforms to the type f_ptr_t as defined in def.h and one to handle an individual unit. The general function, box_line() (see Listing 7-1), executes box_line_unit() (see Listings 7-2 and 7-3) for each possible row and column of the Sudoku.
box_line()
box_line() is pretty obvious, but notice that it passes a flag to box_line_unit()to distinguish between rows and columns. It is actually not strictly necessary, but it makes the log entries clearer.
Listing 7-1. box_line.c
/* box_line.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "box_line.h"
#include "box_line_unit.h"
#include "def.h"
int box_line() {
#ifdef LOG_IN_OUT
printf("--- box_line >>> ");
#endif
int result = FALSE;
for (int k = 0; k < 9 && !result; k++) {
if (box_line_unit(ROW, row[k]) || box_line_unit(COL, col[k])) {
result = TRUE;
}
}
#ifdef LOG_IN_OUT
printf("<<< box_line --- ");
#endif
return result;
}
box_line_unit(), again, like with many other strategies, consists of two for-loops: one to collect information (see Listing 7-2) and one to do the analysis (see Listing 7-3).
Listing 7-2. box_line_unit.c–Part 1
/* box_line_unit.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "box_line_unit.h"
#include "cleanup_around.h"
#include "def.h"
#include "remove_candidate.h"
int box_line_unit(int row_col, char line[9][2]) {
#ifdef LOG_IN_OUT
printf("--- box_line_unit (%s) >>> ", unit_names[row_col]);
#endif
int result = FALSE;
int b[10]; for (int i = 0; i < 10; i++) { b[i] = -1; }
int rc[10];
for (int j1 = 0; j1 < 9; j1++) {
int kR = line[j1][ROW];
int kC = line[j1][COL];
char *elem = grid[kR][kC];
if (elem[0] > 1) {
for (int i = 1; i <= 9; i++) {
if (elem[i] != FALSE) {
int kB = kR/3*3 + kC/3;
if (b[i] == -1) {
b[i] = kB;
rc[i] = (row_col == ROW) ? kR : kC;
}
else if (b[i] != kB) {
b[i] = -2;
}
} // if (elem[i]..
} // for (int i..
} // if (elem[0]..
} // for (int j1..
You collect the information in two vectors that have one element per number candidate: b, initialized to -1, stores the box ID in which each candidate is found. rc stores the cell index of the candidate within the line—that is, the column ID if the unit is a row or the row ID if the unit is a column. As usual, to follow the algorithm, look at the example in Figure 7-1.
Figure 7-1. An example for box-line
If you consider row 3, you will see that all candidates for 3 are in box 4. Therefore, as row 3 must include the number 3, it means that all three other candidates for 3 in box 4 (i.e., in the cells (4,3), (4,4), and (4,5)) can be removed.
When the big for-loop in Listing 7-2 executes, it goes through all the cells of row 3. After ignoring the first four cells because they are solved, it reaches (3,4). Then, after checking for each number candidate that the corresponding element of b is still set to -1, it makes the following assignments, two for each candidate found in cell (3,4):
b[1] = 4; // the box ID
rc[1] = 4; // the column ID
b[3] = 4;
rc[3] = 4;
b[6] = 4;
rc[6] = 4;
When (3,5) is processed, the two vectors remain unchanged because, although the elements of b corresponding to the three numbers are no longer set to -1, they contain the same box ID of the previously processed cell (3,4).
But when you process (3,6), the box ID is 5—that is, different from that stored in b[1] and b[6] for the numbers 1 and 6 found in (3,6). Therefore, b[1] and b[6] are set to -2.
You ignore (3,7) and (3,8) because they are already solved.
At the end of the scan, the two vectors for row 3 look as follows:
0 1 2 3 4 5 6 7 8 9
b: -1 -2 -1 4 -1 -1 -2 -1 -1 -1
rc: -1 4 -1 4 -1 -1 4 -1 -1 -1
You can see that only the element of b associated with number 3 is non-negative. A similar thing happens when box_line() scans column 8.
0 1 2 3 4 5 6 7 8 9
b: -1 -2 5 -2 -1 -1 -2 -1 -1 -1
rc: -1 1 4 0 -1 -1 0 -1 -1 -1
In this case, the non-negative element of b is that associated with number 2. Note that there can be more than one number in a line that has a non-negative element in b. For example, if no candidate for 3 had been present in (4,8), b[3] would have remained set to 2 instead of being overwritten with a -2. But this scan does not take place because box_line() returns after the previous scan results in the removal of 3s in (4,3), (4,4), and (4,5).
Listing 7-3. box_line_unit.c–Part 2
for (int i = 1; i <= 9; i++) {
if (b[i] >= 0) {
int log_printed = FALSE;
int kB = b[i];
int kL = rc[i];
for (int kE = 0; kE < 9; kE++) {
int kR = box[kB][kE][ROW];
int kC = box[kB][kE][COL];
int kRC = (row_col == ROW) ? kR : kC;
if (kRC != kL) {
char *elem = grid[kR][kC];
if (elem[i] != FALSE) {
result = TRUE;
#ifdef LOG_BOX_LINE
if (!log_printed && !silent) {
printf("box_line_unit: all candidates "
"for %d of %s %d are in box %d "
, i, unit_names[row_col], kL, kB
);
log_printed = TRUE;
}
#endif
remove_candidate("box_line_unit",
i, kR, kC
);
if (grid[kR][kC][0] == 1) {
cleanup_around(kR, kC);
}
} // if (elem[i]..
} // if (kRC..
} // for (int kE..
} // if (b[i]..
} // for (int i..
#ifdef LOG_IN_OUT
printf("<<< box_line_unit (%s) --- ",
unit_names[row_col]
);
#endif
return result;
}
When the big for-loop in Listing 7-3 executes, you ignore all elements of b with the exception of those greater than or equal to zero. You then go through all the elements of the box with ID given by b[i] and remove all the candidates for i that have a column ID (or a row ID) different from that saved in rc[i].
In the example, the execution of box_line() results in the following log entries:
box_line_unit: all candidates for 3 of row 3 are in box 4
box_line_unit: removed 3 from (4,3)
box_line_unit: removed 3 from (4,4)
box_line_unit: removed 3 from (4,5)
followed by:
box_line_unit: all candidates for 2 of column 8 are in box 5
box_line_unit: removed 2 from (4,7)
box_line_unit: removed 2 from (5,7)
when box_line() successfully executes a second time after the unique, naked pair, and hidden pair strategies fail to remove any candidate.
Summary
This chapter explained how you can implement box-line. Chapter 8 describes the implementation of a similar strategy: pointing line, which is the last of the level 1 strategies.