Implementing “XY-chain”
This strategy is an extension of Y-wing. Therefore, it is not surprising that the two strategies share a significant amount of code.
The top-level strategy function is xy_chain() (see Listing 11-1). Like y_wing(), its purpose is to provide a standard f_ptr_t interface (see def.h in Listing 3-1) to the function pairs_find() (see Listings 10-3, 10-4, 10-5, and 10-6). pairs_find() executes xy_chain_digit() (see Listing 11-2) for each candidate number, which in turn uses xy_chain_step() (see Listing 11-4) to follow the chain of cells that is at the core of the XY-chain strategy. To determine what area of the Sudoku grid is affected by two distinct cells, xy_chain_step() executes the utility function intersection() (see Listing 10-8), which calls footprint() (see Listing 10-9).
Listing 11-1. xy_chain.c
/* xy_chain.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "pairs_find.h"
#include "xy_chain.h"
int xy_chain() {
#ifdef LOG_IN_OUT
printf("--- xy_chain >>> ");
#endif
int result = pairs_find(DEF_XY_CHAIN);
#ifdef LOG_IN_OUT
printf("<<< xy_chain --- ");
#endif
return result;
}
xy_chain_digit()
The purpose of xy_chain_digit() is to start chains that begin with a particular number.
Listing 11-2. xy_chain_digit.c
/* xy_chain_digit.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "pairs_data.h"
#include "xy_chain_digit.h"
#include "xy_chain_step.h"
int xy_chain_digit(int i0) {
#ifdef LOG_IN_OUT
printf("--- xy_chain_digit (%d) >>> ", i0);
#endif
int n_found = 0;
for (int i1 = 1; i1 <= 9 && n_found == 0; i1++) {
for (int i01 = 0; i01 < n_x_pairs[i0][i1] && n_found == 0; i01++) {
// Flag x_pairs[i0][i1][ROW][i01] and x_pairs[i0][i1][COL][i01]
// to avoid using the same cell more than once within the chain
int kR01 = x_pairs[i0][i1][ROW][i01];
int kC01 = x_pairs[i0][i1][COL][i01];
x_pairs[i0][i1][ROW][i01] += 10;
x_pairs[i1][i0][ROW][i01] += 10;
// Start the chain.
{
int kB01 = x_pairs[i0][i1][BOX][i01];
chain_info_struct_t i0_info;
chain_info_struct_t i1_info;
i0_info.digit = i0;
i1_info.digit = i1;
i1_info.coords[ROW] = i0_info.coords[ROW] = kR01;
i1_info.coords[COL] = i0_info.coords[COL] = kC01;
i1_info.coords[BOX] = i0_info.coords[BOX] = kB01;
i0_info.next = &i1_info;
i1_info.next = NULL;
n_found += xy_chain_step(&i0_info, 1);
}
// Restore the grid.
x_pairs[i0][i1][ROW][i01] -= 10;
x_pairs[i1][i0][ROW][i01] -= 10;
} // for (int i01..
} // for (int i1 = 1..
#ifdef LOG_IN_OUT
printf("<<< xy_chain_digit (%d) --- ", i0);
#endif
return n_found > 0;
}
As in y_wing_digit(), the first two for-loops go in sequence through all the cells containing a naked pair that includes i0 as a candidate. After selecting the cell from which the chain is to start, xy_chain_digit() flags it as already in use by adding 10 to its row ID. This is to avoid xy_chain_step() using it again when extending the chain. The choice of the value 10 makes possible a simple check: rows with ID < 9 are free, while rows with ID > 9 are already part of the chain. As x_pairs is symmetrical, it is necessary to flag both x_pairs[i0][i1] and x_pairs[i1][i0]. Obviously, xy_chain_digit() restores the original row IDs after processing a cell, so that the same cell can be used for other chains.
To start the chain, xy_chain_digit() builds the first two links, one for each number of the first pair (for the definition of the link type, see chain_info_struct in Listing 11-3) and passes it to xy_chain_step() (see Listing 11-4).
Listing 11-3. xy_chain_step.h
/* xy_chain_step.h
*
* XY-chain strategy: moving along the chain till the end.
*
* Returns the number of candidates removed.
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#ifndef XY_CHAIN_STEP
#define XY_CHAIN_STEP
typedef struct chain_info_struct *chain_info_struct_p;
typedef struct chain_info_struct {
int number;
int coords[3];
chain_info_struct_p next;
} chain_info_struct_t;
extern int chain_length;
int xy_chain_step(chain_info_struct_p info, int depth);
#endif
The structure chain_info_struct contains a number candidate, the coordinates of the cell where the candidate is located, and a pointer to a structure of the same type (i.e., to the next link of the chain).
xy_chain_step()
This is where all the work is done. This function is quite a whopper, but I have never been in favor of breaking up a large function into separate functions unless there is a “natural” way to do it. In this case, I believe that spreading the algorithm over more than one function would be unwieldy and confusing.
Listing 11-4. xy_chain_step.c
/* xy_chain_step.c
*
* Copyright (C) 2015 Giulio Zambon - http://zambon.com.au/
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "cleanup_around.h"
#include "def.h"
#include "intersection.h"
#include "pairs_data.h"
#include "remove_candidate.h"
#include "xy_chain_step.h"
#define MAX_DEPTH 8
int chain_length;
int xy_chain_step(chain_info_struct_p info, int depth) {
#ifdef LOG_IN_OUT
printf("--- xy_chain_step (%d) >>> ", depth);
#endif
int n_found = 0;
chain_info_struct_p next = info->next;
chain_info_struct_p ix_info_p;
do {
ix_info_p = next;
next = ix_info_p->next;
} while (next != NULL);
int i0 = info->digit;
int ix = ix_info_p->digit;
for (int iy = 1; iy <= 9 && n_found == 0; iy++) {
for (int ixy = 0; ixy < n_x_pairs[ix][iy] && n_found == 0; ixy++) {
int kRxy = x_pairs[ix][iy][ROW][ixy];
if (kRxy < 9) {
int kCxy = x_pairs[ix][iy][COL][ixy];
int kBxy = x_pairs[ix][iy][BOX][ixy];
if ( kRxy == ix_info_p->coords[ROW]
|| kCxy == ix_info_p->coords[COL]
|| kBxy == ix_info_p->coords[BOX]
) {
int found_something_this_time = FALSE;
if (iy == i0 && depth > 2) {
int printed = FALSE;
void *mem_block = malloc(MAX_INTER_N * sizeof(struct rc_struct));
if (mem_block == NULL) {
printf("*** xy_chain_step: malloc failure ");
exit(EXIT_FAILURE);
}
int kR0 = info->coords[ROW];
int kC0 = info->coords[COL];
rc_p_t inter = intersection(kR0, kC0, kRxy, kCxy, mem_block);
// Check whether intersecting cells contain i0 as candidates.
rc_p_t p = inter;
rc_p_t pp = p;
while (p != NULL) {
int kR = pp->row;
int kC = pp->col;
if (kR < 9 && grid[kR][kC][i0]) {
found_something_this_time = TRUE;
n_found++;
#ifdef LOG_XY_CHAIN
if (!printed && !silent) {
printf("xy_chain_step: (%d,%d):%d", info->coords[ROW],
info->coords[COL], info->digit
);
next = info->next;
printf("%d", next->digit);
do {
chain_info_struct_p next1 = next->next;
if (next1 != NULL) {
printf(" (%d,%d):%d%d", next1->coords[ROW],
next1->coords[COL], next->digit, next1->digit
);
}
next = next1;
} while (next != NULL);
printf(" (%d,%d):%d%d ", kRxy, kCxy, ix, iy);
printf("xy_chain_step: intersection of (%d,%d) and (%d,%d):",
kR0, kC0, kRxy, kCxy
);
rc_p_t p = inter;
rc_p_t pp = p;
do {
printf(" (%d,%d)", pp->row, pp->col);
p = pp->next;
pp = p;
} while (p != NULL);
printf(" ");
printed = TRUE;
} // if (!printed..
#endif
{ // Scan the whole chain to determine its length
// and update chain_length
chain_info_struct_p info1 = info->next;
chain_length = 1;
do {
chain_length++;
chain_info_struct_p info2 = info1->next;
info1 = info2;
} while (info1 != NULL);
}
remove_candidate("xy_chain_step", i0, kR, kC);
if (grid[kR][kC][0] == 1) {
cleanup_around(kR, kC);
}
} // if (elem[i0]..
p = pp->next;
pp = p;
}
free(mem_block);
} // if (iy..
if (!found_something_this_time) {
// The chain is to be extended
x_pairs[ix][iy][ROW][ixy] += 10;
x_pairs[iy][ix][ROW][ixy] += 10;
chain_info_struct_t iy_info;
iy_info.digit = iy;
iy_info.coords[ROW] = kRxy;
iy_info.coords[COL] = kCxy;
iy_info.coords[BOX] = kBxy;
iy_info.next = NULL;
ix_info_p->next = &iy_info;
// Keep following the chain
if (depth < MAX_DEPTH) {
n_found += xy_chain_step(info, depth + 1);
}
// Clean up behind you
ix_info_p->next = NULL;
x_pairs[ix][iy][ROW][ixy] -= 10;
x_pairs[iy][ix][ROW][ixy] -= 10;
} // if (!found_something_this_time..
} // if (kRxy ==..
} // if (kRxy <..
} // for (int ixy..
} // for (int iy..
#ifdef LOG_IN_OUT
printf("<<< xy_chain_step (%d) --- ", depth);
#endif
return n_found;
}
xy_chain_step() goes through the current chain until it reaches its end and saves a pointer to the last link in ix_info_p. For convenience, it also stores the first and last numbers of the current chain, respectively, in i0 and ix. The first two for-loops go through all the pairs containing ix, whereby the if-statement immediately inside the second for-loop ensures that the cell is not one of those already included in the current chain. If the cell is still unused, xy_chain_step() saves its coordinates. At this point, xy_chain_step() has convenient access to the following information:
i0: the first number of the chain;
ix: the last number of the chain as it currently stands;
iy: a number paired with ix that could complete or extend the chain;
kRxy,kCxy,kSxy: the unit IDs of the cell with the [ix iy] pair.
The check
if ( kRxy == ix_info_p->coords[ROW]
|| kCxy == ix_info_p->coords[COL]
|| kSxy == ix_info_p->coords[BOX]
) {
ensures that the cell containing [ix iy] shares at least one unit with the last cell of the current chain—that is, that the new cell is linked to the previous one.
The next if-statement finds out whether the new number (i.e., iy) is identical to the initial one (i.e., i0) but also ensures that the current chain contains at least two cells. iy == i0 tells you that you have reached the end of the chain, but why should you check the length?
If you removed the check on the chain length, it could be that you complete the chain when depth == 2. That would mean that with the new cell, the chain would reach a length of 3. For example, the chain could consist of the cell (4,2) with the pair [3 1], (4,0) with [1 5], and (3,0) with [5 3]. It would be a Y-wing!
In fact, you could have ignored the Y-wing strategy and simply get it as a particular case of XY-chain, but many web sites talk about Y-wing. Also, the general XY-chain is more complicated to implement and more difficult to understand. Therefore, it makes sense to describe it and implement it separately.
So, you only need to change the 2 to 1 to get Y-wing handled by the XY-chain functions. In practice though, considering that Y-wing is a level 2 strategy, XY-chain is level 3, and you only attempt level 3 strategies when all level 2s have been unsuccessful, you would also need to disable Y-wing for XY-chain to take over. If you remove the check completely, it can happen that the chain only contains two cells. For example, (4,2) with [3 1] and (4,0) with [1 3]. But you already handle such occurrences with the naked pair strategy!
In any case, after the iy == i0 check, the chain is completed. However, you still need to see whether there are i0 candidates you can remove from the cells that can see both the initial cell of the chain and the cell with coordinates (kRxy,kCxy). After allocating a block of memory to store the list of cells, xy_chain_step() executes intersection(kR0, kC0, kRxy, kCxy, mem_block),where (kR0,kC0) are the coordinates of the initial cell.
You can easily follow the while-loop if you remove the part that prints the log entry.
If the iy == i0 check fails or if depth <= 2 or if the do-loop doesn’t find any i0 candidate to be removed, found_something_this_time remains set to FALSE. It means that you can attempt to extend the chain. You accomplish this by appending to the chain the cell with the [ix iy] pair and executing xy_chain_step() recursively.
The fact that you extend the chain when you encounter an instance of i0 that doesn’t result in the removal of candidates implies that pairs within the chain can contain i0 and you must not remove those cells from the chain. This explains why you have the condition that kR be less than 9 before checking whether grid[kR][kC][i0] is true. In any case, using a flagged row ID (i.e., an ID to which you added 10) to index the Sudoku grid would lead to unpredictable results.
You have probably noticed that xy_chain_step() only calls itself recursively up to eight times. The longer the chain, the higher the risk of running out of memory, and, in any case, it seems unreasonable to look for chains containing more than nine cells.
The following is an example of a log entry with the longest possible chain:
xy_chain_step: (4,2):13 (3,0):35 (3,6):58 (3,2):84 (5,1):49 (7,1):94 (7,5):47 (2,5):75 (2,1):51
xy_chain_step: intersection of (4,2) and (2,1): (0,2) (1,2) (2,2) (3,1) (4,1) (5,1)
xy_chain_step: removed 1 from (2,2)
As usual, let’s look at an example in some detail.
An Example
Figure 11-1 shows a short chain for the number 9 that begins in (8,1) and ends in (0,0). It allows you to remove the candidates for 9 in (1,1), (6,0), and (8,1) because they are visible by the 9s at both ends of the chain.
If you add to pairs_find.c the code shown in Listing 11-5 (it is already in the source file but commented out), you obtain the list of pairs reproduced in Listing 11-6.
Figure 11-1. An example for XY-chain
Listing 11-5. pairs_find()–Displaying the List of Pairs
for (int i1 = 1; i1 <= 9; i1++) {
if (n_x_pairs[i1][0] > 0) {
printf(" total #pairs for %d: %d ", i1,
n_x_pairs[i1][0]
);
}
for (int i2 = 1; i2 <= 9; i2++) {
if (n_x_pairs[i1][i2] > 0) {
printf("%d %d [%d]:", i1, i2,
n_x_pairs[i1][i2]
);
for (int kkk = 0;
kkk < n_x_pairs[i1][i2];
kkk++
) {
printf(" (%d,%d)", x_pairs[i1][i2][0][kkk],
x_pairs[i1][i2][1][kkk]
);
}
printf(" ");
}
}
}
Listing 11-6. pairs_find()–Example of List of Pairs
total #pairs for 1: 3
1 5 [2]: (0,1) (2,2)
1 9 [1]: (8,1)
total #pairs for 2: 3
2 7 [2]: (4,0) (4,2)
2 9 [1]: (1,1)
total #pairs for 3: 2
3 9 [2]: (2,7) (8,7)
total #pairs for 4: 7
4 5 [1]: (0,8)
4 7 [2]: (7,2) (7,6)
4 8 [1]: (6,8)
4 9 [3]: (0,0) (1,5) (2,5)
total #pairs for 5: 3
5 1 [2]: (0,1) (2,2)
5 4 [1]: (0,8)
total #pairs for 7: 4
7 2 [2]: (4,0) (4,2)
7 4 [2]: (7,2) (7,6)
total #pairs for 8: 1
8 4 [1]: (6,8)
total #pairs for 9: 7
9 1 [1]: (8,1)
9 2 [1]: (1,1)
9 3 [2]: (2,7) (8,7)
9 4 [3]: (0,0) (1,5) (2,5)
After trying the numbers from 1 to 8 without result, pairs_find() executes xy_chain_digit() for the number 9. xy_chain_digit() starts from the pair [9 1] in the cell (8,1), builds the linked chain {9,(8,1)} -> {1,(8,1)} -> NULL, and passes it to xy_chain_step() with depth set to 1.
Depth 1: xy_chain_step() tries with the first two for-loops to find a [1 iy] pair, and only succeeds when iy == 5. The [1 5] found is in (0,1). It adds the new cell to the chain to make {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> NULL and executes itself recursively with depth set to 2.
Depth 2: The first two for-loops of xy_chain_step(), looking for a [5 iy] pair, find at once the [5 1] pair in (0,1), which the previous execution of xy_chain_step() had changed to(10,1), and discards it because its row ID (i.e., kRxy) is greater than 9. It then finds another [5 1] pair in (2,2). This time, xy_chain_step() accepts the pair and adds it to the chain, to form {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> {1,(2,2)} -> NULL. After that, it calls itself recursively with depth set to 3.
Depth 3: The first two for-loops of xy_chain_step(), looking for a [1 iy] pair, find that all three pairs containing a 1 have been already taken (i.e., their cells have the row ID greater than 9) . Therefore, it returns 0.
Depth 2: xy_chain_step() removes the last cell of the chain by executing
ix_info_p->next = NULL;
x_pairs[ix][iy][ROW][ixy] -= 10;
x_pairs[iy][ix][ROW][ixy] -= 10;
By doing so, it restores the chain to what it was when it started execution: {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> NULL. Back to the second for-loop statement, it turns out that both [5 1] pairs have been tried. The loop falls through and control passes to the first for-loop, which sets iy first to 2 and then to 3. In neither case can the second for-loop find a pair. But when the first for-loop sets iy to 4, the second loop finds a [5 4] pair in (0,8). As the new cell shares a unit with (0,1), xy_chain_step() adds it to the chain to form {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> {4,(0,8)} -> NULL and executes itself recursively with depth set to 3.
Depth 3: The first two for-loops of xy_chain_step(), looking for a [4 iy] pair, find the [5 4] in (0,8), but it has already been taken. Then, they find [4 7] in (7,2) and in (7,6), but they are discarded because they don’t share any unit with (0,8). The next pair, [4 8] in (6,8) passes all the checks. Therefore xy_chain_step() adds it to the chain to form {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> {4,(0,8)} -> {8,(6,8)} -> NULL and executes itself recursively with depth set to 4.
Depth 4: The first two for-loops of xy_chain_step() discover that there is only one [8 iy] pair that, obviously, has already been taken. I say “obviously” because we execute xy_chain_step() only after finding a number in a pair. Now, if that number only appears in a single pair, that pair is what took us to xy_chain_step() in the first place, and must therefore already been taken. With nothing to do, xy_chain_step() returns 0.
Depth 3: xy_chain_step() restores the chain to {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> {4,(0,8)} -> NULL before looking for further [4 iy] pairs. It finds [4 9] in (0,0). As iy == i0 and depth > 2, xy_chain_step() executes intersection(8,1,0,0,mem_block), which returns the following list of cells: (0,1), (1,1), (2,1), (6,0), (7,0), and (8,0). Three of those cells contain candidates for 9 to be removed: (1,1), (6,0), and (8,0). The generated log entry is as follows:
xy_chain_step: (8,1):91 (0,1):15 (0,8):54 (0,0):49
xy_chain_step: intersection of (8,1) and (0,0): (0,1) (1,1) (2,1) (6,0) (7,0) (8,0)
xy_chain_step: removed 9 from (1,1)
cleanup_unit [row of (1,1)]: removed 2 from (1,2)
cleanup_unit [column of (1,1)]: removed 2 from (6,1)
xy_chain_step: removed 9 from (6,0)
xy_chain_step: removed 9 from (8,0)
xy_chain_step() restores the chain to {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> {4,(0,8)} -> NULL before looking for further pairs and numbers, but this time n_found == 3. Therefore, xy_chain_step() leaves the first two for-loops and returns 3. Actually, to be precise, the second for-loops exits because there are no further [4 9] pairs, and the first for-loop exits because 9 is the last number available. But the condition n_found == 0 is in both loops to terminate them when candidates are removed, regardless of the number or whether there are still available pairs.
Depth 2: xy_chain_step() restores the chain to {9,(8,1)} -> {1,(8,1)} -> {5,(0,1)} -> NULL and returns 3.
Depth 1: xy_chain_step() restores the chain to {9,(8,1)} -> {1,(8,1)} -> NULL and returns 3.
Depth 0: xy_chain_digit() removes the flags from the last two cells in x_pairs with
x_pairs[i0][i1][ROW][i01] -= 10; // i.e., x_pairs[9][1][ROW][0] -= 10;
x_pairs[i1][i0][ROW][i01] -= 10; // i.e., x_pairs[1][9][ROW][0] -= 10;
before returning TRUE.
pairs_find() exits the number-loop because 9 is the last number, but it would have done the same with any other number, because it only keeps going as long as result is FALSE. After exiting the loop, it frees the allocated memory and returns TRUE.
Summary
Once you have learned how to implement XY-chain, discussed in this chapter, Chapter 12 will present no problems. You will learn the last strategy that Solver implements: the level 3 “rectangle.”