11
\$\begingroup\$

I recently got a new Sudoku app that produces really hard Sudoku's, which can't be solved using the standard strategies. So I had to learn a few new ones. One of these strategies is the Y-Wing Strategy. It is ranked under "Tough Strategies", but it is actually not that hard.

Example

For this strategy only 4 cells are important. Therefore I ignored all other cells in the images.

We look at all candidates for each cell. In the following example we have a cell with the candidates 3 7 (that means we have already rejected the candidates 1 2 4 5 6 8 9, for instance because there is a 1 in the same row, a 2 in the same 3x3 box, ...), a cell with the candidates 6 7, a cell with the candidates 3 6 and a cell with the candidates 2 6. The Y-Wing strategy will suggest, that the 6 can be removed from the candidates of the downright cell, leaving only a 2 as candidate, which you can fill in. So we found a correct number and are one step closer in solving the full Sudoku.

First Example

Why can the 6 be removed?

Explanation

Let us assume that the 6 is the correct number for the downright cell. Now there is a 6 in this column, therefore we can remove the 6 from the candidates of the top right cell, leaving only a 7, which we can fill in. The same happens with the down left cell. We can remove the 6 and fill in the 3. Now if we look at the top left cell we get a contradiction. Because now there's already a 7 in the same row and a 3 in the same column, so we can remove the 7 and the 3 of the candidates, leaving no candidates at all. Which is clearly not possible. Therefore the 6 cannot be the correct number of the downright cell.

More precisely: If we have 4 cells with the candidates [A B] [A C] [C D] [B C] (in this order or circular rotated) and the cells are connected (via same row, same column or same 3x3 box) in a circle (Cell 1 is connected to Cell 2, which is connected to Cell 3, which is connected to Cell 4, which is connected to Cell 1), than you can remove C from the [C D] cell. It is crucial, that the three cells [A B], [A C] and [B C] only contain two candidates each. Differently the cell [C D], which may contain more or less (D can be zero, one or even more candidates).

Example with letters instead of numbers

Notice that I explicitly said they can be connected either way. In the next example you can see the strategy applied again. But this time the 4 cells doesn't form a rectangle. The down left and downright cells are simply connected, because they are in the same 3x3 box. Y-Wing says, that we can remove the 1 as candidate of the top left cell. This time there are still 2 candidates in this cell left, so we didn't actually found a new correct number. But nevertheless the removal of the 1 can open doors to different strategies.

Second example, not in a rectangle

If you want more information about the strategy or want a few more examples, visit sudokuwiki.org.

Challenge Specifications

You will receive 4 lists as input, representing the candidates of the cells. The four cells are connected like a circle (Cell 1 is connected to Cell 2, which is connected to Cell 3, which is connected to Cell 4, which is connected to Cell 1). You can assume that each list is sorted in ascending order.

Your job is to remove one candidate (by applying the Y-Wing strategy) and returning the resulting candidates lists in the same order. If you can't apply the strategy, just return the same candidates lists.

If there are two possible solutions (you could remove A of cell B or remove C of cell D), than return only one solution. It doesn't matter which one.

The input can be in any native list or array format. You could also use a list of lists or something similar. You can receive the input via STDIN, command-line argument, prompt or function argument and return the output via return value or simply by printing to STDOUT.

This is code-golf. The shortest code (in bytes) wins.

Test Cases

[3 7] [6 7] [2 6] [3 6]       => [3 7] [6 7] [2] [3 6]   # Example 1
[6 7] [2 6] [3 6] [3 7]       => [6 7] [2] [3 6] [3 7]   # Example 1, different order
[2 6] [3 6] [3 7] [6 7]       => [2] [3 6] [3 7] [6 7]   # Example 1, different order
[3 6] [3 7] [6 7] [2 6]       => [3 6] [3 7] [6 7] [2]   # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9]     => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4]     => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8]       => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4]         => [4 7] [7 8] [4 8] []    # Fictional example
[3 7] [2 6] [6 7] [3 6]       => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4]     => [4 7] [2 7 8] [4 8] [1 4] # -||-
\$\endgroup\$
  • \$\begingroup\$ Can multiple sets in a single input be exactly same ? \$\endgroup\$ – Optimizer Apr 25 '15 at 17:46
  • \$\begingroup\$ @Optimizer Yes, for instance in the 8th test case, 7 8 is are the candidates for the first and the second cell. The Y-Wing strategy can still be applied. \$\endgroup\$ – Jakube Apr 25 '15 at 17:48
  • \$\begingroup\$ @Jakube ah okay, didn't see that. \$\endgroup\$ – Optimizer Apr 25 '15 at 17:52
  • \$\begingroup\$ If more than 1 solutions are possible, can I output any one of them ? \$\endgroup\$ – Optimizer Apr 25 '15 at 18:32
  • \$\begingroup\$ Yes, I clarified it in the question. \$\endgroup\$ – Jakube Apr 25 '15 at 19:02
3
\$\begingroup\$

CJam, 90 bytes

Ugghhh, this is too long because of the constraint that the other 3 cells should have only 2 candidates.

l~_:_(a+2/::&_{,}$2>:&:Y;{:PY&Y{P1<}?~}%:X,3>1${,}$W=_,2>\Y&,1?*{X:_(+2/{~:I=}#)_2$=I-t}&p

This expects input as a list of list in CJam format. For ex.:

[[2 6] [3 6] [3 7] [6 7]]

gives output in a CJam list of list format:

[[2] [3 6] [3 7] [6 7]]

Will add explanation once I am done golfing..

Try it online here or try the whole test suite here.

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 124 110 bytes

Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])&

Examples:

In[1]:= yWing = Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])& ;

In[2]:= yWing[{{3, 7}, {6, 7}, {2, 6}, {3, 6}}]

Out[2]= {{3, 7}, {6, 7}, {2}, {3, 6}}

In[3]:= yWing[{{4, 7}, {7, 8}, {4, 8}, {4}}]

Out[3]= {{4, 7}, {7, 8}, {4, 8}, {}}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.