The New Sudoku Players' Forum

[denis_berthier]

Hi 1to9only,
I've added the W ratings for the easiest ones.

Code: Select all

.8.3......2.............9.........1......B.........53..5...A......4.............7............A.7..1...1.5...........2....  18 ED=2.9/1.5/1.5  W1
.8.3......2.............9.........1......B..........3..5...A......4.............7............A.7..1...1.5...........2....  17 ED=2.9/1.5/1.5  W1
.8.3......2.............9.........1......B..........3......A......4.............7............A.7..1...1.5...........2....  16 ED=2.9/2.9/2.9   W1
.8.3......2.............9.........1......B..........3......A......4.............7............A.7......1.5...........2....  15 ED=2.9/2.9/2.9   W1
.8.3......2.............9.........1......B..........3......A......4..........................A.7......1.5...........2....  14 ED=7.7/2.9/2.9   W2
.8.3......2.............9.........1......B..........3.............4..........................A.7......1.5...........2....  13 ED=7.9/2.9/2.9    W2
.8.3......2.............9.........1......B..........3.............4..........................A.7........5...........2....  12 ED=8.1/2.9/2.9    W4


Code: Select all

..3..........6.....................7....4..............B...................A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=8.1/1.5/1.5   W4
..3..........6.....................7....4..............B............3......A...6...A............2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=8.3/1.5/1.5   W5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6............BCD.2..5..D12....7........8..B....3.............  25 ED=8.3/8.0/2.9  W5


[denis_berthier]

.
I found this (PD13) 12-clue puzzle, which has 7 empty rows, 7 empty columns, 7 empty right-diagonals and 7 empty.
So only 24 of the 52 houses are hit - it could well be even harder (computationally) than the others. Sadly nobody is in a position to make that assessment!

Not a single whip can be applied.

[creint]

.
I found this (PD13) 12-clue puzzle, which has 7 empty rows, 7 empty columns, 7 empty right-diagonals and 7 empty left-digonals.[/code]

Tried nets on nets, did not find anything, maybe > TE2.

[coloin]

The 25 clues grids are harder:

Code: Select all

.............6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.7/1.5/1.5
..3................................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.4/1.5/1.5
..3..........6..........................4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.7/1.5/1.5
..3..........6.....................7...................B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.0/1.5/1.5
..3..........6.....................7....4...........................3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.7/1.5/1.5
..3..........6.....................7....4..............B...................A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=8.1/1.5/1.5
..3..........6.....................7....4..............B............3..........6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.3/1.5/1.5
..3..........6.....................7....4..............B............3......A.......A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.7/1.5/1.5
..3..........6.....................7....4..............B............3......A...6..........4.....2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=8.4/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A............2.........4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=8.3/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4...............4.6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.6/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2...........6........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.1/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4..........7...BCD.2..5..D12....7........8..B....3.............  25 ED=9.4/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6............BCD.2..5..D12....7........8..B....3.............  25 ED=8.3/8.0/2.9
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7....CD.2..5..D12....7........8..B....3.............  25 ED=9.9/7.6/2.9
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...B.D.2..5..D12....7........8..B....3.............  25 unrated
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BC..2..5..D12....7........8..B....3.............  25 ED=9.1/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD....5..D12....7........8..B....3.............  25 ED=9.3/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2.....D12....7........8..B....3.............  25 unrated
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5...12....7........8..B....3.............  25 ED=9.0/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D.2....7........8..B....3.............  25 unrated
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D1.....7........8..B....3.............  25 ED=9.0/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12.............8..B....3.............  25 ED=9.1/1.5/1.5
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7...........B....3.............  25 unrated
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8.......3.............  25 unrated
..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B..................  25 ED=9.2/1.5/1.5



The first unrated grid crashed the program with an 'out of memory' error! The other unrated grids were stopped after about 5-10 minutes of processing!
No processing of 24 clues done.

I hadnt appreciated that things were that bad !!! One has to be careful what one wishes for i guess !!

So we have puzzles that even -dlx programs and other guessing / proposition programs cant get a solution [ never mind logical elimination] and therefore inherently we cant get a rating !!!

However we have paradoxically a way of certifying that the puzzle is valid and minimal

As a measure of how far away we are with these puzzles - how many clues does a typical minimal puzzle from the above list have !! ?

[denis_berthier]

Hi Coloin,

It isn't such a surprise that larger proportions of puzzles tend to require deeper levels of T&E as grid size increases.
For Sudoku(9), eleven estimated there are about 1 puzzle in 60,000,000 that require T&E(2); none is known that would require T&E(3). But

“Blue”, a participant of the Sudoku Programmer’s Forum, reported that, using his generator – a priori biased towards easier instances, because it is of the top-down kind (see chapter 6):
– 46% of his randomly generated 16x16 minimal puzzles required T&E(2), although he could not find one requiring T&E(3) in 1.9 million random tries;
– 90% of his randomly generated 25x25 minimal puzzles required (at least) T&E(3): http://www.setbb.com/sudoku/viewtopic.p ... rum=sudoku.
[...]
Blue also found a few minimal puzzles with symmetries in the pattern of given cells; it is known that such symmetries often lead to harder puzzles in the mean. [...] T&E(d) computation times grow so fast with d that he computed only a lower bound for d, but this is enough for our present purposes. He posted (in the same thread):
– fifteen 16x16 minimal puzzles requiring at least T&E(3) (two of them appear in Figure 11.5, in hexadecimal notation),
– two 25x25 minimal puzzles requiring at least T&E(4) (one of them is given in Figure 11.6).

There are two main problems with Pandiags: grid size and branching factor. Grids of size 7 correspond to Sudoku{9); grids of size 11 correspond to Sudoku(16). Unfortunately, such puzzles are trivial if one uses the result about the small number of full grids. Next size, 13 - apparently the first size with "interesting" puzzles - correspond to Sudokus of size between 16 and 25.

Code: Select all

Sudoku
size   branching factor
9      20
16     39
25     64

Code: Select all

Pandiags
size    branching factor
7       24
11      40
13      48
17      64

[Mathimagics]

I agree about the "problems" Denis identified, from a puzzle-solving perspective, these are not very interesting.

From an analytical perspective, however, they are very interesting, because of the unique properties, and the unique challenges.

However we have paradoxically a way of certifying that the puzzle is valid and minimal

A method that is available for N=13 only, unfortunately. The next step up is N=17, which is a leap from a pea-sized problem to a planet-sized problem, I suspect ...

how many clues does a typical minimal puzzle from the above list have !!

That one I can answer (12). The real challenge here might be to find a 25-clue (or thereabouts) puzzle that is minimal ...

[denis_berthier]

.
A challenge about Fish in Pandiagonal Latin Squares

While trying to solve Pandiags of various sizes (i.e. 7, 11, 13), I've found Naked/Hidden Pairs/Triplets in rows, columns, diagonals and anti-diagonals. I remember someone has also found X-wings in a diagonal crossed by a column (or the converse - but I can't find the reference). However, I haven't found any Swordfish, let alone any Jellyfish.

As I wrote in a previous post, the number of possible combinations of rows/columns/diags and anti-diags is very large, both for the base sets and the cover sets. I've coded in CSP-Rules all the possibilities that don't mix rows/columns/diags/antidiags neither in the base sets nor in the cover sets - which already makes 12 different possible kinds of "homogeneous" Fish of a given size.

It should therefore be possible to find Swordfishes (Jellyfishes) in base/cover combinations other than the standard row/col or col/row or the diag/antidiag and antidiag/diag that can be derived from them by isomorphism.

Mith and any other champion of Fish, what do you think?

[denis_berthier]

I agree about the "problems" Denis identified, from a puzzle-solving perspective, these are not very interesting.

The case N=7 might be interesting if one forgets about the small number of possible solution grids and doesn't use this property while solving.

[creint]

Taking the last posted puzzle:

Code: Select all

..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B..................  25 ED=9.2/1.5/1.5

Arriving at this state:

Code: Select all

1589ACD   125789A   3         45789CD   159AC     5689D     15679ABC  1289ACD   14589ACD  12589AD   15789BC   189C      5789CD
6         12579C    589ABCD   1789ACD   159ACD    13589B    3489C     59ACD     13589ACD  12589ACD  123589    34789ABC  589ACD
159BC     13589C    589ABCD   15689ACD  129ACD    13489D    1245689AC 24589CD   13569ACD  7         3589CD    1489AD    13589A
13589AC   4         589CD     15689ACD  1379ACD   1789D     13589AC   123589AC  5689BC    59ABCD    135689CD  123789AD  12579
13589AD   12589AC   5689ACD   B         124579ACD 13589D    1789AC    23589C    34589AC   4589CD    13579D    169C      235789ACD
1589CD    1589      2789C     3         1459CD    156789BD  125689BC  789CD     15689CD   14589B    A         179BCD    1589BCD
12589CD   6         5789D     1589C     159CD     A         5789BC    135789CD  189D      1259BC    123589BC  3789BCD   4
139ACD    1589ABC   589ACD    15789AD   1359C     2         1345789C  14589AD   159C      6B        156789CD  189AC     35789CD
2589CD    1359ABC   4         1589C     6         135789    1589AB    1579C     1589ABCD  1589ABCD  1289CD    13789ABCD 1389AC
7         89        69        89A       B         C         D         1689A     2         3         4         5         1689A
3589AC    D         1         2         359A      459       4589A     5689AC    7         589C      89C       89ABC     6B
4         3579AC    569AC     579D      8         1359D     13579AC   B         1359AC    19ACD     1579CD    1269ACD   123569ACD
3589ABCD  1789AC    25789ABD  14569C    2579CD    13579BD   12589AC   135789ACD 13489AD   145689AC  15689CD   13789CD   1589C

Swordfish on 2 in:
Row 1
Row 6
Row 12
Linked to:
Anti-diagonal 2
Diagonal 8
Diagonal 10
-2r3c4

12 swordfishes found in single pass
Other exclusion -2r5c5 from fish in Row 6, Row 12, Column 2

[creint]

Taking the last posted puzzle again:

Code: Select all

..3..........6.....................7....4..............B............3......A...6...A......4.....2.........4.6........7...BCD.2..5..D12....7........8..B..................  25 ED=9.2/1.5/1.5

Arriving at this state:

Code: Select all

1589CD    12589A    3         45789CD   159C      569       15679ABC  1289CD    4589CD    1589AD    159BC     89C       5789CD
6         1579C     589BCD    189ACD    159ACD    13589B    489C      59CD      1589CD    129C      23        4789BC    589ACD
159BC     1589C     589ABCD   15689CD   129ACD    13489D    245689C   4589CD    13569ACD  7         3589CD    1489AD    1589A
13589C    4         589CD     69C       179CD     1789D     1589AC    23589AC   56BC      59ABCD    1589CD    189D      1259
1589AD    12589AC   589ACD    B         1459ACD   13589D    1789C     23589C    34589C    4589C     1579D     6         235789ACD
1589CD    1589      2789C     3         459CD     156789BD  125689BC  789CD     15689CD   14589B    A         179BCD    1589CD
12589CD   6         5789D     1589C     159CD     A         589BC     135789CD  189D      1259BC    2589BC    37B       4
19ACD     B         589ACD    15789D    159C      2         34        4589AD    159C      6         5789CD    189C      35789CD
259CD     1359C     4         1589C     6         15789     589AB     1579C     1589ABCD  1589BCD   1289CD    1789BCD   1389AC
7         89        69        89A       B         C         D         189A      2         3         4         5         1689
589AC     D         1         2         3         459       4589      6         7         589C      89C       89AC      B
4         359C      569AC     579D      8         159D      13579AC   B         1359AC    19ACD     1579CD    2         3569C
3589BCD   1789AC    25789ABD  1459C     2579CD    159BD     12589AC   135789CD  13489AD   4589C     6         13789CD   1589C

Jellyfish A in:
Row 1
Column 2
Column 12
Anti-diagonal 8
Linked to:
Column 4
Anti-diagonal 2
Diagonal 1
Diagonal 6
-Ar12c3

After this another Jellyfish on A found
Row 8
Row 10
Column 10
Anti-diagonal 5
Linked to:
Column 8
Diagonal 8
Diagonal 10
Diagonal 13
-Ar4c7

[denis_berthier]

Hi, creint

those are great examples - with mixed types of base and cover sets.

I wonder how you can find them, considering the huge number of such combinations. Don't you have any combinatorial explosion problems?

I also wonder how you arrive at the mentioned resolution states. To be more specific, the resolution state after Singles and whips[1] is

Code: Select all

14589ACD   125789AB   3          1456789ACD 159AC      5689D      15679ABC   1289ACD    14589ACD   12589AD    1256789BC  1689BC     5789CD     
6          12579BC    2589ABCD   1789ACD    12359ACD   13589B     234789C    1579ACD    13589ABCD  12589ACD   123589     34789ABC   1589ACD   
159BC      13589C     5689ABCD   15689ACD   129ACD     13489D     1245689ABC 2345689CD  13569ABCD  7          3589CD     13489AD    123589AB   
123589ABC  4          589CD      156789ACD  12379ACD   16789BD    135689ABC  1235689AC  35689BC    359ABCD    135689CD   123789AD   12579     
13589AD    12589AC    5689ACD    B          124579ACD  135689D    126789AC   12345689C  34589AC    45689CD    13579D     169C       1235789ACD
12589CD    125789     2789C      3          1459CD     156789BD   125689BC   789CD      15689CD    124589B    A          1679BCD    15689BCD   
123589BCD  6          25789D     1589C      159CD      A          35789BC    135789CD   189BD      1259BC     123589BC   3789BCD    4         
139ACD     1589ABC    589ACD     15789AD    1359C      2          1345789C   1345789AD  1569BC     14689ABCD  1356789BCD 1389AC     356789BCD 
2589BCD    1359ABC    4          1589C      6          135789     1589AB     1579C      13589ABCD  13589ABCD  1289CD     123789ABCD 12389AC   
7          389        69         89A        B          C          D          1689A      2          13689A     4          5          1689A     
3589ABC    D          1          2          359A       459        34589A     35689AC    7          3589C      389C       689ABC     689ABC     
1249C      3579AC     569AC      4579D      8          13569D     13579AC    B          13569AC    19ACD      1579CD     12369ACD   1235679ACD
3589ABCD   1789AC     25789ABD   14569C     23579CD    135679BD   1235689AC  135789ACD  13489AD    1245689ABC 15689BCD   13789CD    135689BC   


Some of these candidates have been deleted from your starting point.

[Edit]: put the resolution state for the correct puzzle.

[Mathimagics]

how many clues does a typical minimal puzzle from the above list have !!

That one I can answer (12). The real challenge here might be to find a 25-clue (or thereabouts) puzzle that is minimal ...

Actually, the first challenge is just to find a 16-clue minimal puzzle!

A review seems in order. All testing I have done is on grid #1 in the ED list. It's non-cyclic, one of only 3 such cases (the others are #2, #3). All other grids are cyclic (grids #4, #10) or semi-cyclic (grids #5 to #9).

Regarding 12C puzzles on grid #1:

• for a 12C enumeration using the HS (hitting set) method, the UA's here seem to be useless. The smallest, UA26's are useless since we require 12 different clue values anyway, so just about any 12 hits those. All the other UA's that I have found (3407 so far) are, as I reported earlier, mostly of sizes ~100, and it is no surprise to find that many choices of 4C, and most choices of 5C, hit every one of those UA's

• so I used a simple generation method, where we start with a pool of known 12C's, then use a PM1 (aka {+1,-1}) to identify new cases, rinse and repeat.

• I started with a pool of 5400 12C's on grid #1 that I had found by random clue removals + removing redundant clues. The PM1 generation expanded this set to 133K, a growth factor of ~25). The next pass had a growth factor of ~24, and our set had grown to 3.3 million. A 3rd pass produced 33 million, with the growth factor (at last!) slowing down to 10. (I have no intention at this stage of doing a 4th pass! )

• from which we may conclude that there are one heck of a shipload of 12C puzzles.

Now, regarding minimal puzzles:

• it was noticeable, during the pool generation phase, that nearly every random reduction led to a 12C, and failing that, a 13C.

• I picked a 12C at random, then used a {+2,-1} search to find minimal 13C's, and this found 24K.

• I then picked a couple of those 13C's, and for each one the {+2,-1} search produced ~750 minimal 14C's

• from these I am enumerating all 14C's that can be found via {+2,-1}. That's still running (it's a slow painful process) but is turning up ~6 15C's per item

• none of the 15C's found so far (and that is not terribly many) have a minimal 16C that can be found via {+2,-1} search

From all of these observations, I think that the number of minimal puzzles starts to decline at the 14C mark, and then declines rapidly. So much, in fact, that the very existence of a minimal 16C is seriously in question ..

OMG, not another $*#@*! 16-clues existence problem, please!

[creint]

I wonder how you can find them, considering the huge number of such combinations. Don't you have any combinatorial explosion problems?

I also wonder how you arrive at the mentioned resolution states. To be more specific, the resolution state after Singles and whips[1] is. Some of these candidates have been deleted from your starting point.

-Sets are not a real problem, don't need to find links, can only be linked one way. Only need to check one constraint.
Fish is a problem with my current implementation. ~25 seconds to scan 2-4 fish.
The problem is linking with all previous base sets. If this process is fast enough then it can find SK-loops and larger structures with no overlapping links. Another problem is trying all base set combinations. Combinations * combinations is not fast unless someone knows a trick to reduce things.

-Arriving using many forcing nets, returning results in groups. Solve speed with max fish size 2 (6s) is <60 seconds.

[denis_berthier]

Sets are not a real problem, don't need to find links, can only be linked one way. Only need to check one constraint.

If you mean Naked and Hidden Subsets, I agree.

Fish is a problem with my current implementation.
[...]
Another problem is trying all base set combinations. Combinations * combinations is not fast unless someone knows a trick to reduce things.

Thats' what I meant. I think it's not only about your implementation. There are huge numbers of possible combinations, especially if you allow mixed base sets and/or mixed cover sets.

Anyway, it's great you could find these examples.

[creint]

I also wonder how you arrive at the mentioned resolution states. To be more specific, the resolution state after Singles and whips[1] is

Hidden Text: Show

Code: Select all

14589ACD   125789AB   3          1456789ACD 159AC      5689D      15679ABC   1289ACD    14589ACD   12589AD    1256789BC  1689BC     5789CD     
6          12579BC    2589ABCD   1789ACD    12359ACD   13589B     234789C    1579ACD    13589ABCD  12589ACD   123589     34789ABC   1589ACD   
159BC      13589C     5689ABCD   15689ACD   129ACD     13489D     1245689ABC 2345689CD  13569ABCD  7          3589CD     13489AD    123589AB   
123589ABC  4          589CD      156789ACD  12379ACD   16789BD    135689ABC  1235689AC  35689BC    359ABCD    135689CD   123789AD   12579     
13589AD    12589AC    5689ACD    B          124579ACD  135689D    126789AC   12345689C  34589AC    45689CD    13579D     169C       1235789ACD
12589CD    125789     2789C      3          1459CD     156789BD   125689BC   789CD      15689CD    124589B    A          1679BCD    15689BCD   
123589BCD  6          25789D     1589C      159CD      A          35789BC    135789CD   189BD      1259BC     589BC      3789BCD    4         
139ACD     1589ABC    589ACD     15789AD    1359C      2          1345789C   1345789AD  1569BC     14689ABCD  1356789BCD 1389AC     356789BCD 
2589BCD    1359ABC    4          1589C      6          135789     1589AB     1579C      13589ABCD  13589ABCD  1289CD     123789ABCD 12389AC   
7          389        69         89A        B          C          D          1689A      2          13689A     4          5          1689A     
3589ABC    D          1          2          359A       459        34589A     35689AC    7          3589C      389C       689ABC     689ABC     
1249C      3579AC     569AC      4579D      8          13569D     13579AC    B          13569AC    19ACD      1579CD     12369ACD   1235679ACD
3589ABCD   1789AC     25789ABD   14569C     23579CD    135679BD   1235689AC  135789ACD  13489AD    1245689ABC 15689BCD   13789CD    135689BC

It seems you are missing some locked singles, whip[1].
For example 3r10 -> -3r5c2, -3r25c10 (using links from column 2, column 10, antidiagonal 6, diagonal 6, diagonal 11)
3 layers of locked singles total 15 pencilmarks.
Or is that not called whip[1]?