a multisolutional sudoku solved by uniqueness

Advanced methods and approaches for solving Sudoku puzzles

a multisolutional sudoku solved by uniqueness

Postby claudiarabia » Sat Aug 18, 2007 11:50 am

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

Postby ronk » Sat Aug 18, 2007 12:17 pm

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

Postby re'born » Sat Aug 18, 2007 12:29 pm

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

Postby udosuk » Sat Aug 18, 2007 3:31 pm

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

Postby JPF » Sat Aug 18, 2007 3:52 pm

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
452789361396142857718635429145396782863217594927854613581973246639428175274561938
452987361396142857718635429143796582865213794927854613581379246639428175274561938
254987361396142857718536429145693782863721594927854613581379246632418975479265138
254987361396142857718635429143796582865213794927854613581379246639428175472561938
254789361396142857718635429145396782863217594927854613581973246639428175472561938
254789361396142857718536429143697582865321794927854613581973246632418975479265138
254789361396142857718536429143697582865321974927854613581973246632418795479265138
452987361369142857718635429145793682837216594926854713581379246693428175274561938
452987361369142857718635429146793582835216794927854613581379246693428175274561938
452789361369142857718635429147396582835217694926854713581973246693428175274561938
452789361369142857718635429145396782836217594927854613581973246693428175274561938
452789361369142857718635429145397682837216594926854713581973246693428175274561938
452789361369142857718635429146397582835216794927854613581973246693428175274561938
254987361369142857718635429145793682837216594926854713581379246693428175472561938
254987361369142857718635429146793582835216794927854613581379246693428175472561938
254789361369142857718635429147396582835217694926854713581973246693428175472561938
254789361369142857718635429145396782836217594927854613581973246693428175472561938
254789361369142857718635429145397682837216594926854713581973246693428175472561938
254789361369142857718635429146397582835216794927854613581973246693428175472561938
.5..8.3613..142857718.3.42914..9..828.......492.854.13581.7.2466..4.8..5.7..6..38

JPF
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

I can see cleeeearly now ....

Postby claudiarabia » Sat Aug 18, 2007 5:47 pm

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

Postby re'born » Sat Aug 18, 2007 6:07 pm

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)?

Postby claudiarabia » Sat Aug 18, 2007 6:17 pm

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

Postby udosuk » Sun Aug 19, 2007 6:49 am

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

Postby claudiarabia » Sun Aug 19, 2007 10:36 am

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

Postby denis_berthier » Sat Aug 25, 2007 7:07 am

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: 3967
Joined: 19 June 2007
Location: Paris

Postby Ruud » Sat Aug 25, 2007 9:54 am

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

Postby 999_Springs » Sat Oct 20, 2007 8:03 pm

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.
999_Springs
 
Posts: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby wintder » Sat Oct 20, 2007 9:06 pm

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.
T&E usually leads to wrong 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

Postby Mauricio » Sat Oct 20, 2007 10:13 pm

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: 1175
Joined: 22 March 2006

Next

Return to Advanced solving techniques

cron