Why Avoidable Loops and Missing Loops Don't need the uniqueness assumption
The Theory
Among advanced Sudoku techniques, the Avoidable Loop is one of the most elegant. Its most surprising feature is this: even when some cells are already solved, and it can’t produce multiple solutions, the pattern can still give us valid eliminations.
That apparent contradiction puzzled me for a long time. After working through the logic carefully, I reached a key conclusion: the Avoidable Loop does NOT depend on a unique-solution assumption at all.
Let’s make this concrete with the example above: an Avoidable Loop Type 2 on {D2, E2, E5, F5, F8, D8/45}. The core is the relationship between two assertions:
Assertion A: The puzzle has a solution where D2=5, E2=4, E5=5, F5=5, F8=4, D8=5.
Assertion B: The puzzle has a solution where D2=4, E2=5, E5=4, F5=4, F8=5, D8=4.
The six-cell loop {D2, E2, E5, F5, F8, D8} enforces an equivalence between A and B. If A is true, we take the solution and swap 4 and 5 in all six cells immediately constructs a new solution where B is true. The reverse works similarly, if B is true, then A is true.
So A and B are equivalent: they are either both true or both false.
Now comes the final step. We already know D8=4, so Assertion A (which requires D8=5) is false. Because A and B are equivalent, B must also be false. Notice that this argument never invokes uniqueness.
By comparison, a standard Unique Loop usually reasons differently: if both A and B were true, the grid would admit two distinct solutions, which violates uniqueness; therefore both must be false.
Similarly, when a Unique Loop has missing candidates, we call it a Missing Loop here, its logic is the same as Avoidable Loop and likewise does not rely on uniqueness.
Since Avoidable Rectangle and Missing Rectangle(ie. Unique Rectangle with missing candidates), is just a special case of Avoidable Loop and Missing Loop respectively, they do not require the uniqueness assumption as well.
The Experiment
This experiment focused on Avoidable Rectangle and Missing Rectangle, which is the level 4 of Avoidable Loop and Missing Loop respectively. Because I wanted to keep it simple so anyone can replicate it easily.
Some people are not convinced because they assumed Avoidable Rectangles (and Missing Rectangle) are based on uniqueness and is about preventing multiple solutions. But there can’t be multiple solutions if we already have a solved cell(or a missing candidate). It’s really not about preventing multiple solutions but about the symmetry between the two solutions. If one solution is already denied(by a solved cell or a missing candidate), then the other is also denied. No uniqueness assumption required! If you really take some time to think about it, you will be able to verify the logic.
If these techniques really require a unique solution, someone must be able to provide an example, when we start with a puzzle with multiple solutions, and then use Avoidable Rectangle or Missing Rectangle techniques with non-unique techniques and the grid get into an invalid state. But no one have ever provided an example where this happens. It shouldn’t be hard to find an example if uniqueness is really required.
I ran an experiment myself, for a million random puzzles with multiple solutions, to find examples to prove myself wrong, but despite the techniques (Avoidable Rectangle and Missing Rectangle) being used tens of thousands of times, the grid never get into an invalid state, which is the oppsite of Unique Rectangle, where I found an example where the grid get into an invalid state within 30 random puzzles. Here are the details of my experiement:
Setup
- Generator: randomly generate a puzzle with a unique solution first(as usual), then randomly remove clues until the puzzle has at least 2 solutions.
- Test puzzle: each sampled puzzle has at least 2 solutions.
- Reference Solution: a random solution is picked for each puzzle to check for contradiction.
- Stop condition: contradiction detected, that is, when the grid has at least one unsolved cell with no candidates, or the puzzle is solved, or the filled numbers in the end state of the grid contradicts the reference solution(that is, any filled number that is different than the number in the same cell in the reference solution is a contradiction).
I compared two solver configurations:
- Normal Unique Rectangle only
- Avoidable Rectangle + Missing Rectangle only
Both solvers used the same support techniques, so the only variable was the Unique Rectangle techniques.
Techniques enabled in solver details
The experiment solver used these techniques:
- Naked Sets up to size 4 (including Naked Single)
- Hidden Sets up to size 4 (including Hidden Single)
- Fish up to size 4 with fins enabled
- Unique Rectangle with two types of setups
- Chains up to length 8 (regular AIC chain techniques, no grouped chains, length means the number of links in the chain)
Unique Rectangle configuration:
- Normal arm: Normal Unique Rectangle
- Avoidable/Missing arm: Avoidable Rectangle + Missing Rectangle
-
Avoidable Rectangle Type 1, Type 2, Type 3, Type 6, Hidden, and Type 7 does exist, only Avoidable Rectangle that doesn’t exist is Type 4. Even though most solvers only implement Type 1 and Type 2, but the techniques do exist, and I have already found many examples in my research. I wouldn’t get into the details here as it will take forever to write the post.
-
Unique Rectangle Type 7 (and avoidable and missing variants) I used is a generalized version of the regular Type 7. How it works is, assume a UR candidate in one of the cells with extra candidates is true, then, fill that cell with that number, and then use Singles on the grid until we reach a state where the extra candidates in the UR cells are eliminated(eliminated or the cell is filled with an UR number). If we reach this state, then this means the original assumption is wrong, meaning the original UR candidate that produces this state can be eliminated.
Results
Summary
I tried a million random puzzles (with multiple solutions) in the case of avoidable and missing varients of Unique Rectangle. Despite they were used 28922 times, no contradiction was found!
For the normal Unique Rectangle, I only need to try 21 random puzzles. And it’s only used 53 times, and one contradiction was already found!
One of the reasons it takes so few puzzles to find a contradiction for the normal Unique Rectangle is that the normal Unique Rectangle is way more common. But then again, I tried 1 million puzzles to make sure we use the avoidable and missing varients enough times.
Avoidable Rectangle + Missing Rectangle
Avoidable and Missing UniqueLoop result
- Tested puzzles: 1000000
- Contradiction puzzles: 0
- Total UniqueLoop usage: 28922
- Average UniqueLoop per puzzle: 0.029
Detailed technique statistics:
- UniqueLoopType7Missing: Total 16456, Average 0.016/puzzle
- UniqueLoopHiddenMissing: Total 5377, Average 0.005/puzzle
- UniqueLoopType1Missing: Total 2489, Average 0.002/puzzle
- UniqueLoopType4Missing: Total 1843, Average 0.002/puzzle
- UniqueLoopType7Avoidable: Total 746, Average 0.001/puzzle
- UniqueLoopHiddenAvoidable: Total 623, Average 0.001/puzzle
- UniqueLoopType3Missing: Total 531, Average 0.001/puzzle
- UniqueLoopType6Missing: Total 488, Average 0.000/puzzle
- UniqueLoopType2Missing: Total 127, Average 0.000/puzzle
- UniqueLoopType3Avoidable: Total 100, Average 0.000/puzzle
- UniqueLoopType2Avoidable: Total 67, Average 0.000/puzzle
- UniqueLoopType6Avoidable: Total 65, Average 0.000/puzzle
- UniqueLoopType1Avoidable: Total 10, Average 0.000/puzzle
No contradiction was found.
Normal Unique Rectangle
Normal UniqueLoop result
- Tested puzzles: 21
- Contradiction puzzles: 1
- Total UniqueLoop usage: 53
- Average UniqueLoop per puzzle: 2.524
Detailed technique statistics:
- UniqueLoopType7: Total 35, Average 1.667/puzzle
- UniqueLoopHidden: Total 9, Average 0.429/puzzle
- UniqueLoopType1: Total 5, Average 0.238/puzzle
- UniqueLoopType4: Total 3, Average 0.143/puzzle
- UniqueLoopType3: Total 1, Average 0.048/puzzle
Contradiction detected, solver: Normal UniqueLoop (Normal only), puzzle: 21, reason: Final board filled numbers mismatches one reference solution
Contradiction puzzle:
3...79.4....8..1...49.......915..6.7..46.1..8.......2.21.........3........7.5.2..
Interpretation
For this test design, Avoidable Rectangle + Missing Rectangle behaved robustly across a large sample of multi-solution puzzles, while Normal Unique Rectangle produced a contradiction quickly.
This supports the idea that Avoidable/Missing variants are safe unlike normal UR assumptions when uniqueness is not guaranteed.
Details of the contradiction
Here is the contradiction when we use normal unique rectangles on a puzzle with multiple solutions.
puzzle: 3...79.4....8..1...49.......915..6.7..46.1..8.......2.21.........3........7.5.2..
reference solution: 368179542572843169149265783891524637724631958635798421216487395453912876987356214
the steps are the following:
step 1 is Naked Single: A4: 8 in block 1
step 2 is Naked Single: H4: 3 in block 1
step 3 is Hidden Single: A3: 1 in block 1
step 4 is Hidden Single: D1: 1 in block 2
step 5 is Hidden Single: B5: 2 in block 4
step 6 is Hidden Single: B6: 3 in block 4
step 7 is Hidden Single: E5: 3 in block 5
step 8 is Hidden Single: I6: 1 in block 6
step 9 is Hidden Single: G6: 4 in block 6
step 10 is Hidden Single: E8: 1 in block 8
step 11 is Hidden Single: H9: 1 in block 9
step 12 is Hidden Single: A5: 7 in row 5
step 13 is Hidden Single: B2: 7 in block 1
step 14 is Fish Lv.1: Cells B1,C1: 8 base regions = {block 1} cover regions = {row 1} removes G1/8
grid before the step is
.-------------------.-------------------.-------------------.
| 3 568 2568 | 1 7 9 | 58 4 256 |
| 56 7 256 | 8 246 23456 | 1 569 23569 |
| 1 4 9 | 23 26 2356 | 3578 5678 2356 |
.-------------------+-------------------+-------------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 59 59 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.-------------------+-------------------+-------------------.
| 2 1 568 | 3479 4689 34678 | 35789 56789 34569 |
| 4569 568 3 | 2479 1 24678 | 5789 56789 4569 |
| 469 68 7 | 349 5 3468 | 2 1 3469 |
.-------------------.-------------------.-------------------.
step 15 is Naked Single: G1: 5 in block 1
step 16 is Naked Single: G5: 9 in block 1
step 17 is Naked Single: H5: 5 in block 1
step 18 is Hidden Single: F3: 5 in row 3
step 19 is Hidden Single: B8: 5 in column 2
step 20 is Hidden Single: I7: 5 in block 9
step 21 is Fish Lv.1: Cells D7,E7,F7: 4 base regions = {row 7} cover regions = {block 8} removes D8/4, F8/4, D9/4, F9/4
grid before the step is
.-------------------.-------------------.-------------------.
| 3 68 268 | 1 7 9 | 5 4 26 |
| 56 7 256 | 8 246 2346 | 1 69 2369 |
| 1 4 9 | 23 26 5 | 378 678 236 |
.-------------------+-------------------+-------------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.-------------------+-------------------+-------------------.
| 2 1 68 | 3479 4689 34678 | 378 6789 5 |
| 469 5 3 | 2479 1 24678 | 78 6789 469 |
| 469 68 7 | 349 5 3468 | 2 1 3469 |
.-------------------.-------------------.-------------------.
step 22 is Hidden Single: D7: 4 in column 4
step 23 is Naked Lv. 2: Cells C7,B9: 6,8 in block 7 removes A8/6, A9/6
grid before the step is
.----------------.----------------.----------------.
| 3 68 268 | 1 7 9 | 5 4 26 |
| 56 7 256 | 8 246 2346 | 1 69 2369 |
| 1 4 9 | 23 26 5 | 378 678 236 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 689 3678 | 378 6789 5 |
| 469 5 3 | 279 1 2678 | 78 6789 469 |
| 469 68 7 | 39 5 368 | 2 1 3469 |
.----------------.----------------.----------------.
step 24 is Hidden Pair: cells G3, H3 numbers = 7, 8 removes = G3/3, H3/6
grid before the step is
.----------------.----------------.----------------.
| 3 68 268 | 1 7 9 | 5 4 26 |
| 56 7 256 | 8 246 2346 | 1 69 2369 |
| 1 4 9 | 23 26 5 | 378 678 236 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 689 3678 | 378 6789 5 |
| 49 5 3 | 279 1 2678 | 78 6789 469 |
| 49 68 7 | 39 5 368 | 2 1 3469 |
.----------------.----------------.----------------.
step 25 is Hidden Single: G7: 3 in column 7
step 26 is Hidden Pair: cells E6, E7 numbers = 8, 9 removes = E7/6
grid before the step is
.----------------.----------------.----------------.
| 3 68 268 | 1 7 9 | 5 4 26 |
| 56 7 256 | 8 246 2346 | 1 69 2369 |
| 1 4 9 | 23 26 5 | 78 78 236 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 689 678 | 3 6789 5 |
| 49 5 3 | 279 1 2678 | 78 6789 469 |
| 49 68 7 | 39 5 368 | 2 1 469 |
.----------------.----------------.----------------.
step 27 is Fish Lv.1: Cells F7,F8,F9: 6 base regions = {block 8} cover regions = {column 6} removes F2/6
grid before the step is
.----------------.----------------.----------------.
| 3 68 268 | 1 7 9 | 5 4 26 |
| 56 7 256 | 8 246 2346 | 1 69 2369 |
| 1 4 9 | 23 26 5 | 78 78 236 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 89 678 | 3 6789 5 |
| 49 5 3 | 279 1 2678 | 78 6789 469 |
| 49 68 7 | 39 5 368 | 2 1 469 |
.----------------.----------------.----------------.
step 28 is Unique Loop Lv. 4 Type1 cells={A2,C2,C6,A6}, numbers={5,6} removes C2/56
grid before the step is
.----------------.----------------.----------------.
| 3 68 268 | 1 7 9 | 5 4 26 |
| 56 7 256 | 8 246 234 | 1 69 2369 |
| 1 4 9 | 23 26 5 | 78 78 236 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 56 3 56 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 89 678 | 3 6789 5 |
| 49 5 3 | 279 1 2678 | 78 6789 469 |
| 49 68 7 | 39 5 368 | 2 1 469 |
.----------------.----------------.----------------.
step 29 is Naked Single: C2: 2 in block 1
step 30 is Hidden Single: A2: 5 in block 1
step 31 is Naked Single: A6: 6 in block 1
step 32 is Naked Single: C6: 5 in block 1
step 33 is Hidden Single: I1: 2 in row 1
step 34 is Unique Loop Lv. 4 Type1 cells={G3,H3,H8,G8}, numbers={7,8} removes H8/78
grid before the step is
.----------------.----------------.----------------.
| 3 68 68 | 1 7 9 | 5 4 2 |
| 5 7 2 | 8 46 34 | 1 69 369 |
| 1 4 9 | 23 26 5 | 78 78 36 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 6 3 5 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 89 678 | 3 6789 5 |
| 49 5 3 | 279 1 2678 | 78 6789 469 |
| 49 68 7 | 39 5 368 | 2 1 469 |
.----------------.----------------.----------------.
step 35 is Naked Lv. 2: Cells H2,H8: 6,9 in column 8 removes H7/69
grid before the step is
.----------------.----------------.----------------.
| 3 68 68 | 1 7 9 | 5 4 2 |
| 5 7 2 | 8 46 34 | 1 69 369 |
| 1 4 9 | 23 26 5 | 78 78 36 |
.----------------+----------------+----------------.
| 8 9 1 | 5 24 24 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 6 3 5 | 79 89 78 | 4 2 1 |
.----------------+----------------+----------------.
| 2 1 68 | 4 89 678 | 3 6789 5 |
| 49 5 3 | 279 1 2678 | 78 69 469 |
| 49 68 7 | 39 5 368 | 2 1 469 |
.----------------.----------------.----------------.
step 36 is Hidden Single: E7: 9 in row 7
step 37 is Naked Single: E6: 8 in block 1
step 38 is Naked Single: F6: 7 in block 1
step 39 is Naked Single: D6: 9 in block 1
step 40 is Naked Single: D9: 3 in block 1
step 41 is Naked Single: D3: 2 in block 1
step 42 is Naked Single: E3: 6 in block 1
step 43 is Naked Single: E2: 4 in block 1
step 44 is Naked Single: F2: 3 in block 1
step 45 is Naked Single: I3: 3 in block 1
step 46 is Naked Single: E4: 2 in block 1
step 47 is Naked Single: F4: 4 in block 1
step 48 is Naked Single: D8: 7 in block 1
step 49 is Naked Single: G8: 8 in block 1
step 50 is Naked Single: G3: 7 in block 1
step 51 is Naked Single: H3: 8 in block 1
step 52 is Naked Single: H7: 7 in block 1
step 53 is Hidden Single: F8: 2 in block 8
step 54 is Fish Lv.1: Cells H8,I8: 6 base regions = {row 8} cover regions = {block 9} removes I9/6
grid before the step is
.-------------.-------------.-------------.
| 3 68 68 | 1 7 9 | 5 4 2 |
| 5 7 2 | 8 4 3 | 1 69 69 |
| 1 4 9 | 2 6 5 | 7 8 3 |
.-------------+-------------+-------------.
| 8 9 1 | 5 2 4 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 6 3 5 | 9 8 7 | 4 2 1 |
.-------------+-------------+-------------.
| 2 1 68 | 4 9 68 | 3 7 5 |
| 49 5 3 | 7 1 2 | 8 69 469 |
| 49 68 7 | 3 5 68 | 2 1 469 |
.-------------.-------------.-------------.
step 55 is Unique Loop Lv. 4 Type1 cells={A8,I8,I9,A9}, numbers={4,9} removes I8/49
grid before the step is
.-------------.-------------.-------------.
| 3 68 68 | 1 7 9 | 5 4 2 |
| 5 7 2 | 8 4 3 | 1 69 69 |
| 1 4 9 | 2 6 5 | 7 8 3 |
.-------------+-------------+-------------.
| 8 9 1 | 5 2 4 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 6 3 5 | 9 8 7 | 4 2 1 |
.-------------+-------------+-------------.
| 2 1 68 | 4 9 68 | 3 7 5 |
| 49 5 3 | 7 1 2 | 8 69 469 |
| 49 68 7 | 3 5 68 | 2 1 49 |
.-------------.-------------.-------------.
step 56 is Naked Single: I8: 6 in block 1
step 57 is Naked Single: I2: 9 in block 1
step 58 is Naked Single: H2: 6 in block 1
step 59 is Naked Single: H8: 9 in block 1
step 60 is Naked Single: A8: 4 in block 1
step 61 is Naked Single: A9: 9 in block 1
step 62 is Naked Single: I9: 4 in block 1
the final grid is
.----------.----------.----------.
| 3 68 68 | 1 7 9 | 5 4 2 |
| 5 7 2 | 8 4 3 | 1 6 9 |
| 1 4 9 | 2 6 5 | 7 8 3 |
.----------+----------+----------.
| 8 9 1 | 5 2 4 | 6 3 7 |
| 7 2 4 | 6 3 1 | 9 5 8 |
| 6 3 5 | 9 8 7 | 4 2 1 |
.----------+----------+----------.
| 2 1 68 | 4 9 68 | 3 7 5 |
| 4 5 3 | 7 1 2 | 8 9 6 |
| 9 68 7 | 3 5 68 | 2 1 4 |
.----------.----------.----------.
Contradiction!
The filled numbers contradicts the reference solution:
368179542
572843169
149265783
891524637
724631958
635798421 -> contradictions at this row
216487395 -> contradictions at this row
453912876 -> contradictions at this row
987356214- Fish level 1 just mean Pointing/Claiming.
- Unique Loop level 4 just mean Unique Rectangle
- Chain’s length mean the number of links