Sudoku - Programming the Y-wing strategy

On the web there are many explanations of the Y-wing strategy, but none seems to go to the core of the issue. The only clear statement I found was that Y-wing doesn’t solve cells, but only eliminates possible candidates.

Strategy

Look for cells that contain only two candidates each. Among those cells, look for three cells that satisfy the following two conditions:

1. The arrangement of candidates in the cells is AB, AC, and BC. That is, no two cells have the same pair of candidates.

2. The cells are in two intersecting groups. This is equivalent to say that the two wing cells cannot share any group and can only happen in two ways: row+column (one of the cells shares the row with one of the other two cells and the column with the third one) and line+square, where ‘line’ stands for either ‘column’ or ‘row’ (one of the cells shares the line (row or column) with one of the other two cells and the square with the third one).

In other words, you can apply Y-wing when you find a chain of three cells containing all possible different pairs that can be formed with three candidates, whereby two cells are said to be chained if they belong to the same group and one (and only one) of their two candidates are identical.

Anyhow, when the two conditions are satisfied, you have one of the following two configurations:

row+column

The four squares shown can be adjacent to each other or not. Regardless of what numeric candidates correspond to A, B, and C, one of the candidates appears in both of the two ‘wings’. In the example, it is C. If, at a later stage, you find out that the solution for the intersection cell is A, C must be in the bottom-left cell. If, on the other hand, the intersection cell turns out to contain B, C must be in the top-right cell. In either case, the cell marked with an asterisk cannot contain C.

line+square

In this example, the line containing one of the pairs is the top row of a square, and the square is on the left of the portion of row which contains the BC pair. But the row could be in the middle or at the bottom of the square, and the square could be on the right. Also, you could rotate the diagramme ninenty degree and have the column-square configuration. You can easily verify that, regardless of whether the intersection cell turns out to contain A or B, the cells marked with an asterisk cannot contain a C.

Program

The strategy is centred around two tables that are accessible to all functions that implement the Y-wing strategy:

char n_x_pairs[10][10] = {{0}};

char *x_pairs[10][10][3] = {{{0}}};

with the following definitions for the third index of x_pairs:

#define ROW 0

#define COL 1

#define SQU 2

The first two indices refer to candidates, from 1 to 9. n_x_pairs counts the number of pairs for every possible combination of two candidates, while x_pairs stores the coordinates of the cells that contain the pairs. I use the type char because one byte is more than sufficient to store the numbers we deal with.

x_pairs is a table of pointers because there can be more than one pair containing the same combination of candidates.

I make a first pass of scanning the sudoku table to fill in n_x_pairs. At the end of the scan, for example, a value of 2 in n_x_pairs[4][7] tells me that there are two cells containing the pair of candidates 4 and 7. I also use n_x_pairs[i][0] to store the total number of pairs containing candidate i.

Knowing how many pairs are possible, allows me to allocate from the heap exactly the amount of space I need to store the coordinates of the cells:

char *data_block = (char*)malloc(n_x_pairs[0][0] * 6);

{

     char *offset = data_block;

      for (int i1 = 1; i1 <= 9; i1++) {

          for (int i2 = 1; i2 <= 9; i2++) {

              for (int k_coord = 0; k_coord < 3; k_coord++) {

                   x_pairs[i1][i2][k_coord] = offset;

                   offset += n_x_pairs[i1][i2];

                   }

              }

          }

     }

Notice that I have enclosed the code between square brackets in order to limit the scope of the variable offset to the filling in of the data block. It’s something I like to do whenever I can. Keeping the variables as local as possible is always safer. I also, obviously, inserted

free(data_block);

before returning from the function (and I always use a single return statement).

To fill in x_pairs, I scan the sudoku table a second time and, this time, save the coordinates of each pair I find. For ease of use later, I ‘symmetrise’ the array. What I mean is that, for example, when I find a cell with the pair i1 and i2, I store its coordinates twice. This is how it looks for the row coordinate:

x_pairs[i1][i2][ROW][n] = (char)k;

x_pairs[i1][i2][COL][n] = (char)j;

x_pairs[i1][i2][SQU][n] = (char)(k/3*3+j/3);

x_pairs[i2][i1][ROW][n] = (char)k;

x_pairs[i2][i1][COL][n] = (char)j;

x_pairs[i2][i1][SQU][n] = (char)(k/3*3+j/3);

Where ‘n’ is the counter of i1-i2 pairs found so far.

Once the tables have been filled in, we can look for possible Y-wing combinations. You can only use Y-wing if you have at least two pairs with the same candidate. Therefore, I execute the function that does all the work as follows:

for (int i = 1; i <= 9; i++) {

     if (n_x_pairs[i][0] >= 2) {

         result |= y_wing_digit(i);

         }

     }

Within y_wing_digit() I assign to the candidate parameter the identifier i0. i0 corresponds to the letter C of the examples in the strategy description.

The function consists of a loop that contains the whole functionality:

for (int i1 = 1; i1 <= 9; i1++) {

     for (int i1k = 0; i1k < n_x_pairs[i0][i1]; i1k++) {

The first ‘for’ goes through all the possible candidates that form a pair with i0. i1 corrisponds to either A or B of the examples (let’s say A). Concerning the second loop, as the for statement checks the control variable before entering, it means that the code inside it is only executed if the puzzle, at the stage when we apply Y-wing, contains at least one i0-i1 pair.

Inside this first couple of loops, we have a second set of for statements:

for (int i2 = 1; i2 <= 9; i2++) {

     if (i2 != i0) {

         for (int i2k = 0; i2k < n_x_pairs[i1][i2]; i2k++) {

They do for i1 what the first set of loops did for i0, but notice that the second loop is only entered if i2 is different from i0. If i1 was A, i2 is B.

We have now found three cells that contain the pairs i0-i1, i1-i2, and i2-i0. This means that we find the same three cells starting from i0-i2 instead of i0-i1 (i.e., starting from BC instead of AC). To avoid wasting time in attempting to remove twice the same candidate, I only proceed when i2 > i1 (i1 > i2 would have been OK as well).

Also, I have to check that the cells with i0-i1 and i1-i2 share at least one group. If that is the case, I then look for a pair containing i2 and i0:

for (int i3k = 0; i3k < n_x_pairs[i2][i0]; i3k++) {

If we find one (i.e., when we enter the loop), before being satisfied that the Y-wing strategy applies, we have to check a couple of other things. Firstly, we check that the third and first cells (i.e., those with BC and with AC) do not share any group. Secondly, we have to check that the third and second cell (i.e., those with BC and AB) do share at least one group.

If we have managed to pass all the checks, we know that we can apply Y-wing. We still have to determine what type it is, but we know that we can eliminate at least one candidate.

Here is what my program logs when it finds an Y-wing:

y_wing_digit: 7-5 in (7,0), 5-9 in (7,7), and 9-7 in (1,7)

y_wing_digit: removed 7 from (1,0)

Was it worth investing so much work and writing so much code to eliminate one candidate? It might make all the difference...