Max number of clues 2

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

Postby ravel » Tue Jul 17, 2007 10:13 am

Thank you two, champagne is ordered:)

ronk wrote:It looks like it's in row-order minlex form ... but gsf's canonicalization yields a different result. What "normalization" did you use?
The 37, i have it from, was gsf-canonicalized, but the 1off/2on changed it.

btw, sorry udosuk, for having destroyed the symmety:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Tue Jul 17, 2007 10:24 am

ravel wrote:Hey, another look and here it is:

a great find
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Tue Jul 17, 2007 12:02 pm

to ravel
Code: Select all
+---+---+---+
|312|67.|.54|
|7..|4..|.36|
|.46|5..|..2|
+---+---+---+
|.71|3..|.68|
|.6.|2.7|..3|
|..3|.6.|...|
+---+---+---+
|...|.2.|.4.|
|1.7|8..|..5|
|.24|7.5|.81|
+---+---+---+


Congratulations on the 38...only you really know how difficult it was to find !

Very well done.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby JPF » Tue Jul 17, 2007 1:55 pm

Congratulations, ravel
Not easy to find mini minimals (17s) and maxi minimals at the same time:)

ronk wrote:BTW I think you should scramble it. Why make it easy for people to simply guess that r1c4=4?

Use this one:) :
Code: Select all
 *-----------*
 |123|.56|78.|
 |.57|.8.|2..|
 |6..|.7.|51.|
 |---+---+---|
 |.1.|..5|...|
 |.36|.1.|95.|
 |..5|62.|1..|
 |---+---+---|
 |36.|.9.|8..|
 |...|..2|.7.|
 |.72|86.|39.|
 *-----------*

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

Postby udosuk » Tue Jul 17, 2007 1:58 pm

ravel wrote:btw, sorry udosuk, for having destroyed the symmetry:)

I did mention 38 is my favourite number.:D So congrats and well done!:)

You can make it symmetrical again by finding a 16!:!: Nothing is impossible (yet)!:?:

Just a random thought, if some of those huge multi-billionaire corporations are willing to make those $1-million-prize offer for the discovery of a valid 16-clue Sudoku puzzle (or to prove the inexistence of it) perhaps it would lure those maths/combinatorics big guns to really devote their effort working on it!:idea:

Added later:

Thanks to some magnificient fishing work by Danny & Ron, I could solve this puzzle using a sashimi swordfish plus one each of x-wing, y-wing and xy-wing::)
Code: Select all
 *-----------------------------------------------------------------------------*
 | 3       1       2       | 6       7       89      | 89      5       4       |
 | 7       589     589     | 4       189    #1289    | 189     3       6       |
 | 89      4       6       | 5       1389    1389    | 1789    179     2       |
 |-------------------------+-------------------------+-------------------------|
 | 2459    7       1       | 3       459     49      | 2459    6       8       |
 | 4589    6       589     | 2       14589   7       | 1459    19      3       |
 |-24589  -589     3       |*19      6      -1489    |-124579 -1279   *79      |
 |-------------------------+-------------------------+-------------------------|
 |-5689   -3589   -589     |*19      2      -1369    |-3679    4      *79      |
 | 1       39      7       | 8       349     3469    | 2369    29      5       |
 | 69      2       4       | 7       39      5       | 369     8       1       |
 *-----------------------------------------------------------------------------*
x-wing of {9} in r67c49: r6c12678<>9, r7c12367<>9
hidden single of {2} in b2: r2c6=2
Code: Select all
 *--------------------------------------------------------------------*
 | 3      1      2      | 6      7      89     | 89     5      4      |
 | 7     #589   #589    | 4      189    2      | 189    3      6      |
 |-89     4      6      | 5      1389   1389   | 1789  *179    2      |
 |----------------------+----------------------+----------------------|
 | 2459   7      1      | 3      459    49     | 2459   6      8      |
 | 4589   6     *589    | 2      14589  7      | 1459  *19     3      |
 | 2458   58     3      | 19     6      148    | 12457  127    79     |
 |----------------------+----------------------+----------------------|
 | 568    358    58     | 19     2      136    | 367    4      79     |
 | 1     *39     7      | 8      349    3469   | 2369  *29     5      |
 | 69     2      4      | 7      39     5      | 369    8      1      |
 *--------------------------------------------------------------------*
sashimi swordfish of {9} in r358c238 with fin in r2c23: r3c1<>9
naked single: r3c1=8
Code: Select all
 *--------------------------------------------------------------------*
 | 3      1      2      | 6      7     #89     |#89     5      4      |
 | 7     *59    *59     | 4      189    2      | 189    3      6      |
 | 8      4      6      | 5      139    139    | 179    179    2      |
 |----------------------+----------------------+----------------------|
 | 2459   7      1      | 3      459    49     | 2459   6      8      |
 | 459    6     -589    | 2      14589  7      | 1459   19     3      |
 | 245   *58     3      | 19     6      148    | 12457  127    79     |
 |----------------------+----------------------+----------------------|
 | 56    -358   *58     | 19     2      136    | 367    4      79     |
 | 1      39     7      | 8      349    3469   | 2369   29     5      |
 | 69     2      4      | 7      39     5      | 369    8      1      |
 *--------------------------------------------------------------------*
y-wing of {58} in r6c2+r7c3 with strong link of {5} in r2c23: r5c3<>8, r7c2<>8
hidden single of {8} in b4: r6c2=8
hidden single of {8} in c6: r1c6=8
naked single: r1c7=9
Code: Select all
 *--------------------------------------------------------------------*
 | 3      1      2      | 6      7      8      | 9      5      4      |
 | 7      59     59     | 4     #19     2      | 18     3      6      |
 | 8      4      6      | 5      139    139    |#17    *17     2      |
 |----------------------+----------------------+----------------------|
 | 2459   7      1      | 3      459    49     | 245    6      8      |
 | 459    6      59     | 2      14589  7      | 145   *19     3      |
 | 245    8      3      | 19     6      14     | 12457 -127   *79     |
 |----------------------+----------------------+----------------------|
 | 56     35     58     | 19     2      136    | 367    4      79     |
 | 1      39     7      | 8      349    3469   | 236    29     5      |
 | 69     2      4      | 7      39     5      | 36     8      1      |
 *--------------------------------------------------------------------*
xy-wing of {179} in r3c8+r6c9 with pivot {19} in r5c8: r6c8<>7
hidden single of {7} in c8: r3c8=7
naked single: r3c7=1
hidden single of {1} in b2: r2c5=1
hidden single of {1} in r5: r5c8=1

And naked singles will solve the rest!:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ravel » Tue Jul 17, 2007 6:50 pm

I am honoured by the congrats again, thanks to all.

udosuk, so we almost found the same solutions:)
udosuk wrote:Just a random thought, if some of those huge multi-billionaire corporations are willing to make those $1-million-prize offer for the discovery of a valid 16-clue Sudoku puzzle (or to prove the inexistence of it) perhaps it would lure those maths/combinatorics big guns to really devote their effort working on it!
Hm, i would not invest a penny for a 16 clues search, i am very sure, that there is none and i think, a million dollar prize is not enough for the costs of a proof, that it does not exist.
Note, that the new found 17's become more and more loneley, and - different to the minimal high clues - for a 16 clue there must be at least the 64 17's and a lot of 18's around and it is very unprobable, that they never would have been found so far.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Havard » Tue Jul 17, 2007 9:34 pm

ravel wrote:
udosuk wrote:Just a random thought, if some of those huge multi-billionaire corporations are willing to make those $1-million-prize offer for the discovery of a valid 16-clue Sudoku puzzle (or to prove the inexistence of it) perhaps it would lure those maths/combinatorics big guns to really devote their effort working on it!
Hm, i would not invest a penny for a 16 clues search, i am very sure, that there is none and i think, a million dollar prize is not enough for the costs of a proof, that it does not exist.
Note, that the new found 17's become more and more loneley, and - different to the minimal high clues - for a 16 clue there must be at least the 64 17's and a lot of 18's around and it is very unprobable, that they never would have been found so far.


I am not quite so pessimistic....:) If you look at Gordons list it keeps a steady growth, and over a thousand 17 has been found in the last few months. I think the total number of 17's is way over 50000, and in that case a 16 is not at all improbable. But first lets find a 39!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Mauricio » Wed Jul 18, 2007 1:15 am

Wow!, very impressive work! Nice 38
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby ravel » Wed Jul 18, 2007 3:07 pm

Thanks.

I stopped my search now. The following 37's have not been posted yet. For none of them i have made a 2off/2on. I also have a list of almost 700 36's, for which i did not make a 1off/2on, if someone is interested.

003400009450009200098372405080031904340007108019800020000023801000000000031708500
003400009450080130089230506000000000500020900941860250305600400610000390094300605
020006700400109006069072154008907065096000470000000900082600547010700002004025010
103000089057109030690300510001900005765001093900007160376804050500700048000000000
103056709050000006609207001200063000315902608006501002530008900000000000901705803
103056780057080200600270510010005000036010450005620100360040800000000020072860340
120056709050009206609207001200060000315902608006501000530008007000000100901005803
123006709000709103090000000261308904000040000040600802600003400012064307034807200
123056709050000200609007000200001300015002608006503002531608907000000000900715803
123056780057080200600070510010005000036010450005620100360040800000000020072860340
123406089400000000009200004208690010391702068000000000730900041804007090010304870
020000700400109006069072154008907065096000470000060900082600547010700002004025010
100056000007000006609027014201000405000000000905042801002005608506008147708064052
103056080057080030608730015216070050700005002005600000300068041000300000061047023
103406780000000000608037104205070600800024500034605020302500400501743060000002005
103450089400109000009030040241903057030500094905700000310802075502370000000000020
120000000007100000089730041060801090098670012710920006070308024840207630000060000
120056709050009206609007000200061000315902608006500002501708903000000000930005807
123006709006709003090000000261308904000040000040600802600003400012064307034807200
123056709050000200609007000200001300015902600006503002500718903000000000931605807
000000000400109206689203400030800504506001800008305160394502608005008042000000305
000000000450009030980300054004907560590630027670500003040260070700003600860700342
003400009450009200098372405000031904340007108019800020000023801800000000031708500
100006700007000006680002514230804000500203148000000000360015807705308061800607050
103006709057009003600003015261045007000000100700020006316092074072064901900000000
120450080050080000608000004200018070710520008805670002000000000570041096901265047
123056709050000006609207001200061300315902608006500002500700903000000000931000807
000000700057180206680027501004801003030060000068530002376048105800000304045010000
000006000400180036800030140280617390010890027090003000070900003600070910940061078
000400080400009206968302054205000007640507802080204000070000000506903070890705603
000400080407000036086203054204937008008640000069802047605728090000000000002300075
000406009400080030869023014204037060080000003930804027398601002000000000602008091
003000000450109006609003501201004653006002800500000002000208960860901025902005108
003000000450109006609003501201004653006002800500000002005208960860901020902005108
003006700000180030860037510035874900678901300000003000086705490004000000790048050
003406789000000000089003406031800007548307091900105000005000008010500904804601305
003456709000089063009003400034561908010097004905040600048075006501000807000000000
020000009407009000090273054000000010014038927089012043005027001042001375001300000
020000009407009030098273054000000010014038927089012043000027001040001375001300000
020000009407009030098273054000000010014038927089012043000027001042001075001300000
020000009407080000090273054000000010014038927089012043005027001042001375001300000
020000700057180206800020014000000005045690870760800400502960140610070900004210007
020000700057180206800020014000000005045690870760800400572960140610070900004210000
020000709407009030098203054000000010014038927089012043000027001040001375001300000
020000709407009030098203054000000010014038927089012043000027001042001075001300000
020050780057180006680200501000000000060910400790540162072890610800700024000020800
020050780057180206680200501000000000060910400790540162072890610800700004000020800
023450089407080200090200004000000000305010027019500308002001403031740090904020071
023450089407180000000200004019570308305000927000000000002001403031740092904020001
023450089407180200090200004000000000305000027019500308002001403031740090904020071
023450089407180200090200004000000000305010027019500308002000403031740090904020071
100406009400080036680730014000897065008600003960003000004000000590078041810904050
100406009400180036680730014000890065008600003960003000004000000590078041810904050
100406009407180036680730014000890065008600003960003000004000000500078041810904050
103400080450000036869003100000000000586000071901075460300008600690037814000040053
103400080450000036869003140000000000586000071901075460300008600690037810000040053
103456009000009030009000405205061304300502000010040002000090000802014093901235048
120006089400109206000000000208031064000008003930760020340800690702093048800000302
120006089400109206000000000208031064000008003930760820340800690702093040800000302
120456700000009000690237140246705300300002407000000060000000900062903004900524670
123056780057000200600000510206710950010020000005630100300000000060892370072360090
123056780057000200600000510236710950010020000005630100000000000060892370072360090
123056780057080200600000510230710950010020000005630100000000000060892370072360090
123056780057080200600000510236710050010020000005630100000000000060892370072360090
123056780057080200600000510236710950010020000005600100000000000060892370072360090
123056780057080200600070510236710050010020000005600100000000000060892370072360090
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Wed Jul 18, 2007 5:21 pm

ravel wrote:
ronk wrote:... -m1 -e"C==37"
Dont use this option. In the time my program found 2 37's and 44 new 36's (from a list with 39 36's), -goc{-1+1} -m1 -e"C==36" only gave me 2 36's.

the problem here is -m1 which only derives 1 minimal puzzle from each generated puzzle
-m will derive all minimal puzzles from each generated puzzle
-e"C==37" limits the output to exactly 37 clues
-e"C>=37" would be the optimists choice for this thread

the -e clue limit exposed a (waste of computation) weakness in the minimization code that does not take -e into account
I reposted the solver and it handles -m.M, which cuts off the minimal puzzle derivation at M clues
so -m.37 would efficiently derive minimal puzzles with 37 or more clues
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Wed Jul 18, 2007 7:06 pm

ravel wrote:At the time it is not even completely proved, that a 10 cell sudoku cant be unique..

What are the links related to this topic ?

What about n = maximum number of clues of a minimal puzzle?
Obviously n<=72 …

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

Postby coloin » Wed Jul 18, 2007 7:39 pm

I dont think there is a thread which deals with an attempt to prove that min clues is not 10,11,12,13,14,15,or 16.

min = 8 is trivial
min =9 im not sure if even this is proved !

JPF wrote:What about n = maximum number of clues of a minimal puzzle?
Obviously n<=72 …

Ah I see what you mean.......I think it should be easy to prove that itis less than 50 .......I will think...

Although an optimistic Havard probably has a chance at a John Buchan [39].....at least more chance than a Ringo Star [16]

On that line - quite possibly with all the 36s and 37s found we might have a minimal 2-stepper ?

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby ravel » Thu Jul 19, 2007 7:17 am

JPF wrote:
ravel wrote:At the time it is not even completely proved, that a 10 cell sudoku cant be unique..
What are the links related to this topic ?
I have searched the forum for this topic some time ago and all i found was this thread.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Thu Jul 19, 2007 5:28 pm

There is a bit more on the subject here
But still no real proof.

I think statistically we should be able to quote an improbability figure which makes a 16 extremely unlikely.

for example if we make up an improbabilty eg 1 in 10^64 [but is this proof ?]

If we had a 16 puzzle, it would have 16 15-clue subpuzzles.

At least one of these 15-clue subpuzzles will have a 17-clue puzzle with a 2on method - after all we are after any 2 clues to perform what a single clue did.

If you take a remote 17 and do a {-1+2} you get 260 different minimal 18s

You could argue that each of those 15-clue subpuzzles will have at least one 17 in 2on distance.

We havn't found any of these 17s yet.

So if the chance that a 17 is new is ?5000 in 40908 [to date]

We need all 16 of these new 17s not to have been found yet.

That works out at 1 in 8^16 = 1 in 281474976710656.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby coloin » Thu Jul 19, 2007 7:10 pm

Rather more on topic......

Has any one seen a minimal puzzle with 7 clues of one value

If not then the max number of clues is </= to 54

Observationally, one clue value tends to be absent.......so that makes it </= 48 clues.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

PreviousNext

Return to General