minimum number of end-game singles

Everything about Sudoku that doesn't fit in one of the other sections

minimum number of end-game singles

Postby r.e.s. » Thu May 25, 2006 5:26 pm

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?
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby RW » Thu May 25, 2006 6:00 pm

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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby r.e.s. » Thu May 25, 2006 6:12 pm

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.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby tso » Thu May 25, 2006 7:14 pm

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.
tso
 
Posts: 798
Joined: 22 June 2005

Postby r.e.s. » Thu May 25, 2006 7:44 pm

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.
Last edited by r.e.s. on Thu May 25, 2006 4:59 pm, edited 2 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby Ocean » Thu May 25, 2006 8:24 pm

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    |
 *--------------------------------------------------*
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Ruud » Thu May 25, 2006 8:49 pm

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.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby r.e.s. » Thu May 25, 2006 8:55 pm

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.
 
Posts: 337
Joined: 31 August 2005

Postby r.e.s. » Thu May 25, 2006 9:13 pm

Hi Ruud,
Ruud wrote: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.

Ruud wrote: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.

Ruud wrote: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!
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby JPF » Thu May 25, 2006 11:35 pm

Ruud wrote: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 ?

Ruud wrote: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
JPF
2017 Supporter
 
Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Postby Ruud » Fri May 26, 2006 12:22 am

JPF wrote: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.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby r.e.s. » Fri May 26, 2006 12:40 am

JPF wrote:I made earlier a similar (?) observation in this post
JPF wrote: 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):

gsf wrote: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.]
Last edited by r.e.s. on Fri May 26, 2006 9:59 am, edited 1 time in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby gsf » Fri May 26, 2006 6:00 am

r.e.s. wrote:
gsf wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA


Return to General