The New Sudoku Players' Forum

[gfroyle]

Rather than bury this in the minimum clues thread, I thought I would update the current status of the files of 17-clue and 18-clue Sudokus that I have generated as a result of the (so far fruitless) search for the elusive 16.

I now have 32930 distinct 17-clue sudokus, and have updated the file on the website.

http://www.csse.uwa.edu.au/~gordon/sudokumin.php

They are stored in lex order according to the canonical labelling that comes out of a program, and so the old ones will be interleaved with the new ones, thus any references to "Number #21020" and so on will change. When I get round to it, I will put them in a proper database with a permanent ID number.

The search for 17s is slowing down dramatically, in that I am finding fewer and fewer new ones. I had wanted to get to a round 35000 before updating, but this would take too long. This either means that I have found a substantial proportion of them, or just that my search techniques have exhausted the space that they are capable of searching.


As for 18s, I now have 22079642 of them. They are not online as the uncompressed files are about 1.8Gb in size. The search for these appears unlimited, in that there seems no sign of a diminishing number of new ones.

Of course the two paragraphs preceding contain seemingly contradictory statements, and I do not understand myself why I can keep finding new 18s at will, but these contain only few new 17s (of course I check the new 18s for any 17s they contain). This is presumably an artefact of the search, and is possibly an indication that there are lots more 17s "somewhere else" in the search space.

Here are some quick stats on the 17s: this shows the number of occurrences of each digit - for example, 7 of them have one absent digit, three digits occurring once, two occurring twice, two occurring three times and one occurring 4 times.

Code: Select all

      7 0 1 1 1 2 2 3 3 4
    175 0 1 1 1 2 3 3 3 3
    197 0 1 1 2 2 2 2 3 4
   5908 0 1 1 2 2 2 3 3 3
     12 0 1 2 2 2 2 2 2 4
   8377 0 1 2 2 2 2 2 3 3
    730 0 2 2 2 2 2 2 2 3
     10 1 1 1 1 1 3 3 3 3
     81 1 1 1 1 2 2 2 3 4
   2220 1 1 1 1 2 2 3 3 3
     13 1 1 1 2 2 2 2 2 4
  11091 1 1 1 2 2 2 2 3 3
   4104 1 1 2 2 2 2 2 2 3
      5 1 2 2 2 2 2 2 2 2


There are 20717 different clue-patterns with the most popular pattern occurring 36 times - here is one with this pattern.

Code: Select all

0 8 0  0 0 0  0 0 9 
0 1 2  0 0 0  0 0 0 
0 0 0  6 0 0  3 0 0 

0 7 0  0 0 0  2 8 0 
9 0 0  4 0 0  0 0 0 
0 0 0  3 0 0  0 0 0 

3 0 0  0 0 0  4 0 0 
5 0 0  0 8 0  0 0 0 
0 0 0  0 1 0  0 0 0


I will provide in due course a way to access the 18s for anyone interested, either few-at-a-time via some web interface for players, or via CD for those interested in the mathematical/statistical aspects of the entire collection.

In the meantime, if anyone has a program (that I can compile on Linux or MacOS X) that rates Sudokus for human solvers in terms of techniques needed, then I would be grateful if I could use it on my 18s in order to provide useful information to players (dukusos rating program provides a more technical rating that does not correspond to human techniques). I just don't have time to write one myself at the moment.

Cheers

Gordon

[kjellfp]

Great work, nice list of 17s - and here are my two conclusions based on what you say.

1. There most certainly is no 16-clue sudoku:

Every 16 should give 65 different 17s. If you have found only 1/10th (probably you have much more, since the number of new 17s is dropping dramatically) of the 17s, some of them should belong to a 16 if it exists. I'm sure that you have testet the 17s for 16s and found none.

However, the fact that we already have a 16-clue with only two solutions makes me wonder. Have you thought about rewriting your code to find 16s with N solutions, and get an idea on how that number changes with N?

2. There most certainly is no symmetric 17-clue sudoku:

There are 81!/(64!*17!)=1.28e17 different 17-clue patterns.

There are 40!/(32!*8!)=7.69e7 different symmetric 17-clue patterns.

How many 17-clue pattern equivalence classes are there (modulo ordinary transformations)? Well, from one pattern, you can do 6*6*2*2*2 transformations and still get a symmetric pattern: 6 ways to permute the first band, 6 ways to permute the last, swap top and bottom band, swap top and bottom column on middle band, and for all these, operations, do the same operation on columns/stacks to conserve symmetry. That is 6*6*2*2. In addition to that, we can transpose. However, one of these transformations lead to the same pattern, namely horisontal+vertical mirroring.

So if the automorphism groups are as small as possible (expected in most cases), we have about 7.69e7/(6*6*2*2)=5.34e5 pattern equivalence classes with symmetric members. I call this a symmteric equivalence class.

Most 17-clue pattern equivalence classes have trivial automorphism gourp, so one equivalence class should contain 2*6^8 patterns. For symmetric classes, we know about the mirroring transforamtion leaving a symmetric pattern fixed, so such classes are expected to have 6^8 different patterns.

Therefore, there are about 5.34e5 * 6^8 = 8.97e11 17 clue patterns belonging to a symmetric class. Compared to the 1.28e17 17-clue patterns in total, only 1 out of about 140000 17-clue patterns give a symmetric pattern. That is more than you have found (under 35000).

But not as far away as for the 16s, so maybe I'm wrong, and some symmetric 17 is hiding somewhere...

[dukuso]

thanks Gordon.
I might be interested in the CD later, should I change my method
to rate sudokus by difficlty.
Can you put a random sample of -say- 10000 from the 18s
to your webpage for statistics ?

To me it's surprising how many really hard sudokus are in these lists
although it was not designed for that search.

I know, Nick70 and others could also rate them by the methods
required to solve them, rather than node-counts for the fastest
computer solvers.
I also hope someone will do it and post the statistics.

here is a repost of Nick70's statistics for an earlier list :

9276 diff 00 [trivial]
5994 diff 01 [single unit candidate]
778 diff 02 [naked pair]
511 diff 03 [hidden pair]
4 diff 04 [x-wing]
1037 diff 05 [turbot fish]
17 diff 06 [naked triplet]
2 diff 07 [swordfish]
8 diff 08 [hidden triplet]
499 diff 09 [xy-wing]
61 diff 10 [skewed swordfish]
2 diff 14 [jellyfish]
931 diff 15 [forcing chain]
72 diff 16 [multi forcing chain]
5 diff 20 [guessing]


to see how this compares with random minimal sudokus :
http://www.research.att.com/~gsf/sudoku/

e.g.:
17 clue: 47% trivial (FN-constraint)
all minimal : 68% trivial


-Guenter

[Nick70]

I now have 32930 distinct 17-clue sudokus, and have updated the file on the website.

Here are statistics for the difficulty of those problems, as reported by my program. The order is the arbitrary order of technique difficulty, e.g. a puzzle classified as "x-wing" might also require hidden pair.

Code: Select all

singles             15198  46,15%
box-line exclusion  10461  31,77%
hidden pair          2384   7,24%
naked pair            100   0,30%
x-wing                 11   0,03%
turbot               1899   5,77%
naked triplet          23   0,07%
swordfish               4   0,01%
hidden triplet         14   0,04%
xy-chain             1572   4,77%
jellyfish               2   0,01%
forcing chain        1121   3,40%
multi forcing chain   129   0,39%
forcing tree           12   0,04%

[Ocean]

I now have 32930 distinct 17-clue sudokus, and have updated the file on the website.

...
I will provide in due course a way to access the 18s for anyone interested, either few-at-a-time via some web interface for players, or via CD for those interested in the mathematical/statistical aspects of the entire collection.

Thank you Gordon. (Also looking forward to the 18s ...)

Here are some more stats on the 17s: this shows the distributon of digits over the boxes - for example, 2 of them have two empty boxes, two boxes with one digit, two boxes with two digits, one box with three digits and two boxes with four digits. The two most common box configurations (111222233 and 112222223) are found in about 70% of the 17s. There are 20 sudokus with two empty boxes, and 5 sudokus that have five clues in the same box.

Code: Select all

   
    2 001122344:B
    2 001222334:B
    2 001223333:B
    2 002222234:B
   12 002222333:B
    7 011112344:B
    4 011113334:B
    2 011122235:B
   17 011122244:B
  177 011122334:B
  108 011123333:B
    2 011222225:B
  381 011222234:B
  946 011222333:B
  100 012222224:B
  945 012222233:B
  157 022222223:B
    1 111112235:B
   22 111112244:B
  486 111112334:B
  135 111113333:B
 1341 111122234:B
 2904 111122333:B
  659 111222224:B
11342 111222233:B
11769 112222223:B
 1405 122222222:B



[Wolfgang]

This either means that I have found a substantial proportion of them, or just that my search techniques have exhausted the space that they are capable of searching.

(If my normalization is correct:) The 4 17-clues i found with the simple heuristic all have been in the list, but not the one, i found from the 18-clues in ssf (though its easy to solve).

[dukuso]

that means, there are probably less than 100000 17-clue-sudoku-
equivalence-classes and chances for a 16 are very small.

Seems closer to 50000 than to 100000, but I wanted to be safe

the 16-search is (almost) over !

[gfroyle]

(If my normalization is correct:) The 4 17-clues i found with the simple heuristic all have been in the list, but not the one, i found from the 18-clues in ssf (though its easy to solve).

can you please post/send the new one?

thx

gordon

[Wolfgang]

can you please post/send the new one?

I had already posted it in the minimum thread. This is the normalized form:

Code: Select all

120300000300000000000000400500000000004600700000210000078090000000005030000000020


[Moschopulus]

that means, there are probably less than 100000 17-clue-sudoku-
equivalence-classes and chances for a 16 are very small.

Seems closer to 50000 than to 100000, but I wanted to be safe

the 16-search is (almost) over !

Does anybody think that a 16 exists? Gordon used to think so - have you changed?

[gfroyle]

I had already posted it in the minimum thread. This is the normalized form:

Code: Select all

120300000300000000000000400500000000004600700000210000078090000000005030000000020


Sorry about that .. I missed it before, or I would have commented on it.

It is new to my list... even the list as recently updated.


What would be great is if you could find 10 or 20 "random" 17s - that is, constructed without reference to the existing lists. Then if it turned out that all but 1 or 2 of them were already on the list, we would have confidence that the 17s are mostly found. But if most of them were NOT on the list, then we would be back to the default assumption that there are plenty more hiding somewhere.

Moschopulus - I am now pessimistic of the chances of a 16 existing. Now that the search really seems to be grinding to a halt, I am getting less and less hopeful.

Cheers

Gordon

[udosuk]

Sorry Gfroyle if you've posted it before somewhere else but could you please list out the 5 "8 1/2 pairs of clues" puzzles? Also the lists of the 7 {0 1 1 1 2 2 3 3 4} and the 10 "5 singles & 4 triples" would be of some interest too, as they are rare.

You also showed us an example of a 16-clue puzzle that has 7 out of the 9 digits all fixed on 63 cells and the remaining 18 cells can only be filled in 2 ways, swapping the remaining 2 digits. Which is this one:

Code: Select all

5 . 2 . . . 4 . .
. . . 7 1 . . . 3
. . . . . . . . .
. . . . . 4 6 . .
. 7 . 2 . . . . .
. 1 . . . . . . .
6 . . . . 2 . . .
. . . . 3 . . 1 .
4 . . . . . . . .

Is this unique or are there any others of this type? Thanks!

[Ocean]

... could you please list out the 5 "8 1/2 pairs of clues" puzzles? Also the lists of the 7 {0 1 1 1 2 2 3 3 4} and the 10 "5 singles & 4 triples" would be of some interest too, as they are rare.

Code: Select all

V:222222221

010000009000300800000000600000012400703000000500000000800600000000040020000700050
030600080019000000000020000700000450000031000200000000400800000060500000000000900
052400000000070100000000000000802000300000600090500000106030000000000089700000000
092300000000080100000000000107040000000000065800000000060502000400000700000900000
800000001000950000000000000000070420301600000000000000040000570600308000000000200


V:433221110

000000130000080005420000000600000020005010000000000400070402000000600200000000001
000031600200000007000000100050200040036000000001000000800710000000000020000000300
000401200800600010300000500040100700200030000000000000000020080010000000000000030
040030000000000052000000670080000300000200000000700000203000100700502000000080000
160500000000008700500000000450100060007000300000020000000000051000073000000000000
600300000000000081000000000018000050005600000000703000200010000400000600060000300
830020000200500100000000000070000082000601000000000000020080030001000600400000000


V:333311111

000010300520000000060000070400000130000806000000500000000600005109000000300000000
000060030000800200200500000000290500076000000000000100000007064500000000000000070
000081000500000200000000000084000007000200500000000000250600040000040038900000000
070030000020000060000000039000200700306000000000000100000702400600000050000800000
080030000020000060000000039000200800306000000000000100000702400600000050000800000
200060000000700010000000300000020096001000000070000000050400700600000802000100000
230040500000081040700000000000306200014000000000000000000000091300200000000000000
300200000200000800000000001008030007000900030010000000000018500400006020000000000
500020000000300040100000000000400570030900000600000100000050800040000003000001000
600100000000000250100000000020057000000000060000020000059000400000601008000300000

[gfroyle]

You also showed us an example of a 16-clue puzzle that has 7 out of the 9 digits all fixed on 63 cells and the remaining 18 cells can only be filled in 2 ways, swapping the remaining 2 digits. Which is this one:

Code: Select all

5 . 2 . . . 4 . .
. . . 7 1 . . . 3
. . . . . . . . .
. . . . . 4 6 . .
. 7 . 2 . . . . .
. 1 . . . . . . .
6 . . . . 2 . . .
. . . . 3 . . 1 .
4 . . . . . . . .

Is this unique or are there any others of this type? Thanks!

Firstly, thanks Ocean for posting the others; I am a bit busy at the moment...

Secondly, yes, this is the only 2-solution Sudoku that I know at the moment.

Thirdly, to answer an earlier query by Kjell - I do keep a list of all the 16-clue Sudokus with at most 200 completions, hoping that I can perturb one of them slightly to find one with 1 completion. I currently have

1 with 2 completion
3 with 4 completion
5 with 6 completion
1 with 7 completion
8 with 8 completions
1 with 9 completions
13 with 10 completions
... etc etc
2035 with 200 completions

Total of about 110000 of them.

And for what it's worth, I also have some 15s with as few as 596 completions.

I don't post these on my site in case they are mistaken for valid 1-completion puzzles, but of course I am happy to put some here if anyone is interested.

Cheers

gordon

[Moschopulus]

I don't post these on my site in case they are mistaken for valid 1-completion puzzles, but of course I am happy to put some here if anyone is interested.

I would be interested to see the ones with up to 10 or 20 completions. Some small number that doesn't create much work for you.

I'd also like to see a few 15s with a small number of completions. Thanks!

One of the two solutions to the 16 with two solutions is
562389471849716253137425896358194627974263185216857349691542738725638914483971562

How many 17s have you found in this grid?