View previous topic :: View next topic |
Author |
Message |
| daj95376
| Joined: 05 Feb 2006 | Posts: 349 | : | | Items |
|
Posted: Sat Feb 11, 2006 4:50 am Post subject: Cascading Singles |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sat Feb 11, 2006 6:34 am Post subject: |
|
|
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 |
|
|
| foxglove
| Joined: 04 Feb 2006 | Posts: 42 | : | Location: Portugal | Items |
|
Posted: Sat Feb 11, 2006 10:32 pm Post subject: |
|
|
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 |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Sat Feb 11, 2006 11:00 pm Post subject: |
|
|
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 |
|
|
| vidarino
| Joined: 10 Feb 2006 | Posts: 38 | : | Location: Haugesund, Norway | Items |
|
Posted: Sat Feb 11, 2006 11:17 pm Post subject: |
|
|
rkral wrote: | ... and the horizontal scale represents ??? |
Time, steps or iterations, I bet. |
|
Back to top |
|
|
| foxglove
| Joined: 04 Feb 2006 | Posts: 42 | : | Location: Portugal | Items |
|
Posted: Sat Feb 11, 2006 11:23 pm Post subject: |
|
|
Time, steps or iterations
|
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sun Feb 12, 2006 1:18 am Post subject: |
|
|
wow fox!
those graphs are pretty much speaking for themselves. I'm really impressed with those!
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| foxglove
| Joined: 04 Feb 2006 | Posts: 42 | : | Location: Portugal | Items |
|
Posted: Sun Feb 12, 2006 2:05 am Post subject: |
|
|
Thanks!
I put up a detailed explanation at:
Puzzle profiles |
|
Back to top |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Sun Feb 12, 2006 8:25 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sun Feb 12, 2006 11:47 am Post subject: |
|
|
Thanks for pointing that one out.
I can imagine a 7 remaining cells configuration, but I cannot turn it into a practical example:
Anyone?
Ruud. _________________ Meet me at sudocue.net |
|
Back to top |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Sun Feb 12, 2006 12:44 pm Post subject: |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Sun Feb 12, 2006 3:35 pm Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Mon Feb 13, 2006 12:07 am Post subject: |
|
|
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 |
|
|
| gsf
| Joined: 18 Aug 2005 | Posts: 411 | : | Location: NJ USA | Items |
|
Posted: Mon Feb 13, 2006 1:55 am Post subject: |
|
|
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
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 |
|
|
| eclark
| Joined: 28 Dec 2005 | Posts: 70 | : | | Items |
|
Posted: Mon Feb 13, 2006 2:19 am Post subject: |
|
|
So whats the opposite? Whats the highest cascading singles before hitting a stopping place. This seems a bit harder to count. |
|
Back to top |
|
|
|