The New Sudoku Players' Forum

[r.e.s.]

In solving any unique-solution "non-basic" sudoku, eventually there will be a "last non-basic stage" such that the next candidate elimination leaves only naked/hidden singles. I'm looking for puzzles with a solution-path such that the last non-basic stage has as few unsolved cells as possible (i.e. the number of singles in the "end-game" is a minimum). If puzzles tie at this number, those that further minimize the total number of candidates in the last non-basic stage are preferred.

Could anyone please post a puzzle or two that they believe might be at this minimum?

[RW]

Here's one with 16 empty cells that require a BUG-lite or one x-wing+one xy-wing (or BUG+1). Can't remember seeing any with fewer cells. Looking through the BUG trails might give some result. I tried to examine the candidate grid to find out what makes this setup not solvable by singles and if it could be reduced to a smaller size setup, but I just can't figure it out right now...

I'm sorry, I don't have the initial puzzle.

Code: Select all

 *-----------------------------------------------------------*
 | 4     57    2     | 1     6     8     | 57    3     9     |
 | 1     3     67    | 57    9     2     | 567   4     8     |
 | 8     567   9     | 57    3     4     | 2567  1     27    |
 |-------------------+-------------------+-------------------|
 | 6     8     5     | 3     4     9     | 12    7     12    |
 | 7     4     1     | 2     8     5     | 9     6     3     |
 | 2     9     3     | 6     7     1     | 4     8     5     |
 |-------------------+-------------------+-------------------|
 | 5     2     4     | 8     1     7     | 3     9     6     |
 | 3     17    8     | 9     2     6     | 17    5     4     |
 | 9     167   67    | 4     5     3     | 8     2     17    |
 *-----------------------------------------------------------*

RW

[r.e.s.]

RW -
Thanks for the speedy reply! The best I've been able to do so far is this one, with 12 end-game singles, and 27 last-nonbasic-stage candidates (4 distinct candidate values) -- sorry, I should have posted this at the beginning :

Code: Select all

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

Code: Select all

+-------------+-------------+-------------+
| 5   4   37  | 78  378 6   | 2   1   9   |
| 2   8   79  | 1   79  5   | 6   4   3   |
| 39  6   1   | 4   39  2   | 8   7   5   |
+-------------+-------------+-------------+
| 8   3   5   | 2   4   7   | 1   9   6   |
| 1   9   6   | 3   5   8   | 7   2   4   |
| 4   7   2   | 9   6   1   | 5   3   8   |
+-------------+-------------+-------------+
| 79  1   89  | 6   78  4   | 3   5   2   |
| 37  5   38  | 78  2   9   | 4   6   1   |
| 6   2   4   | 5   1   3   | 9   8   7   |
+-------------+-------------+-------------+

(An xy-wing gives 7[14] is False; or, a BUG gives 7[15] is True.)

If the last nonbasic "move" is setting a candidate to True, as in the BUG -- rather than setting one to False, as in the xy-wing -- I suppose the number of end-game singles in this puzzle is 12, rather than 13.

[tso]

From the "Dead easy -- but beyond logic" thread of sudoku.org.uk forum
{ dead link www.sudoku.org.uk/discus/messages/29/51.html?1117005685 }
The question is similar.

Code: Select all

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

Code: Select all

 *--------------------------------------------------*
 | 2    5    8    | 1    69   4    | 69   3    7    |
 | 9    3    6    | 8    2    7    | 5    1    4    |
 | 4    7    1    | 5    3    69   | 2    8    69   |
 |----------------+----------------+----------------|
 | 7    1    5    | 2    89   3    | 689  4    69   |
 | 8    4    9    | 6    7    5    | 3    2    1    |
 | 3    6    2    | 4    1    89   | 89   7    5    |
 |----------------+----------------+----------------|
 | 1    2    4    | 9    68   68   | 7    5    3    |
 | 5    9    3    | 7    4    2    | 1    6    8    |
 | 6    8    7    | 3    5    1    | 4    9    2    |
 *--------------------------------------------------*

I don't know what the original puzzle looked like or if this was constructed as is. Anyway, after BUG places a 9 in the last tri-value cell, 10 singles remain.

[r.e.s.]

Thanks, tso -- I knew I'd read something about this somewhere/somewhen! It'll be very interesting if the minimum turns out to be less than 10. I decided to make a puzzle out of it (don't know if it's minimal-clue):

Code: Select all

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

Interestingly, every bivalue cell in the last-nonbasic stage can also be solved by a 5- or 6-link xy-chain, also leaving 10 singles in each case.

Edit: Removed an erroneous comment about xy-chains leaving only 12 singles in my 13-cell example.

[Ocean]

Here is one with a 'coloring' step after 70 cells are filled in, where the coloring removes five candidates:

Code: Select all

 *-----------*
 |...|...|...|
 |..1|.2.|3..|
 |.3.|4.5|.6.|
 |---+---+---|
 |..2|...|1..|
 |.7.|...|.4.|
 |..3|...|8..|
 |---+---+---|
 |.4.|8.6|.7.|
 |..5|.1.|9..|
 |...|...|...|
 *-----------*

 *-----------*
 |2.4|361|78.|
 |..1|728|3.4|
 |837|495|261|
 |---+---+---|
 |4.2|.83|1.7|
 |978|152|643|
 |.13|.47|82.|
 |---+---+---|
 |149|836|572|
 |785|214|936|
 |326|579|418|
 *-----------*

 Here: 70 cells finished:
 *--------------------------------------------------*
 | 2    59   4    | 3    6    1    | 7    8    59   |
 | 56   569  1    | 7    2    8    | 3    59   4    |
 | 8    3    7    | 4    9    5    | 2    6    1    |
 |----------------+----------------+----------------|
 | 4    56   2    | 69   8    3    | 1    59   7    |
 | 9    7    8    | 1    5    2    | 6    4    3    |
 | 56   1    3    | 69   4    7    | 8    2    59   |
 |----------------+----------------+----------------|
 | 1    4    9    | 8    3    6    | 5    7    2    |
 | 7    8    5    | 2    1    4    | 9    3    6    |
 | 3    2    6    | 5    7    9    | 4    1    8    |
 *--------------------------------------------------*

 After 'Color elimination' of 5s:
 *--------------------------------------------------*
 | 2    9    4    | 3    6    1    | 7    8    59   |
 | 6    569  1    | 7    2    8    | 3    9    4    |
 | 8    3    7    | 4    9    5    | 2    6    1    |
 |----------------+----------------+----------------|
 | 4    6    2    | 69   8    3    | 1    59   7    |
 | 9    7    8    | 1    5    2    | 6    4    3    |
 | 56   1    3    | 69   4    7    | 8    2    9    |
 |----------------+----------------+----------------|
 | 1    4    9    | 8    3    6    | 5    7    2    |
 | 7    8    5    | 2    1    4    | 9    3    6    |
 | 3    2    6    | 5    7    9    | 4    1    8    |
 *--------------------------------------------------*

[Ruud]

I remember we had a similar discussion a couple of months ago. I tried to search for that thread but cannot find it.
Does anyone remember where it is? Maybe on another forum?

Anyway,

I've programmed my solver in such a way that advanced techniques never place digits. They only eliminate candidates, where basic FN techniques then pick up the singles.

For a valid sudoku, 70 placements seems to be the maximum. Any advancement will reduce the puzzle to singles. I've tested my entire collection, and never found a puzzle that exceeds this 70 limit.

Ruud.

[r.e.s.]

Ocean, one thing your puzzle brings out is an ambiguity in the final nonbasic "move". In Simple Sudoku, for example, the coloring step leaves a naked single in every cell in which there was an elimination -- in which case there will be 11 remaining singles ...

Code: Select all

 *--------------------------------------------------*
 | 2   [9]    4   | 3    6    1    | 7    8   [59]  |
 |[6]  [569]  1   | 7    2    8    | 3   [9]   4    |
 | 8    3    7    | 4    9    5    | 2    6    1    |
 |----------------+----------------+----------------|
 | 4   [6]    2   |[69]   8    3   | 1   [59]  7    |
 | 9    7    8    | 1     5    2   | 6    4    3    |
 |[56]   1    3   |[69]   4    7   | 8    2   [9]   |
 |----------------+----------------+----------------|
 | 1    4    9    | 8    3    6    | 5    7    2    |
 | 7    8    5    | 2    1    4    | 9    3    6    |
 | 3    2    6    | 5    7    9    | 4    1    8    |
 *--------------------------------------------------*

It seems I made a similar "mistake" when I said the xy-chains in my 13-cell example would leave only 12 singles -- only the BUG manages to do that, I guess.

[r.e.s.]

Hi Ruud,

I remember we had a similar discussion a couple of months ago. I tried to search for that thread but cannot find it.
Does anyone remember where it is? Maybe on another forum?

I don't think I've seen it, but would be interested.

I've programmed my solver in such a way that advanced techniques never place digits. They only eliminate candidates, where basic FN techniques then pick up the singles.

I see why in most cases you might want to do that, but I wonder if some logic that sets a candidate True might not pick up cases otherwise missed. I'm thinking mostly about forcing chains in the two complementary forms (like <here>) -- if I'm not mistaken, sometimes the form that makes a placement can be used when the other cannot be, and vice versa.

For a valid sudoku, 70 placements seems to be the maximum. Any advancement will reduce the puzzle to singles. I've tested my entire collection, and never found a puzzle that exceeds this 70 limit.

Very interesting, thanks!

[JPF]

I remember we had a similar discussion a couple of months ago. I tried to search for that thread but cannot find it.
Does anyone remember where it is? Maybe on another forum?

Are you thinking about this thread ?

For a valid sudoku, 70 placements seems to be the maximum. Any advancement will reduce the puzzle to singles. I've tested my entire collection, and never found a puzzle that exceeds this 70 limit.

I made earlier a similar (?) observation in this post

I'd like to make an observation.

It seems to be impossible to find a puzzle starting with singles only, until n cells are known and stopping after, for 70 < n < 81.
Does anybody have an explanation for that ?
or is it not true ?
JPF

A different way to say it :
If a puzzle is "singles-only" until 70 cells are known, then it is an "all singles" one.

Are we speaking about the same thing ?


JPF

[Ruud]

Are you thinking about this thread ?

Yes, that's the one. Thanks. That was a very interesting discussion.

A different way to say it :
If a puzzle is "singles-only" until 70 cells are known, then it is an "all singles" one.

Are we speaking about the same thing?

Yes. That's another way to look at it. You can also say that is is not possible to have less than 11 unbound cells without a single.

The way I see it, you need at least 11 unbound cells to form a pattern that is not deadly. The minimum number of digits involved in this pattern is 3.

Ruud.

[r.e.s.]

I made earlier a similar (?) observation in this post

I'd like to make an observation.

It seems to be impossible to find a puzzle starting with singles only, until n cells are known and stopping after, for 70 < n < 81.
Does anybody have an explanation for that ?
or is it not true ?
JPF

I haven't read all 15 pages of that thread, but istm there's really not much to explain. There must be some minimum number of unsolved cells ([at most 11, it seems]) in order to host a structure "complex" enough to involve no singles. Such a structure just can't show up any longer if fewer than that minimum number of cells remain.

That was actually the reason for my original posting -- I was curious to see what these "least complex" nonbasic logic structures would be. gsf's remark in the "Cascading Singles" thread (thanks for the link!) was especially interesting in this regard (my emphasis added):

so I agree with the count of 11
I checked 225M puzzles, 11 was the minimum singles cascade, there were 1771 of them, and all were preceded by an x-cycle

There's probably some nice proof that that's the way it has to happen.

(Sorry, Ruud -- our posts crossed.)

[Edit: I'd written "at least 11" by mistake.]

[gsf]

so I agree with the count of 11
I checked 225M puzzles, 11 was the minimum singles cascade, there were 1771 of them, and all were preceded by an x-cycle

I may have attributed a candidate removal due to the x-cycle to the singles

for oceans example above 3 x-cycles on candidate 5 can progress the puzzle before the cascade
if all 3 are applied then the cascade is 8 singles
if a shortest is applied then the cascade is 10

but an x-cycle progression can be one or more cells
in my implementation the x-cycle eliminates or assigns just one candidate
and lets the subsequent singles constraint find the rest that
could have been determined by running round the cycle

I ran through a few M using the shortest x/y cycle as the last move
and attributing one candidate progression to the cycle, and have seen
no cascade lower than 10