A record named "maximum" of Sudoku list

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

Postby Eioru » Fri Sep 22, 2006 4:39 pm

Code: Select all
......3.1
86.......
...2.....
....4.76.
..1......
.......8.
.7....64.
5..1.3...
...5.....


Like this puzzle is 17-clue but it only has 64 Hidden Single.

Hidden Single has 3 kinds
1. Only remaining empty cell of the block, row or column (1.0)
2. Only possible position of one value in block (1.2)
3. Only possible position of one value in row or column (1.5)
But Naked Single (2.3) is more difficuly then Hidden Single and one kind
1. One value is the only possible value for a cell

562149378
000678125
178253649
000800063
000405x07
000300900
006500030
210034806
400086000
On the R5C7 cell ( I bold x there ) is the only possible value of 2, because the mid-right block, row 5 and column 7 already have 1,3,4,5,6,7,8,9, this cell can only put 2 in.

Bacause there isn't a 16-clue puzzle of normal Sudoku, the maximum Hidden Single is 64. And all of puzzle are solved by Hidden Single when the last some steps. Naked Single should don't have as many as 60 you said, but I am sure there are puzzles needing more than 5 steps of Naked Single, I don't find yet.
Eioru
 
Posts: 182
Joined: 16 August 2006

Postby udosuk » Sat Sep 23, 2006 2:26 pm

I finally dug up this old post...:D

http://forum.enjoysudoku.com/viewtopic.php?t=2124

Where dukuso, once one of our most prominent contributors and now reverted-expert of pandemic studies (for the sake of our global human health), posted this 18-clue beauty solvable solely with naked singles (no hidden singles required)...
Code: Select all
.1....6..
...3...7.
...7.....
7..43...8
..5...1..
......2..
8......4.
....62...
...51....

What's more, he verified that none of Gordon's 17s is solvable with naked singles alone. So it should be safe to say that the maximum #naked singles in a puzzle is 63...:idea:

I recommend everyone to try solving that 18-clue puzzle using naked singles only, and notice how each solved cell lead to another (few) naked single(s)... It's by no means an easy puzzle if you do it without pencilmarks...:!:

And it is the unique discovery among 10 million puzzles...:!:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Sat Sep 23, 2006 3:45 pm

Thanks udosuk.
I din't know that interesting thread.
As I mentionned above, my own record was 59 Nacked singles (puzzle with 22 clues).

Here is one solution for the dukuso's puzzle.

r7c4=9 - r7c5=7 - r7c6=3 - r7c7=5 - r8c4=8 - r9c6=4 - r1c4=2 - r4c7=9 - r5c4=6 - r5c8=3 - r6c4=1 - r4c6=5 - r4c8=6 - r6c8=5 - r4c2=2 - r4c3=1 - r7c2=6 - r7c3=2 - r7c9=1 - r8c8=9 - r1c8=8 - r2c7=4 - r3c7=3 - r8c7=7 - r8c9=3 - r9c7=8 - r9c8=2 - r9c9=6 - r1c6=9 - r1c9=5 - r3c8=1 - r8c3=4 - r1c5=4 - r8c2=5 - r1c1=3 - r1c3=7 - r8c1=1 - r9c1=9 - r9c3=3 - r5c1=4 - r5c9=7 - r6c1=6 - r6c9=4 - r9c2=7 - r5c6=8 - r6c5=9 - r6c6=7 - r3c6=6 - r5c2=9 - r5c5=2 - r6c3=8 - r2c2=8 - r2c5=5 - r2c6=1 - r3c2=4 - r3c3=9 - r3c5=8 - r3c9=2 - r6c2=3 - r2c1=2 - r2c3=6 - r2c9=9 - r3c1=5


I checked gordon's list (more recently). I haven't found any only-nacked singles puzzle either.

udosuk wrote:I only know that at the end of a puzzle there's generally a bunch of naked singles

see this thread.

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

Postby udosuk » Sat Sep 23, 2006 4:22 pm

Thanks JPF...:)

Unfortunately, this puzzle (I named it "Naked Beauty") wouldn't make Eioru's list because he rated the puzzles using SE which has a particular hierarchy ranking hidden singles before naked singles... IMHO for interest's sake we should not assume any hierarchy when establishing such a record archive list... Instead for each step the targeted technique should be ranked at the top so that all possible occurences could be spotted...

And I don't think hidden singles should be ranked before naked singles anyway... For pencilmark solvers or computer programs surely naked singles is much more easily spotted... E.g. SSTS ranks naked singles as the most obvious technique...

I suspect gsf's program could be much more suited for this task...:?:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ravel » Sat Sep 23, 2006 6:33 pm

udosuk wrote:And I don't think hidden singles should be ranked before naked singles anyway... For pencilmark solvers or computer programs surely naked singles is much more easily spotted...
I dont agree here. When we talk about spotting singles, for sure no pencilmarks are needed and the majority of people is solving sudokus on paper (maybe not in this forum).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Sun Sep 24, 2006 12:55 am

gordon's 22M 18's has 307 solved by naked singles only (2m30s @ 3.2Ghz)

asking for hidden single only solutions is trickier because at the end some
naked singles remain, in some cases only naked singles remain, so all cells
have one value, but some of them may not have been the result of an explicit placement
the trickieness is what technique gets to claim those remaining naked singles?
my solver attributes them to the most recent move

given that attribution, gordon's 18's has 9,716,852 solved by hidden singles (17m31s @ 3.2Ghz)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Sun Sep 24, 2006 7:14 am

gsf wrote:asking for hidden single only solutions is trickier because at the end some
naked singles remain, in some cases only naked singles remain, so all cells
have one value, but some of them may not have been the result of an explicit placement
the trickieness is what technique gets to claim those remaining naked singles?
my solver attributes them to the most recent move

Thanks for the analysis gsf.:)

It seems naked-singles-only puzzles are much rarer than hidden-singles-only ones. BTW at the end I'd say most singles are both naked & hidden. I'd be quite surprised to see a puzzle where at the end there remain several naked singles which are all not hidden at the same time...

Sudoku Explainer would be most effective to find HS-only puzzles... Perhaps you'd like to contact it's programmer to find out how...:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby tarek » Sun Sep 24, 2006 8:31 am

udosuk wrote:It seems naked-singles-only puzzles are much rarer than hidden-singles-only ones. BTW at the end I'd say most singles are both naked & hidden. I'd be quite surprised to see a puzzle where at the end there remain several naked singles which are all not hidden at the same time...

Sudoku Explainer would be most effective to find HS-only puzzles... Perhaps you'd like to contact it's programmer to find out how...:idea:


We ran into several discussions discussing situations where the naked single is also a hidden single in the ULTERIOR puzzles thread.......

The discussions included the (F valid but N invalid puzzles and vice versa), you need 2 runs of the solver to establish that.....

tarek
User avatar
tarek
 
Posts: 2624
Joined: 05 January 2006

Postby gsf » Sun Sep 24, 2006 9:32 am

tarek wrote:We ran into several discussions discussing situations where the naked single is also a hidden single in the ULTERIOR puzzles thread.......

The discussions included the (F valid but N invalid puzzles and vice versa), you need 2 runs of the solver to establish that.....

thanks for the memory, tarek
I reran gordon's 18s with the invalid qualification:
Code: Select all
-qN-G -Q!F -e V

(hidden single valid, naked single invalid): 9716611 puzzles
Code: Select all
-qF-G -Q!N -e V

(naked single valid, hidden single invalid): 66 puzzles

based on the previous runs there are 9716852 - 9716611 = 241 that solve
with either naked singles only or hidden singles only
here's one of the 241, 17 naked single steps or 10 hidden single steps:
Code: Select all
1 . . | . 2 . | 5 . .
. 8 . | . . . | . 3 .
. 4 . | 7 . . | . . .
------+-------+------
2 . 1 | . 5 . | 6 . .
. . . | 4 . . | . 8 .
. . . | 3 . . | . . .
------+-------+------
5 . . | . . . | 2 . .
. . . | 8 . . | . 4 .
. . . | . . . | . . .
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Eioru » Sun Sep 24, 2006 2:10 pm

udosuk wrote:
Code: Select all
.1....6..
...3...7.
...7.....
7..43...8
..5...1..
......2..
8......4.
....62...
...51....




This really can use naked single to find all of the numbers.
So, I add one condition that when there are easier solving way, it should do that way. I think SE follow this rule to solve all of puzzles and analyse the difficulty. Thus, my lists are all "exact difficulty" without "maximum difficulty" when collecting puzzles.
Thanks.
Eioru
 
Posts: 182
Joined: 16 August 2006

Postby gsf » Sun Sep 24, 2006 2:49 pm

udosuk wrote:Sudoku Explainer would be most effective to find HS-only puzzles... Perhaps you'd like to contact it's programmer to find out how...:idea:

in my solver the constraint order (and grouping for step counting) can be specified on the command line
-- no need for me to outsource

also, a note on programming, when a solver is working on limited techniques
it pays to bail as early as possible when those techniques fail -- this allowed
gordon's 18's to be filtered for naked singles only solutions (F-valid N-invalid) at the rate of ~45K/sec/Ghz
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

re: "naked single" valid, "hidden single"

Postby Pat » Mon Sep 25, 2006 8:24 am

gsf wrote:I re-ran Gordon's 18-clue puzzles
with the invalid qualification:
Code: Select all
-qF-G -Q!N -e V

( "naked single" valid and "hidden single" invalid ): 66 puzzles
this is the rarest type - could we please have an example?
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Postby Carcul » Mon Sep 25, 2006 12:46 pm

Mike Barker wrote:And these contain 9 URs:
Code: Select all
 . . 7 | . . . | . 3 .
 4 . . | 5 . 9 | . . .
 . 3 . | 8 . . | . 1 .
 ------+-------+------
 . . . | . . . | 1 . 4
 . . 5 | 1 4 . | . . .
 . . 4 | . . 3 | . . 6
 ------+-------+------
 . 2 . | . . 5 | . 7 .
 9 . . | . . . | . . 1
 . . . | . . 2 | . 9 .


Just by curiosity, how does your solver (and other solvers out there, electronic and human) solve this puzzle with the minimal number of steps?

Thanks in advance, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby Mike Barker » Mon Sep 25, 2006 1:09 pm

To me that is one of the million dollor questions. My solver is very simple in that it goes through a hierarchy of techniques which I've ranked based on my view of simplicity. It reports the first technique that is found which is why my solutions tend to be longer. There have been several threads on making solutions hierarchy independent and ravel and gsf have solvers which try to look for the next "best" step. I agree with all of this work, but haven't focused on it. I guess part of the issue, which has been discussed, is how to balance complexity with the number of steps required. My view was to take the easiest one and hope for the best (which I think somewhat reflects how most human solvers would approach the problem), however, there is an elegance in short solutions. I think we'd all like to find an algorithm to find the backdoor. As far as I know this is an area which is wide open and ripe for focus of the BB's considerable talent.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ravel » Mon Sep 25, 2006 1:33 pm

Carcul wrote:Just by curiosity, how does your solver (and other solvers out there, electronic and human) solve this puzzle with the minimal number of steps?

My program found 66 ways to solve it in 2 steps. All of them used the elimination r1c1<>8 or r1c2<>9 (or both).
Remark: How these eliminations are proved is all but optimized in my program, its about the same as if you enter the (wrong) number in a solver program like SS, susser etc. and continue until a contradiction arises.
[Added:] Also note, that after the first elimination it stops with the next one, that solves the puzzle. As there are so much possibilities for 2-steppers here, this happened in all 66 cases already with candidates in the first 2 cells.
ravel
 
Posts: 998
Joined: 21 February 2006

PreviousNext

Return to General