11
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.
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).
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.
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] # -||-
Jakube
Posted 2015-04-25T16:47:22.573
Reputation: 21 462
Can multiple sets in a single input be exactly same ? – Optimizer – 2015-04-25T17:46:09.507
@Optimizer Yes, for instance in the 8th test case,
7 8is are the candidates for the first and the second cell. The Y-Wing strategy can still be applied. – Jakube – 2015-04-25T17:48:36.380@Jakube ah okay, didn't see that. – Optimizer – 2015-04-25T17:52:54.963
If more than 1 solutions are possible, can I output any one of them ? – Optimizer – 2015-04-25T18:32:27.980
Yes, I clarified it in the question. – Jakube – 2015-04-25T19:02:57.117