Sudoku - Programming the XY-chain strategy

XY-chain is a generalisation of Y-wing. Essentially, instead of looking for a chain of three pairs, you look for longer chains in which the intersection cell of the Y-wing is expanded to a chain. The chain can be surprisingly long (one day, I might try to find out how long...), as shown in the following examples (only the relevant cells are shown).

The cells highlighted in yellow are the two ends of the chain, while the cells highlighted in red and marked with an asterisk are the cells in which we can possibly eliminate a candidate. If cell (4,4) contains a 1, the red cells cannot contain a 1. If, on the other hand, cell (4,4) contains a 2, it means that cell (4,7) must contain a 3, (1,7) a 4, ..., and (7,4) a 1. Therefore, without knowing whether cell (4,4) contains a 1 or a 2, we can remove all 1s from the red cells.

In this second example, we can only exclude the presence of a 1 in cell (4,7). But notice that the chain is 14-cell long. Also note that the some of the cells contain the same pair. In fact, most of the cells could be identical. The fact that the chain is so long shouldn’t deter you from attempting to apply this method. You only need to ignore all cells that contain other than two candidates, start from the top-left cell, see whether you link it to another cell at other cells with two candidates within one of its three groups (row, column, or square), and keep going, until you hit a cell of which the second candidate is identical to the one of the initial cell that you did not use to start the chain.

Obviously, many times it will happen that you don’t manage to build a chain. If so, look at the next cell with exactly two candidates and try again.

Here is another example:

Notice that most pairs are identical. I have only written them alternatively as 23 and 32 to make the following of the chain easier.

Program

To implement the XY-chain strategy, you start like for the Y-wing strategy (see my previous post). That is, you form two matrices: n_x_pairs[i1][i2] counting the pairs with candidates i1 and i2, and x_pairs[i1][i2][group type][pair index] containing the coordinates of the pairs. For example, x_pairs[3][4][ROW][1] is the row index of the second pair with coandidates 3 and 4 that the program found (the second pair because the pair index starts from zero.

Somehow, it might have seemed more natural to place the pair index before the group type, so as to use the fastest-changing index of the matrix (i.e., the rightmost one) for row/column/square IDs. But the purpose of the matrix is to find pairs that have one of the groups in common. Therefore, if I had placed the pair index before the group type, I would have then been forced to scan all the values of the pair index when looking for pairs with a particular coordinate.

As with the Y-wing strategy, the ‘root’ function xy_chain() executes xy_chain_digit() for each possible candidate if n_x_pairs tells us that there are at least two pairs with that candidate. xy_chain_digit(i0) then executes xy_chain_step() for each pair containing the i0 candidate.

xy_chain_step() calls itself recursively until it reaches a pair containing e0. That is, until it reaches the end of a chain. In order for xy_chain_step() to avoid looping back to cells already in the chain, it must be able to recognise whether a cell has already been used. I solved this issue by adding 10 to the row index of the cells as they are ‘attached’ to the chain. xy_chain_step() also has to know the coordinates of the initial cell, so that when it reaches the end of the chain it can determine the intersection with the groups of the final cell and, in this way, identify the cells from which i0 can be removed. Also, xy_chain_step() must also know the coordinates of the previous cell, otherwise, it couldn’t determine whether which cell, if any, can be attached to the chain. Finally, I wanted xy_chain_step() to be able to log a message containing the list of all the cells of the chain.

In conclusion, I had to pass ‘down’ to xy_chain_step() quite a bit of information. Moreover, I needed to be able to attach fresh information every time the function was executed. To do so, I created the following straucture and typedef:

typedef struct chain_info_struct *chain_info_struct_p;

typedef struct chain_info_struct {

     int digit;

     int coords[3];

     chain_info_struct_p next;

     } chain_info_struct;

As you can see, the structure contains the new candidate of a cell and the cell coordinates, plus a pointer to a structure, so that it can really build the chain. For example, if we start a chain with the candidate 5 forming a pair with 8 in cell (3,6), the structure is filled in with 5, 3, 6, 5, 0 (where 5 is the square ID and 0 is the place to be used for the pointer to the next instantiation of the structure).

The first thing xy_chain_step() does is to create a few pointers to make the programming comfortable and clearer:

chain_info_struct_p i0_info_p = info;

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 > 0);

int i0 = i0_info_p->digit;

int ix = ix_info_p->digit;

It then looks for a pair containing the candidate ix (i.e., 8 in our example) and with one of its groups intersecting

ix_info_p->coords[ROW] or

ix_info_p->coords[COL] or

ix_info_p->coords[SQU]

In our example: row 3, column 6, or square 5. Let’s say that it find the pair 83 in cell (3,0). As the initial candidate in the example (i0) was 5, it means that the chain is not completed. xy_chain_step() creates a structure to store the new information and attaches it to the chain, before executing itself recursively:

chain_info_struct iy_info;

iy_info.digit = iy;

iy_info.coords[ROW] = kRxy;

iy_info.coords[COL] = kCxy;

iy_info.coords[SQU] = kSxy;

iy_info.next = 0;

ix_info_p->next = &iy_info;

n_found += xy_chain_step(info, depth + 1);

From the call, you see that xy_chain_step() has two parameters. The first one is the chain of structures and the third parameter is a counter of recursions, which increases by one every time the function calls itself. Its purpose will become clear shortly.

What happens when xy_chain_step() find a pair with its second digit identical to i0? In our example, let’s say that in cell (3,0) the function finds the pair 85. First of all, we check that the ‘depth’ argument is greater than 2. If not, it means that we cannot possibly have hit a proper chain, and ignore the match. If we are past the second recursion, we check that at least one of groups of the newly found cell is not identical to the corresponding group of the initial cell. If that were the case, it would mean that we have looped back to the initial cell.

If we pass the checks listed in the previous paragraph, it means that we have found a proper chain, and that we can remove i0 from the intersection of the groups of the two ends of the chain. The message we get is something like this:

xy_chain_step (crossing): (1,1):38 (0,1):82 (0,4):28 (1,4):89 (1,7):97 (4,7):73

xy_chain_step: removed 3 from (4,1)

Now, let’s follow the chain on the sudoku table:

Do you notice anything funny? The chain goes up, then right, then down. It could have gone right from the starting cell, to form the chain: (1,1):38 (1,4):89 (1,7):97 (4,7):73 with identical result. It found a longer chain because, as the sudoku table is scanned row by row from the top, the pair in (0,1) was discovered before the pair in (1,4). The chain the program found is perfectly valid, but it is not the shortest one. If we want the program to optimise the length of the chains it finds, we first have to discover all valid chains with the same ends, and then pick the shortest one. But that is for another day...