## a multisolutional sudoku solved by uniqueness

Advanced methods and approaches for solving Sudoku puzzles

### a multisolutional sudoku solved by uniqueness

A sudoku of shame?
Code: Select all
` *-----------* |.5.|.8.|.6.| |3..|1.2|..7| |..8|...|4..| |---+---+---| |.4.|.9.|.8.| |8..|...|..4| |.2.|.5.|.1.| |---+---+---| |..1|...|2..| |6..|4.8|..5| |.7.|.6.|.3.| *-----------* *-----------* |254|.8.|361| |396|142|857| |718|536|429| |---+---+---| |14.|69.|.82| |86.|.21|..4| |927|854|613| |---+---+---| |581|.7.|246| |632|418|..5| |479|265|138| *-----------*  *--------------------------------------------------* | 2    5    4    | 79   8    79   | 3    6    1    | | 3    9    6    | 1    4    2    | 8    5    7    | | 7    1    8    | 5    3    6    | 4    2    9    | |----------------+----------------+----------------| | 1    4    35   | 6    9    37   | 57   8    2    | | 8    6    35   | 37   2    1    |#579  79   4    | | 9    2    7    | 8    5    4    | 6    1    3    | |----------------+----------------+----------------| | 5    8    1    | 39   7    39   | 2    4    6    | | 6    3    2    | 4    1    8    | 79   79   5    | | 4    7    9    | 2    6    5    | 1    3    8    | *--------------------------------------------------* `

I made this sudoku step by step with the Sudoku Assistenten 2.0 (2 in r5c5 included). Suddenly I spotted a BUG-Pattern. Because I know that the good old SA can't detect BUG-Pattern, I tried the Explainer and tricked while removing the 2 in r5c5 because otherwise the explainer doesn't show a step-by-step solution of a multiple-solutional sudoku. Then SE gave me a solution and placed also the 2 in r5c5. Simple Sudoku instead shows 19 solutions (also without 2 in r5c5).
At first stunned, I realized soon that there is no classical BUG-Pattern to be seen her, but intertwined with the BUG a Unique Rectangle Type 1 in r58c78 upon 79.

The 5 in r5c7 is solving the Unique rectangle giving one valid solution, the 7 in the same cell (three times in it's row, column and box) is solving the BUG-pattern, giving the other valid solution. The 9 in the same cell is giving the 3rd valid solution. No idea which (uniqueness)strategy this 9 represents.

Without the 2 in r5c5 Simple Sudoku shows 19 solution. With the 2 in r5c5 it shows 3 solutions only. But the 2 is omittable because you can detect it easily by placing singles and Line vs. Box and Pairs and a Unique rectangle Type 1. But when the 2 is a part of the main solution that means, that Simple Sudoku is showing more solutions than actually are because it can't detect the rectangles and other strategies I suppose.

Happy weekend!
Claudia
claudiarabia

Posts: 288
Joined: 14 May 2006

For a puzzle without a unique solution, uniqueness techniques -- including UR Type 1 and BUG -- are invalid, so I don't understand the purpose of your thread.

claudiarabia wrote:But when the 2 is a part of the main solution that means, that Simple Sudoku is showing more solutions than actually are because it can't detect the rectangles and other strategies I suppose.

I seriously doubt Simple Sudoku is miscounting.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: a multisolutional sudoku solved by uniqueness

claudiarabia wrote:The 9 in the same cell is giving the 3rd valid solution. No idea which (uniqueness)strategy this 9 represents.

The 9 would come from
Code: Select all
`*--------------------------------------------------* | 2    5    4    | *79  8    *79  | 3    6    1    | | 3    9    6    | 1    4    2    | 8    5    7    | | 7    1    8    | 5    3    6    | 4    2    9    | |----------------+----------------+----------------| | 1    4    *35  | 6    9    *37  |*57   8    2    | | 8    6    *35  | *37  2    1    |*57+9 79   4    | | 9    2    7    | 8    5    4    | 6    1    3    | |----------------+----------------+----------------| | 5    8    1    | *39  7    *39  | 2    4    6    | | 6    3    2    | 4    1    8    | 79   79   5    | | 4    7    9    | 2    6    5    | 1    3    8    | *--------------------------------------------------* `
re'born

Posts: 551
Joined: 31 May 2007

claudiarabia wrote:Without the 2 in r5c5 Simple Sudoku shows 19 solution. With the 2 in r5c5 it shows 3 solutions only. But the 2 is omittable because you can detect it easily by placing singles and Line vs. Box and Pairs and a Unique rectangle Type 1. But when the 2 is a part of the main solution that means, that Simple Sudoku is showing more solutions than actually are because it can't detect the rectangles and other strategies I suppose.

Claudia, Simple Sudoku makes no mistake in counting 19 solutions for your puzzle, and your logic for the placement r5c5=2 is faulty. You can't apply UR (type 1) on a puzzle with multiple solutions!

I'll show you all 19 solutions. SS takes us to this state:
Code: Select all
` *-----------------------------------------------------------* | 24    5     24    | 79    8     79    | 3     6     1     | | 3     69    69    | 1     4     2     | 8     5     7     | | 7     1     8     | 56    3     56    | 4     2     9     | |-------------------+-------------------+-------------------| | 1     4     3567  | 367   9     367   | 567   8     2     | | 8     36    3567  | 2367  12    1367  | 5679  79    4     | | 9     2     67    | 8     5     4     | 67    1     3     | |-------------------+-------------------+-------------------| | 5     8     1     | 39    7     39    | 2     4     6     | | 6     39    239   | 4     12    8     | 179   79    5     | | 24    7     249   | 25    6     15    | 19    3     8     | *-----------------------------------------------------------*`

Where you can't make any more legal elimination from here.

If you assume r5c5=2, after a few trivial moves you arrive at:
Code: Select all
` *--------------------------------------------------* | 2    5    4    | 79   8    79   | 3    6    1    | | 3    9    6    | 1    4    2    | 8    5    7    | | 7    1    8    | 5    3    6    | 4    2    9    | |----------------+----------------+----------------| | 1    4    35   | 6    9    37   | 57   8    2    | | 8    6    35   | 37   2    1    | 579  79   4    | | 9    2    7    | 8    5    4    | 6    1    3    | |----------------+----------------+----------------| | 5    8    1    | 39   7    39   | 2    4    6    | | 6    3    2    | 4    1    8    | 79   79   5    | | 4    7    9    | 2    6    5    | 1    3    8    | *--------------------------------------------------*`

... which obviously leads to 3 solutions by assigning r5c7 to 5|7|9 respectively.

However, if you assume r5c5=1, you arrive at:
Code: Select all
` *-----------------------------------------------------------* |@24    5    @24    | 79    8     79    | 3     6     1     | | 3     69    69    | 1     4     2     | 8     5     7     | | 7     1     8     | 6     3     5     | 4     2     9     | |-------------------+-------------------+-------------------| | 1     4     3567  | 37    9     367   | 567   8     2     | | 8     36    3567  | 2     1     367   | 567   9     4     | | 9     2     67    | 8     5     4     | 67    1     3     | |-------------------+-------------------+-------------------| | 5     8     1     | 39    7     39    | 2     4     6     | | 6     39    39    | 4     2     8     | 1     7     5     | |@24    7    @24    | 5     6     1     | 9     3     8     | *-----------------------------------------------------------*`

Notice the deadly pattern in r19c13, that means this grid at least yield to 2 solutions. But all other cells are quite intertwined, so it takes a bit of work to enumerate all 16 solutions from this position.

Firstly notice in b5, the 6 can only appear in r4c6 or r5c6.

Assuming r5c6=6, after a few trivial moves:
Code: Select all
` *-----------------------------------------* |@24  5  @24  |*79  8  *79  | 3   6   1   | | 3   6   9   | 1   4   2   | 8   5   7   | | 7   1   8   | 6   3   5   | 4   2   9   | |-------------+-------------+-------------| | 1   4  #56  |*37  9  *37  |#56  8   2   | | 8   3  #57  | 2   1   6   |#57  9   4   | | 9   2  #67  | 8   5   4   |#67  1   3   | |-------------+-------------+-------------| | 5   8   1   |*39  7  *39  | 2   4   6   | | 6   9   3   | 4   2   8   | 1   7   5   | |@24  7  @24  | 5   6   1   | 9   3   8   | *-----------------------------------------*`

You can easily notice this grid yields 8 solutions from the deadly patterns in r19c13, r147c46 & r456c37 respectively.

Assuming r4c6=6, and r5c2=3, you arrive at:
Code: Select all
` *-----------------------------------------* |@24  5  @24  | 7   8   9   | 3   6   1   | | 3   6   9   | 1   4   2   | 8   5   7   | | 7   1   8   | 6   3   5   | 4   2   9   | |-------------+-------------+-------------| | 1   4  #57  | 3   9   6   |#57  8   2   | | 8   3  #56  | 2   1   7   |#56  9   4   | | 9   2  #67  | 8   5   4   |#67  1   3   | |-------------+-------------+-------------| | 5   8   1   | 9   7   3   | 2   4   6   | | 6   9   3   | 4   2   8   | 1   7   5   | |@24  7  @24  | 5   6   1   | 9   3   8   | *-----------------------------------------*`

This grid yields 4 solutions from the DPs in r19c13 & r456c37.

Finally, assuming r4c6=6, and r5c2=6, you arrive at:
Code: Select all
` *-----------------------------------------* |@24  5  @24  |*79  8  *79  | 3   6   1   | | 3   9   6   | 1   4   2   | 8   5   7   | | 7   1   8   | 6   3   5   | 4   2   9   | |-------------+-------------+-------------| | 1   4  *35  |*37  9   6   |*57  8   2   | | 8   6  *35  | 2   1  *37  |*57  9   4   | | 9   2   7   | 8   5   4   | 6   1   3   | |-------------+-------------+-------------| | 5   8   1   |*39  7  *39  | 2   4   6   | | 6   3   9   | 4   2   8   | 1   7   5   | |@24  7  @24  | 5   6   1   | 9   3   8   | *-----------------------------------------*`

This again yields 4 solutions from the UR-style DP in r19c13 and the complex 8-cell BUG-lite-style DP in r1457c3467.

Moral of the story: don't blindly apply uniqueness-based techniques on multiple-solutional puzzles, and don't hastily accuse good programs of malfunctioning.
udosuk

Posts: 2698
Joined: 17 July 2005

Yes, whatever (good) solver we use, we can't solve more than :
Code: Select all
` *-----------* |.5.|.8.|361| |3..|142|857| |718|.3.|429| |---+---+---| |14.|.9.|.82| |8..|...|..4| |92.|854|.13| |---+---+---| |581|.7.|246| |6..|4.8|..5| |.7.|.6.|.38| *-----------*`

These are the cells common to the 19 solutions :
Code: Select all
`452789361396142857718635429145396782863217594927854613581973246639428175274561938452987361396142857718635429143796582865213794927854613581379246639428175274561938254987361396142857718536429145693782863721594927854613581379246632418975479265138254987361396142857718635429143796582865213794927854613581379246639428175472561938254789361396142857718635429145396782863217594927854613581973246639428175472561938254789361396142857718536429143697582865321794927854613581973246632418975479265138254789361396142857718536429143697582865321974927854613581973246632418795479265138452987361369142857718635429145793682837216594926854713581379246693428175274561938452987361369142857718635429146793582835216794927854613581379246693428175274561938452789361369142857718635429147396582835217694926854713581973246693428175274561938452789361369142857718635429145396782836217594927854613581973246693428175274561938452789361369142857718635429145397682837216594926854713581973246693428175274561938452789361369142857718635429146397582835216794927854613581973246693428175274561938254987361369142857718635429145793682837216594926854713581379246693428175472561938254987361369142857718635429146793582835216794927854613581379246693428175472561938254789361369142857718635429147396582835217694926854713581973246693428175472561938254789361369142857718635429145396782836217594927854613581973246693428175472561938254789361369142857718635429145397682837216594926854713581973246693428175472561938254789361369142857718635429146397582835216794927854613581973246693428175472561938.5..8.3613..142857718.3.42914..9..828.......492.854.13581.7.2466..4.8..5.7..6..38`

JPF
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

### I can see cleeeearly now ....

Thank you all for your fast and precise answers. I'm not into multi-solutional sudokus now. I posted this only, because I saw such a pattern like below for the first time. Usually the easy multi-solutional sudokus are ending up in some rectangles without candidates solving them like Udosuk and JPF demonstated impressively while listing all the solutions and possibilities to get on them. Se everyone will know at the first glance that a sudoku is multi-solutional. But this one seemed to be very special because despite of having multiple solutions it's structure gives you two clear hints how to insert one number in order to find a final solution.

Code: Select all
`*--------------------------------------------------*  | 2    5    4    | *79  8    *79  | 3    6    1    |  | 3    9    6    | 1    4    2    | 8    5    7    |  | 7    1    8    | 5    3    6    | 4    2    9    |  |----------------+----------------+----------------|  | 1    4    *35  | 6    9    *37  |*57   8    2    |  | 8    6    *35  | *37  2    1    |*57+9 79   4    |  | 9    2    7    | 8    5    4    | 6    1    3    |  |----------------+----------------+----------------|  | 5    8    1    | *39  7    *39  | 2    4    6    |  | 6    3    2    | 4    1    8    | 79   79   5    |  | 4    7    9    | 2    6    5    | 1    3    8    |  *--------------------------------------------------* `

And these two hints are in r5c7 the decepting bogus-pattern looking like a BUG Type 1 and like a unique rectangle Type 1 while in fact they aren't such. When I saw it, I was wandering: should I insert in r5c7 the 5 for solving the bogus-Unique rectangle - or instead insert the 7 because this 7 looked like the candidate solving the at the first glance presumed BUG-pattern?

So I guess the secret is, that if you apply Uniqueness strategies to multi-solutional sudokus, you will reach in some special cases a solution without knowing, that there are other solutions like the explainer did and like I did in this case before checking it by Simple Sudoku.

So now I'm sure that even the first unique rectangle found by me and the Explainer in AC19 upon 2 and 4 was not so unique in fact. Instead of the 9 in r9c3 a 4 or a 2 could be placed as well. Udosuk showed this in one of the 19 solutions. This bogus-unique rectangle is indeed responsible for finally putting the 2 in r5c5 reducing thus the number of the solutions from 19 to 3. And why should Simple Sudoku take into consideration unique rectangles when in fact there are no such? Thus the number of the solutions of Simple Sudoku is now reasonable for me.

Yes, it is still multisolutional, but forgive me, I was just fascinated.

Claudia
Last edited by claudiarabia on Sat Aug 18, 2007 2:08 pm, edited 1 time in total.
claudiarabia

Posts: 288
Joined: 14 May 2006

udosuk wrote:You can't apply UR (type 1) on a puzzle with multiple solutions!

Well I guess in principle you can, as long as you understand that in doing so you are throwing away an even number of solutions. In this case, there are an odd number of solutions, so you will never be put into a position of being left with no solutions. However, if the puzzle had 18 solutions, it might have been the case that using the UR (type 1) would have made the puzzle completely unsolvable.
re'born

Posts: 551
Joined: 31 May 2007

### Unsolvable by using UR (type 1)?

re'born wrote:
udosuk wrote:You can't apply UR (type 1) on a puzzle with multiple solutions!

Well I guess in principle you can, as long as you understand that in doing so you are throwing away an even number of solutions. In this case, there are an odd number of solutions, so you will never be put into a position of being left with no solutions. However, if the puzzle had 18 solutions, it might have been the case that using the UR (type 1) would have made the puzzle completely unsolvable.

Hmm, interesting question.

If the application of UR (type 1) would lead to an unsolvable pattern, then the puzzle is likely to be unsolvable at all. Usually logical strategies shouldn't lead to deadly contradictions.

Claudia
claudiarabia

Posts: 288
Joined: 14 May 2006

re'born wrote:
udosuk wrote:You can't apply UR (type 1) on a puzzle with multiple solutions!

Well I guess in principle you can, as long as you understand that in doing so you are throwing away an even number of solutions. In this case, there are an odd number of solutions, so you will never be put into a position of being left with no solutions. However, if the puzzle had 18 solutions, it might have been the case that using the UR (type 1) would have made the puzzle completely unsolvable.

That depends on what your goal is. Because you can't know how many solutions a multiple-solutional puzzle has you surely can't decide if the number is odd or even. Suppose it's a crappy source of Sudoku puzzles and your only goal is to find one of the solution, any one. Then the only way I can see your "principle" work is to firstly use programs such as Simple Sudoku to count the number of solutions first, then if it turns out to be odd you work on it and use UR whenever appropriate. That way sooner or later you'll find one of the solutions. But I highly doubt if this whole practice is meaningful at all.
udosuk

Posts: 2698
Joined: 17 July 2005

### Uniqueness shortens the way to validity

Once I bought a sudoku-book and found out that nearly all the sudokus there were multisolutional. It was written in the preface that there were some but not, that with exception of one or two they were all multisolutional.

Thus I started making them valid with the help of SE. I tried to put as few clues as possible in order to get a valid solution. Now I think that using uniqueness is one way to find such crucial clues to archieve this aim quickly.

When I think of re'borns remark that it is dangerous to use uniqueness, when the number of solutions is even, then I propose to exhaust at first all the "simple" strategies like Pointing, Claiming (locked candidates), placing singles and pairs or triplets. Afterwards turbot-fishes, X-Wings Only if this is not working anymore then I would take resort to uniqueness and then it wouldn't mess anything. If you use all the aforesaid strategies, then the 2-solution rectangle will mostly come out and you will clearly see, that you can't use URs there. But if such a 2-solution-rectangle is not being carved out by other strategies, well - uniqueness shortens the way to the final validity because it connects at least two cell groups which would be torn apart without uniqueness so that you would need one clue more to fix them both.

I would care about multi-solutional sudokus in this regard only, when there are no more then, say 30 solutions or when approximately 20 cells remain undefined. Otherwise it mutates from sudoku-solving to sudoku-building and for that I prefere an empty grid.

Claudia
claudiarabia

Posts: 288
Joined: 14 May 2006

### Re: Uniqueness shortens the way to validity

Claudia
I agree with you that techniques based on the asumption of Uniqueness are dangerous. One can never be sure that a puzzle has a unique solution, even when it is claimed to have this property. In my book, I showed that the example of a BUG in Andrew's book (a book I consider among the best) has 3 solutions.
Many proposed puzzles are prososed as having a unique solution, but if the author checked uniqueness using the uniqueness assumption, that's a vicious circle. That's why many incorrect puzzles are published.

Notice that I'm not excluding any rule based on uniqueness, as a last resort weapon, just before T&E.
It's true that such rules can simplify the solution. But I currently have no example of a puzzle that SudoRules (my solver, implementing the rules described in other threads) can't solve without Uniqueness rules and that it could solve when I add them.
denis_berthier
2010 Supporter

Posts: 1261
Joined: 19 June 2007
Location: Paris

Denis,

When you enter a Sudoku into a computer program, such as Simple Sudoku, SudoCue or the Sudoku program by Pappocom, it will first validate the puzzle with a straightforward backtracking algorithm. The program will warn the user if the puzzle has multiple solutions.

After a puzzle has been validated, I see no reason to treat uniqueness-based techniques different from other techniques. Their ranking should not be based on the danger they no longer present to this puzzle, but on how easy it is to spot these patterns relative to those of other techniques. Several uniqueness-based techniques use easy-to-recognize patterns and deserve a spot before complex chains.

If the puzzle is unverified or known to have multiple solutions, uniqueness-based techniques should never be used by the program, not even as a last resort weapon. T&E would be safer to use.
Ruud

Posts: 664
Joined: 28 October 2005

re'born wrote:you understand that in doing so you are throwing away an even number of solutions

Not necessarily:
Code: Select all
`. .  .   |. .  . |. . . . .  .   |. .  . |. . . . .  .   |. .  . |. . . ---------+-------+-----. .  .   |. .  . |. . . . 12 12  |. .  . |. . . . .  .   |. .  . |. . . ---------+-------+-----. .  .   |. .  . |. . . . 12 1234|. 13 . |. . . . .  13  |. 13 . |. . . `

applying UR type 1 twice eliminates 3 solutions because of the overlap.
Once upon a time I was a teenager who was active on here 2007-2011
ocean and eleven should have paired up to make a sudoku-solving duo called Ocean's Eleven
999_Springs

Posts: 420
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Ruud wrote:If the puzzle is unverified or known to have multiple solutions, uniqueness-based techniques should never be used by the program, not even as a last resort weapon. T&E would be safer to use.

T&E is safer?

As far as I can see uniqueness can only lead to possible correct answers.

Show me a case where uniqueness eliminates a solution that MAY be valid, and does not present an alternate solution, no less correct.

T&E will present many not possible "solutions".
wintder

Posts: 297
Joined: 24 April 2007

### Re: Uniqueness shortens the way to validity

denis_berthier wrote:Claudia
It's true that such rules can simplify the solution. But I currently have no example of a puzzle that SudoRules (my solver, implementing the rules described in other threads) can't solve without Uniqueness rules and that it could solve when I add them.

I think this one would qualify:
Code: Select all
`+-------+-------+-------+| 1 . . | . 6 . | . . 5 || . 9 . | . . 2 | . 7 . || . . . | 8 . . | 3 . . |+-------+-------+-------+| . . 2 | 1 . . | . 4 . || 4 . . | . . . | . . 8 || . 8 . | . . 9 | 6 . . |+-------+-------+-------+| . . 7 | . . 4 | . . . || . 3 . | 6 . . | . 1 . || 5 . . | . 2 . | . . 9 |+-------+-------+-------+`

There exists a uniqueness technique that guarantees r3c3=r5c5=r7c7=5, and r6c4=r4c6={3,7}, the rest is singles.
Mauricio

Posts: 1174
Joined: 22 March 2006

Next