The New Sudoku Players' Forum

[ghfick]

Thanks to Jason, champagne and David for their responses.
I believe that Andrew Stuart's solver uses a brute force algorithm to enumerate all the solutions.
The first puzzle in the 'Multiple Solutions?' thread is :
6.4.925.15.9.1.....2....7..4.2.3.......2.1.4.813..592..4.38.6.53..1..2.8..7.2.3..

Using Andrew's solver, we uncheck BUG, Unique Rectangles, Extended Unique Rectangles and Hidden Unique Rectangles, then advance the puzzle as far as his solver will go. This gives:
6.4.925.15.9.1.4.2128.5.7.9462938157795261843813..592624138.6.53561..2.8987526314

with C=3 solutions:
634792581579813462128654739462938157795261843813475926241387695356149278987526314
634792581579813462128654739462938157795261843813475926241389675356147298987526314
674892531539617482128453769462938157795261843813745926241389675356174298987526314

Andrew's solver shows all the incomplete cells with their candidates:

Code: Select all

+--------------+--------------+--------------+
|    6  37   4 |   78   9   2 |    5  38   1 |
|    5  37   9 |   68   1  37 |    4  68   2 |
|    1   2   8 |   46   5  34 |    7  36   9 |
+--------------+--------------+--------------+
|    4   6   2 |    9   3   8 |    1   5   7 |
|    7   9   5 |    2   6   1 |    8   4   3 |
|    8   1   3 |   47  47   5 |    9   2   6 |
+--------------+--------------+--------------+
|    2   4   1 |    3   8  79 |    6  79   5 |
|    3   5   6 |    1  47 479 |    2  79   8 |
|    9   8   7 |    5   2   6 |    3   1   4 |
+--------------+--------------+--------------+


So r1c2 must be either 3 or 7, r1c4 must 7 or 8 and so on. The usual Sudoku rules determine the additional constraints. So, if r1c2=3, then r1c8=8, r1c4=7 and first band fills in. Now r7c8 must be either 7 or 9. r7c8=7 gives the first solution and r7c8=9 gives the second solution. Now, if r1c2=7, we get the third solution.

Now, if we had used UR with this puzzle, we would note r78c68 => r8c6=4 which would reveal the third solution and [more importantly] conceal the first two solutions.

I am now on the hunt for some other examples

Best Wishes
Gordon

[ghfick]

Hi David,

Here is a puzzle with exactly 2 solutions:

1.....58.8....1..6.6..2.......59........7.....93..2....1....8.4...9.7.5.6..2..71.

1....958.8....1..6.6..2.......59.....8..73....93..2....17...8.4..891765.6..28471.

132469587874351926965728431421596378586173249793842165217635894348917652659284713
174639582852741396369825147746598231281473965593162478917356824428917653635284719

Code: Select all

+--------------+--------------+--------------+
|    1  37  24 |   46  36   9 |    5   8  27 |
|    8  57  24 |   37  45   1 |   39  29   6 |
|   39   6  59 |   78   2  58 |   14  34  17 |
+--------------+--------------+--------------+
|   47  24  16 |    5   9  68 |   23  37  18 |
|   25   8  16 |   14   7   3 |   29  46  59 |
|   57   9   3 |   18  46   2 |   14  67  58 |
+--------------+--------------+--------------+
|   29   1   7 |   36  35  56 |    8  29   4 |
|   34  24   8 |    9   1   7 |    6   5  23 |
|    6  35  59 |    2   8   4 |    7   1  39 |
+--------------+--------------+--------------+


So even numbered solution counts are possible.

Best
Gordon

[ghfick]

Also with this puzzle, none of the uniqueness methods advance the puzzle. UR does not conceal one of the solutions. So I am still on the hunt.
Gordon

[blue]

The first puzzle in the 'Multiple Solutions?' thread is :
6.4.925.15.9.1.....2....7..4.2.3.......2.1.4.813..592..4.38.6.53..1..2.8..7.2.3..

(...)

Andrew's solver shows all the incomplete cells with their candidates:

Code: Select all

+--------------+--------------+--------------+
|    6  37   4 |   78   9   2 |    5  38   1 |
|    5  37   9 |   68   1  37 |    4  68   2 |
|    1   2   8 |   46   5  34 |    7  36   9 |
+--------------+--------------+--------------+
|    4   6   2 |    9   3   8 |    1   5   7 |
|    7   9   5 |    2   6   1 |    8   4   3 |
|    8   1   3 |   47  47   5 |    9   2   6 |
+--------------+--------------+--------------+
|    2   4   1 |    3   8  79 |    6  79   5 |
|    3   5   6 |    1  47 479 |    2  79   8 |
|    9   8   7 |    5   2   6 |    3   1   4 |
+--------------+--------------+--------------+


(...)

Now, if we had used UR with this puzzle, we would note r78c68 => r8c6=4 which would reveal the third solution and [more importantly] conceal the first two solutions.

Hi Gordon,

There's also:

BUG+1 => r8c6=7, giving the 2nd solution.
BUG-Lite+1 => r8c6=9, giving the 1st solution, where the BUG-Lite cells are all of the cells except r7c6,r78c8.

Cheers,
Blue.

[David P Bird]

Hi Blue,
Your response to Gordon shows that I can't say that applying uniqueness methods to puzzles with an even number of solutions will never find any solution. I must therefore modify that to 'isn't guaranteed to find a solution'.

In my thinking I considered a puzzle where the only reason for one given was to reduce a UR to one solution. If that given was missing a solver would either disrupt the UR making no solution possible, or solve all the other cells leaving two ways of filling it.

On reflection I think it would be extremely difficult to compose a puzzle for my hypothetical case with three URs considering the sort of structure the unavoidable sets would need.

If my suspicions that most puzzles with an even number of solutions through clueless URs will get strangled at birth are right, Gordon will have a difficult job to find one that slipped through. Would it be possible for you to compose one?

David

[Edit] Key word highlighted. Considering people's reactions I'll stay quiet from now on.

[eleven]

I don't understand the purpose of this discussion. Probably i am in a line here with strmchkr.

If you have a multiple solution puzzle, then the pattern, which remains unsolved with non-uniqueness methods is always a MUG (a uniqueness pattern like UR, just more complex), have it 4 cells or 81.

So ghfick's first sample is a MUG with 3 possible solutions (and the second one a BUG/MUG/BUG lite with 2 solutions). If you would apply it, the puzzle would not have a solution.
It is definitely nonsense to apply uniqueness methods on non-unique puzzles. Sometimes you can advance the puzzle without loosing all solutions, that's all (as sometimes you can make a lucky mistake).

Such a MUG may contain smaller uniqueness patterns or not. But for what reason should we investigate that ?

PS: Maybe it could be interesting to know, which solution numbers are impossible. Is this known ?

[David P Bird]

I don't understand the purpose of this discussion

Perhaps you have missed that this thread is in the help section not the advanced solving one.

I don't mind admitting that when I try to explain something it shows up any misconceptions I have acquired, and I for one have benefitted.

[JasonLion]

Perhaps you have missed that this thread is in the help section not the advanced solving one.

None the less, understanding the purpose, or goal, of this line of questioning would help a great deal in being able to formulate answers.

[eleven]

PS: Maybe it could be interesting to know, which solution numbers are impossible. Is this known ?

Ok, a quick test showed, that it is easy to get puzzles with 1 to 100 solutions. So there seems to be no restriction.

I am not sure what David was looking for.
This is a puzzle with 9 solutions, which can be "solved" with a simple UR 69, which kills 8 solutions.
Singles to this grid. There is also a 47 UR, which kills 4 solutions. Then a 13 UR, which kills the other 4.

Code: Select all

+-------------------+-------------------+-------------------+
| 1     5     8     | 3     67    67    | 2     4     9     |
| 47    47    9     | 2     8     1     | 3     5     6     |
| 6     2     3     | 4     9     5     | 1     7     8     |
+-------------------+-------------------+-------------------+
| 3     6     2     | 7     4     8     | 5     9     1     |
| 9     8     7     | 5     1     3     | 6     2     4     |
| 5     14    14    | 69    2     69    | 7     8     3     |
+-------------------+-------------------+-------------------+
| 47    1347  146   | 69    5     679   | 8     13    2     |
| 2     137   16    | 8     67    4     | 9     13    5     |
| 8     9     5     | 1     3     2     | 4     6     7     |
+-------------------+-------------------+-------------------+

.5.3..2.9....813.6...49.....62.4....9...1........2.78.......8.22....4..5..513....
158367249479281356623495178362748591987513624514629783741956832236874915895132467
158367249479281356623495178362748591987513624514926783741659832236874915895132467
158367249479281356623495178362748591987513624541629783714956832236874915895132467
158367249479281356623495178362748591987513624541629783734956812216874935895132467
158367249479281356623495178362748591987513624541926783714659832236874915895132467
158367249479281356623495178362748591987513624541926783734659812216874935895132467
158367249749281356623495178362748591987513624514629783471956832236874915895132467
158367249749281356623495178362748591987513624514926783471659832236874915895132467
158376249749281356623495178362748591987513624514629783436957812271864935895132467

[eleven]

This is a puzzle with 8 solutions, which can be "solved" using URs.

Code: Select all

+-------------------------+-------------------------+-------------------------+
| 178     2       14678   | 68      367     9       | 5       37      14      |
| 57      9       3       | 1       57      4       | 6       8       2       |
| 1578    46      145678  | 268     23567   56      | 9       37      14      |
+-------------------------+-------------------------+-------------------------+
| 9       8       16      | 7       156     56      | 4       2       3       |
| 1357    13      157     | 4       8       2       | 17      9       6       |
| 2       46      1467    | 9       16      3       | 17      5       8       |
+-------------------------+-------------------------+-------------------------+
| 138     13      18      | 5       4       7       | 2       6       9       |
| 4       7       9       | 26      26      8       | 3       1       5       |
| 6       5       2       | 3       9       1       | 8       4       7       |
+-------------------------+-------------------------+-------------------------+

Code: Select all

.2....5....31...82......9...8.7..42......2......9.3.58....4726.4.9..8...65...1..7
824639571593174682167825934981756423735482196246913758318547269479268315652391847
126839574593174682847256931981765423735482196264913758318547269479628315652391847  <- 56
126839574593174682847265931981756423735482196264913758318547269479628315652391847  <- 56  <- 26
126839574593174682847625931981756423735482196264913758318547269479268315652391847         <- 26
126839574793154682845276931981765423537482196264913758318547269479628315652391847  <- 37
126879534793154682845236971981765423537482196264913758318547269479628315652391847  <- 37
127869534593174682846235971981756423735482196264913758318547269479628315652391847  <- 46
127869534593174682864235971981756423735482196246913758318547269479628315652391847  <- 46

[Added, which UR's kill which solutions]

[eleven]

Just to make clear, that also simple UR moves can kill all solutions.
This puzzle
...8.7.1......467.....12.....4.9......9...75.3.85..4....3.4.2.7..5.8....7..2.1...
gets here:

Code: Select all

+----------------+----------------+----------------+
| 49   3    2    | 8    6    7    |#59   1   #459  |
| 89   89   1    | 3    5    4    | 6    7    2    |
| 468  568  7    | 9    1    2    | 58   3    45   |
+----------------+----------------+----------------+
| 5    7    4    | 1    9    8    | 3    2    6    |
| 16   16   9    | 4    2    3    | 7    5    8    |
| 3    2    8    | 5    7    6    | 4    9    1    |
+----------------+----------------+----------------+
| 19   19   3    | 6    4    5    | 2    8    7    |
| 2    4    5    | 7    8    9    | 1    6    3    |
| 7    89   6    | 2    3    1    |#59   4   #59   |
+----------------+----------------+----------------+

If you set r1c9=4, both solutions are killed, and you are left with an invalid puzzle.

[blue]

Hi Blue,
Your response to Gordon shows that I can't say that applying uniqueness methods to puzzles with an even number of solutions will never find any solution. I must therefore modify that to 'isn't guaranteed to find a solution'.

In my thinking I considered a puzzle where the only reason for one given was to reduce a UR to one solution. If that given was missing a solver would either disrupt the UR making no solution possible, or solve all the other cells leaving two ways of filling it.

On reflection I think it would be extremely difficult to compose a puzzle for my hypothetical case with three URs considering the sort of structure the unavoidable sets would need.

If my suspicions that most puzzles with an even number of solutions through clueless URs will get strangled at birth are right, Gordon will have a difficult job to find one that slipped through. Would it be possible for you to compose one?

David

[Edit] Key word highlighted. Considering people's reactions I'll stay quiet from now on.

Hi David,

There's this: MUG+n ... where the MUG has an odd number of solutions, and the n extra candiates, provide a common elimination.

Here's a puzzle with 4 solutions:

.......5..7..8...458.3.9......4..2..6..5.8.....87.1.3......374...36..1...5...7...

Solutions:

Code: Select all

139264857276185394584379621315496278627538419948721536861953742793642185452817963
239164857176285394584379621315496278627538419948721536861953742793642185452817963
319264857276185394584379621135496278627538419948721536861953742793642185452817963
329164857176285394584379621915436278637528419248791536861953742793642185452817963

After singles, it's:

..9.64857.76.85394584379621..54.62786.75.8419.487.1536861953742793642185452817963

Line of sight eliminations reduce the PMs to the following:

Code: Select all

+-------------+-----------+---------+
| 123  123  9 | 12  6   4 | 8  5  7 |
| 12   7    6 | 12  8   5 | 3  9  4 |
| 5    8    4 | 3   7   9 | 6  2  1 |
+-------------+-----------+---------+
| 139  13   5 | 4   39  6 | 2  7  8 |
| 6    23   7 | 5   23  8 | 4  1  9 |
| 29   4    8 | 7   29  1 | 5  3  6 |
+-------------+-----------+---------+
| 8    6    1 | 9   5   3 | 7  4  2 |
| 7    9    3 | 6   4   2 | 1  8  5 |
| 4    5    2 | 8   1   7 | 9  6  3 |
+-------------+-----------+---------+

[ Whether it's relevant or not ... each candidate in an unsolved cell, corresponds to one of the cell values in the solution list. ]

Embedded in the PM's is a 3-solution MUG (DP) -- one that's simple enough to be recognizable:

Code: Select all

+------------+----------+
| 123  13  . | 12  .  . |
| 12   .   . | 12  .  . |
| .    .   . | .   .  . |
+------------+----------+
| 13   13  . | .   .  . |
| .    .   . | .   .  . |
| .    .   . | .   .  . |
+------------+----------+

With that, there's a MUG+2 pattern, that can be used to eliminate 2r5c2, leaving a PM grid that's solvable by singles, giving the 4th solution above.

Code: Select all

+-----------------+------------+---------+
| *123   *13+2  9 | *12  6   4 | 8  5  7 |
| *12     7     6 | *12  8   5 | 3  9  4 |
|  5      8     4 |  3   7   9 | 6  2  1 |
+-----------------+------------+---------+
| *13+9  *13    5 |  4   39  6 | 2  7  8 |
|  6      3-2   7 |  5   23  8 | 4  1  9 |
|  (29)   4     8 |  7   29  1 | 5  3  6 |
+-----------------+------------+---------+
|  8      6     1 |  9   5   3 | 7  4  2 |
|  7      9     3 |  6   4   2 | 1  8  5 |
|  4      5     2 |  8   1   7 | 9  6  3 |
+-----------------+------------+---------+

  DP
  ||
2r1c2 -----------
  ||              \
9r4c1 - (9=2)r6c1 - 2r5c2

Best Regards,
Blue.

P.S.: Looking at this again, I suppose you could say that rather than being a way to avoid the 3-solution DP, it's a way of simultaneously avoiding two UR's. To avoid 12r12c14, r1c1 must be 3, and to avoid 13r14c12, one of 2r1c12,9r4c1 must be true. Since r1c1=3 means r1c1 can't be a 2, all together we'ld need r1c1 to be 3, and one of 2r1c2,9r4c1 to be true ... leading to the same elimination.

[eleven]

It turns out, that my 8 solution sample above also has such an overlapping UR, which kills 3 (of 4 remainung) solutions.

Code: Select all

+----------------+----------------+----------------+
| 18   2    46   | 68   3    9    | 5    7    14   |
| 5    9    3    | 1    7    4    | 6    8    2    |
| 18   46   7    |#26+8 #256 #56  | 9    3    14   |
+----------------+----------------+----------------+
| 9    8    1    | 7   #56  #56   | 4    2    3    |
| 7    3    5    | 4    8    2    | 1    9    6    |
| 2    46   46   | 9    1    3    | 7    5    8    |
+----------------+----------------+----------------+
| 3    1    8    | 5    4    7    | 2    6    9    |
| 4    7    9    |#26  #26   8    | 3    1    5    |
| 6    5    2    | 3    9    1    | 8    4    7    |
+----------------+----------------+----------------+

[eleven]

Just for fun. How to solve a 15 solutions puzzle manually.

..36..7...9..8..6..25......2.......14......8.3..9...24..7.2.3.9.4...8.7.....7.4..

With basics, then a w-wing (15-> -5r5c6) and a small chain (5r6c7=r4c7-(5=7)r4c2-r6c2=r6c6 -> -5r6c6) come here:

Code: Select all

+-------------------+-------------------+-------------------+
| 1     8     3     | 6     45    2459  | 7     49    25    |
| 7     9     4     | 25    8     3     | 1     6     25    |
| 6     2     5     | 7     14    149   | 8     49    3     |
+-------------------+-------------------+-------------------+
| 2     57    69    | 8     456   457   | 569   3     1     |
| 4     15    69    | 125   3     12    | 69    8     7     |
| 3     157   8     | 9     156   17    | 56    2     4     |
+-------------------+-------------------+-------------------+
| 8     6     7     | 4     2     15    | 3     15    9     |
| 5     4     1     | 3     9     8     | 2     7     6     |
| 9     3     2     | 15    7     6     | 4     15    8     |
+-------------------+-------------------+-------------------+

Now split it somewhere.

(1) r5c6=1

Code: Select all

+----------------+----------------+----------------+
| 1    8    3    | 6    4    2    | 7    9    5    |
| 7    9    4    | 5    8    3    | 1    6    2    |
| 6    2    5    | 7    1    9    | 8    4    3    |
+----------------+----------------+----------------+
| 2    7    69   | 8    56   4    | 569  3    1    |
| 4    5    69   | 2    3    1    | 69   8    7    |
| 3    1    8    | 9    56   7    | 56   2    4    |
+----------------+----------------+----------------+
| 8    6    7    | 4    2    5    | 3    1    9    |
| 5    4    1    | 3    9    8    | 2    7    6    |
| 9    3    2    | 1    7    6    | 4    5    8    |
+----------------+----------------+----------------+

3 solutions

(2) r5c6=2, r4c7=5

Code: Select all

+-------------+-------------+-------------+
| 1   8   3   | 6   45  59  | 7   49  2   |
| 7   9   4   | 2   8   3   | 1   6   5   |
| 6   2   5   | 7   14  19  | 8   49  3   |
+-------------+-------------+-------------+
| 2   7   9   | 8   6   4   | 5   3   1   |
| 4   15  6   | 15  3   2   | 9   8   7   |
| 3   15  8   | 9   15  7   | 6   2   4   |
+-------------+-------------+-------------+
| 8   6   7   | 4   2   15  | 3   15  9   |
| 5   4   1   | 3   9   8   | 2   7   6   |
| 9   3   2   | 15  7   6   | 4   15  8   |
+-------------+-------------+-------------+

2 solutions
(3) r5c6=2, r4c7<>5, r1c6=5

Code: Select all

+-------------+-------------+-------------+
| 1   8   3   | 6   4   5   | 7   9   2   |
| 7   9   4   | 2   8   3   | 1   6   5   |
| 6   2   5   | 7   1   9   | 8   4   3   |
+-------------+-------------+-------------+
| 2   7   69  | 8   5   4   | 69  3   1   |
| 4   5   69  | 1   3   2   | 69  8   7   |
| 3   1   8   | 9   6   7   | 5   2   4   |
+-------------+-------------+-------------+
| 8   6   7   | 4   2   1   | 3   5   9   |
| 5   4   1   | 3   9   8   | 2   7   6   |
| 9   3   2   | 5   7   6   | 4   1   8   |
+-------------+-------------+-------------+

2 solutions
(3) r5c6=2, r4c7<>5, r1c6<>5

Code: Select all

+-------------+-------------+-------------+
| 1   8   3   | 6   5   49  | 7   49  2   |
| 7   9   4   | 2   8   3   | 1   6   5   |
| 6   2   5   | 7   1   49  | 8   49  3   |
+-------------+-------------+-------------+
| 2   57  69  | 8   4   57  | 69  3   1   |
| 4   15  69  | 15  3   2   | 69  8   7   |
| 3   17  8   | 9   6   17  | 5   2   4   |
+-------------+-------------+-------------+
| 8   6   7   | 4   2   15  | 3   15  9   |
| 5   4   1   | 3   9   8   | 2   7   6   |
| 9   3   2   | 15  7   6   | 4   15  8   |
+-------------+-------------+-------------+

8 solutions (2x2x2)

PS: Ok, nothing new, JC already did it here

[ghfick]

Blue: I was not that familiar with the term 'Bug Lite' so I looked it up and found:
http://www.sudoku9981.com/sudoku-solving/bug-lite.php
So-called 'Deadly Formations' [would formation be better than pattern?] should be in the human solver's lexicon, especially those that are made up of only bi-value cells.
I now see we also have MUG [Multi-Value Universal Grave] and so I found:
layered-bug-lite-t4432.html
Again MUGs could be findable by humans but slightly tougher, for sure.
The examples found are very helpful. Is there a place that gives precise definitions for these terms?

eleven: You make it clear that any solution count is possible though clearly finite. I suppose the empty puzzle has the maximum solution count. [combinatorics here?]. I wonder what the maximum solution count would be for a puzzle with 17+ givens? Could you please post a list of 100 puzzles with the first hundred solution counts? It would be interesting to explore such a list to see how the various paths [which include uniqueness strategies] conceal solutions.
Regarding the puzzle: ...8.7.1......467.....12.....4.9......9...75.3.85..4....3.4.2.7..5.8....7..2.1...
One can take the path further using only non-uniqueness methods to the very end where there the puzzle is solved except for the four bi-value cells [59] in r19c78. One can then see the 2 solutions. The earlier use of UR is intriguing.

David: Understanding the structures in play with these multi solution puzzles does have even/odd issues. I suspect there are other issues to tease us.

Jason: I definitely agree that the study of the 'Sudokus of Shame' is largely a side issue and that our interests should focus on puzzles with unique solutions.