Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Cascading Singles
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Feb 11, 2006 4:50 am    Post subject: Cascading Singles Reply with quote

I'm new to Sudoku and learning more each day.

I've used Simple Sudoku for fun and as a learning tool. I also managed to get QQwing installed on my Win 98 system and ran several solutions with it.

In all of the puzzles that I've encountered, there's always a number of single cell values that cascade during the final steps of a solution. However, among all of the information that I've read on this forum, I don't recall anyone posting any statistics on this topic.

What's the minimum number of values in a cascade? The maximum? What might a typical distribution look like for, say, 10K hard puzzles?

(Yes, I know that hard is subjective. )
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Feb 11, 2006 6:34 am    Post subject: Reply with quote

Hi,

Each Sudoku that requires reduction techniques will at some point "break". Beyond that breaking point the remainder of the placements can be done by singles only. There are at least 9 "last empty cell" singles in each sudoku, and a couple more when "last empty cell" for row, column and box do not coincide. Many of those are part of the final sequence of singles.

I will give you 2 examples:

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


This first sudoku allows 1 single placement, 2 line-box reductions, a coloring step and then it breaks. You can call this a "hard" sudoku, but after this hurdle in the beginning, it is solved with 57 singles. That would qualify for the longest sequence, I think.

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


The sudoku above allows the placement of 46 singles, then stops at a point where a remote pair (or BUG) is required, and then you can easily place the last 11 digits.

I've checked my complete database, but 11 seems to be the minimum number of consecutive singles completing the puzzle.

Thanks for your interesting question. This has helped me look at a few other aspects in determining the optimum solving path.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
foxglove

Joined: 04 Feb 2006
Posts: 42
:
Location: Portugal

Items
PostPosted: Sat Feb 11, 2006 10:32 pm    Post subject: Reply with quote

An illustration for the very paradigmatic examples by Ruud:
Ex 1:


Ex 2:


and something in the middle that besides doesn't break at once.


the green bars are the count of naked/hidden singles; red bars the "hurdles"
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sat Feb 11, 2006 11:00 pm    Post subject: Reply with quote

foxglove wrote:
An illustration for ... something in the middle that besides doesn't break at once.



the green bars are the count of naked/hidden singles; red bars the "hurdles"

... and the horizontal scale represents ???
Back to top
View user's profile Send private message
vidarino

Joined: 10 Feb 2006
Posts: 38
:
Location: Haugesund, Norway

Items
PostPosted: Sat Feb 11, 2006 11:17 pm    Post subject: Reply with quote

rkral wrote:
... and the horizontal scale represents ???


Time, steps or iterations, I bet. Smile
Back to top
View user's profile Send private message Visit poster's website
foxglove

Joined: 04 Feb 2006
Posts: 42
:
Location: Portugal

Items
PostPosted: Sat Feb 11, 2006 11:23 pm    Post subject: Reply with quote

Time, steps or iterations
Very Happy
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Feb 12, 2006 1:18 am    Post subject: Reply with quote

wow fox!

those graphs are pretty much speaking for themselves. I'm really impressed with those! Cool

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
foxglove

Joined: 04 Feb 2006
Posts: 42
:
Location: Portugal

Items
PostPosted: Sun Feb 12, 2006 2:05 am    Post subject: Reply with quote

Embarassed

Thanks!
I put up a detailed explanation at:
Puzzle profiles
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sun Feb 12, 2006 8:25 am    Post subject: Reply with quote

Ruud wrote:

I've checked my complete database, but 11 seems to be the minimum number of consecutive singles completing the puzzle.

here is a puzzle advanced to the point where an odd (5 edge) x-cycle on value 1
with one weak edge leads to a singles only solution with 9 singles
(cycle notation snarfed from my ancient solver)
Code:

x-cycle: [4,3][4,8][8,8][8,2]-[5,2] => [5,2]^1[8,2]^1

 1   2   3  | 4   5   6  | 7   8   9
 4   5   6  | 7   8   9  | 1   2   3
 7   8   9  | 1   3   2  | 5   6   4
------------+------------+------------
 2   3   14 | 9   47  5  | 8   17  6
 6   14  5  | 2   47  8  | 9   3   17
 8   9   7  | 3   6   1  | 2   4   5
------------+------------+------------
 3   6   2  | 5   1   7  | 4   9   8
 5   17  8  | 6   9   4  | 3   17  2
 9  147  14 | 8   2   3  | 6   5   17

final singles: [4,3]=1[4,8]=7[5,5]=7[5,9]=1[8,8]=1[9,2]=1[9,3]=4[9,9]=7[4,5]=4
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sun Feb 12, 2006 11:47 am    Post subject: Reply with quote

Thanks for pointing that one out.

I can imagine a 7 remaining cells configuration, but I cannot turn it into a practical example:

Code:
   X   X

X      X

X  X   X


Anyone?

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sun Feb 12, 2006 12:44 pm    Post subject: Reply with quote

Ruud wrote:
... after this hurdle in the beginning, it is solved with 57 singles. That would qualify for the longest sequence, I think.

Hi Ruud. From this stage of #389 of the top1465 ...
Code:

 ...|.14|7..
 6.9|...|...
 3..|...|...
 ---+---+---
 ...|6.1|.3.
 .5.|8..|...
 ...|...|.1.
 ---+---+---
 ...|93.|8..
 .4.|...|..2
 ...|...|5..

 258     28      258     | 235     1       4       | 7       25689   3689
 6       1278    9       | 2357    2578    23578   | 1234    2458    1348
 3       1278    4       | 257     256789  256789  | 12      258     18
-------------------------+-------------------------+------------------------
 24789   289     278     | 6       24579   1       | 249     3       45789
 12479   5       12367   | 8       2479    2379    | 2469    24679   4679
 24789   23689   23678   | 23457   24579   23579   | 2469    1       456789
-------------------------+-------------------------+------------------------
 1257    26      12567   | 9       3       2567    | 8       467     1467
 15789   4       135678  | 157     5678    5678    | 1369    679     2
 12789   23689   123678  | 1247    24678   2678    | 5       679     13679

... eliminate 8s from box 3 col 9 intersection (because of locked candidates in box 6) and there are 62 cascading singles.

And I doubt this is the longest cascade of singles, Ron
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Sun Feb 12, 2006 3:35 pm    Post subject: Reply with quote

rkral wrote:

... eliminate 8s from box 3 col 9 intersection (because of locked candidates in box 6) and there are 62 cascading singles.

And I doubt this is the longest cascade of singles, Ron

(81-17)=64, so if 17 is the minimal number of clues there should be a 64 cascade
lurking in Gordon's catalog -- there are 15201
here's one of them
Code:

9 8 . | . 5 . | . . .
. . . | . . . | 7 3 .
6 . . | . . . | . . 2
------+-------+------
. . . | 3 . . | . . 8
4 . . | . . . | . . .
. 5 . | . . . | . . .
------+-------+------
. . 3 | 2 . . | 1 . .
. . . | . . 1 | 4 5 .
. . . | . . . | . . .
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Feb 13, 2006 12:07 am    Post subject: Reply with quote

Does that count in this topic? Singles only?

I have to revisit this example of yours, gsf:

Code:
x-cycle: [4,3][4,8][8,8][8,2]-[5,2] => [5,2]^1[8,2]^1

 1   2   3  | 4   5   6  | 7   8   9
 4   5   6  | 7   8   9  | 1   2   3
 7   8   9  | 1   3   2  | 5   6   4
------------+------------+------------
 2   3   14 | 9   47  5  | 8   17  6
 6   14  5  | 2   47  8  | 9   3   17
 8   9   7  | 3   6   1  | 2   4   5
------------+------------+------------
 3   6   2  | 5   1   7  | 4   9   8
 5   17  8  | 6   9   4  | 3   17  2
 9  147  14 | 8   2   3  | 6   5   17

final singles: [4,3]=1[4,8]=7[5,5]=7[5,9]=1[8,8]=1[9,2]=1[9,3]=4[9,9]=7[4,5]=4


In my code, higher techniques never do placements, so my solver reports this as an 11 singles cascade.

The way my solver handles singles creates the difference here.

I do not see any way to construct a sudoku with less than 11 cells that require a technique other than singles.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Mon Feb 13, 2006 1:55 am    Post subject: Reply with quote

Ruud wrote:

Code:
x-cycle: [4,3][4,8][8,8][8,2]-[5,2] => [5,2]^1[8,2]^1


In my code, higher techniques never do placements, so my solver reports this as an 11 singles cascade.

The way my solver handles singles creates the difference here.

I do not see any way to construct a sudoku with less than 11 cells that require a technique other than singles.

its right on the edge
Code:
[5,2]^1

drops candidate 1 from [5,2], at this point my solver recognizes the remaining single and notes it without going to the singles logic (an optimization) but it gets listed as a single (is that twisted enough)

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
Back to top
View user's profile Send private message Visit poster's website
eclark

Joined: 28 Dec 2005
Posts: 70
:

Items
PostPosted: Mon Feb 13, 2006 2:19 am    Post subject: Reply with quote

So whats the opposite? Whats the highest cascading singles before hitting a stopping place. This seems a bit harder to count.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron