Structures of the solution grid

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

Postby Ocean » Wed Aug 30, 2006 3:28 pm

Red Ed wrote:A systematic search for grids with no fully-entwined pairs yields just one answer, up to isomorphism, namely this 78 (which I suppose we could call the "Platinum trellis", Pt, atomic number 78):
Code: Select all
 
123|456|789
457|189|326
689|327|154
---+---+---
231|645|897
745|891|632
896|732|541
---+---+---
318|264|975
574|918|263
962|573|418

A puzzle with 20 clues, having the Pt grid as its solution:
Code: Select all
...|...|78.
.5.|1.9|...
...|.2.|..4
---+---+---
..1|.4.|...
...|8..|..2
.9.|...|5..
---+---+---
3..|2..|...
..4|...|.63
...|57.|...
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Red Ed » Wed Aug 30, 2006 4:37 pm

Moschopulus wrote:It remains to do a search fixing the other three clues in 14, 21, 24. I'll start on 14.
I'll be community-spirited and do 21 and 24.

Update: done. No 19s.
Last edited by Red Ed on Thu Aug 31, 2006 1:57 am, edited 1 time in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby udosuk » Thu Aug 31, 2006 3:53 am

Having been an interested onlooker from the side for long, I just want to seek clarification for some of the remarkable results found so far (it's too difficult to catch up with all that's posted):

The "Platinum trellis" (Pt), is the only grid (barring isomorphism) which contains NO fully-entwined pairs (out of 36 possible pairings)... And probably have the largest possible number of "2-digit unavoidables" (78)... And is conjectured to be one of the grids which could not give a 19-clue puzzle, but only 20-clue puzzles (how many such grids are there?)...

Red Ed has also found the total of 127 grids which contain 36 (the maximum) fully-entwined pairs... Are they posted somewhere? So these grids are supposed to have the smallest possible number of "2-digit unavoidables"? And are more probable to give 17-clue puzzles?

The "most canonical grid" (123456789456789123789123456231564897564897231897231564312645978645978312978312645) is conjectured to NOT giving any 19-clue puzzle, but only ONE 20-clue puzzle (barring isomorphism)? Is it the ONLY one? Are there any grids which NO puzzles with 20 clues or fewer are found? Are there other grids which also give at most ONE 20-clue puzzle (up to isomorphism)?

Thanks for the help...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Red Ed » Thu Aug 31, 2006 5:56 am

udosuk wrote:The "Platinum trellis" (Pt), is the only grid (barring isomorphism) which contains NO fully-entwined pairs (out of 36 possible pairings)...
Yes.
And probably have the largest possible number of "2-digit unavoidables" (78)...
I'd be happier with "possibly" rather than "probably" but, yes, that's the gist.
And is conjectured to be one of the grids which could not give a 19-clue puzzle, but only 20-clue puzzles
I've finished my two branches of the 19 search, with no success. Assuming Moschopulus also turns up no 19s in his search then, yes, no 19s. Ocean's supplied a 20.
(how many such grids are there?)...
No idea.

Red Ed has also found the total of 127 grids which contain 36 (the maximum) fully-entwined pairs... Are they posted somewhere?
No, not posted yet. I keep meaning to generate some stats to go with them first. I'll get round to that soon, or just post the bare grids.
So these grids are supposed to have the smallest possible number of "2-digit unavoidables"?
The smallest number of minimal unavoidable sets comprising just 2 digits, yes. In a random grid, a pair of digits gives rise to 1, 2, 3 or 4 minimal unavoidable sets; in the 127 FE grids, each pair gives rise to just 1.
And are more probable to give 17-clue puzzles?
Mmm... that might be a "yes", but not in a useful way. You can generate all sorts of statistics that try to capture what is good about 17-capabable grids. The statistic, Unav, that counts the number of minimal 2-digit unavoidables is more-or-less as good as any other, in the sense that there's a c. 80% chance that a 17-capable grid will "beat" a random grid by that measure. However, this only means that better Unav statistic => better chance of a 17, not that better Unav statistic => good chance of a 17!!. In fact I would be surprised if any more 17-capable solution grids (beyond those derived from gfroyle's puzzles list) will be discovered.

The "most canonical grid" (123456789456789123789123456231564897564897231897231564312645978645978312978312645) is conjectured to NOT giving any 19-clue puzzle, but only ONE 20-clue puzzle (barring isomorphism)? Is it the ONLY one? Are there any grids which NO puzzles with 20 clues or fewer are found? Are there other grids which also give at most ONE 20-clue puzzle (up to isomorphism)?
Someone else had better comment on that. I'll just say that I am sure Ocean will find more 20s in the Pt grid if he goes looking, since if there was (essentially, up to 6-way automorphism) only one 20 then it would have been too much of an achievement to have found it so quickly ... even for Ocean's magic puzzle-discovery methods!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Moschopulus » Thu Aug 31, 2006 8:19 am

Red Ed wrote:
And is conjectured to be one of the grids which could not give a 19-clue puzzle, but only 20-clue puzzles
I've finished my two branches of the 19 search, with no success. Assuming Moschopulus also turns up no 19s in his search then, yes, no 19s. Ocean's supplied a 20.

Finished and no 19 found. So the PT grid has no 19.


The "most canonical grid" (123456789456789123789123456231564897564897231897231564312645978645978312978312645) is conjectured to NOT giving any 19-clue puzzle, but only ONE 20-clue puzzle (barring isomorphism)?


I suggest we call the "most canonical" grid the MC grid for short. It helps to have short names when we are talking about grids a lot.

I announced the MC grid has no 19 here

The next thing to do is search it for 20s. coloin suggested it might only have one 20 up to isomorphism.

I don't think we know of any grid that has no 19 and only one 20 up to isomorphism.

It would be nice in a way if MC were the only grid to have exactly one 20 up to isomorphism. This would distinguish it in another way.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby RW » Thu Aug 31, 2006 1:33 pm

Moschopulus wrote:I don't think we know of any grid that has no 19 and only one 20 up to isomorphism.

It would be nice in a way if MC were the only grid to have exactly one 20 up to isomorphism. This would distinguish it in another way.


This search could probably be significantly speeded up if you introduced unavoidables that require 2-clues to checker:

Code: Select all
a . . | b . . | c . .
b . . | c . . | a . .
c . . | a . . | b . .


Size 9 sets of this type needs 2 given clues to give a unique solution. The MC grid has 9 disjoint sets of this type -> MCN 18. Ha, just proved that a grid cannot have a 17 in only 2 minutes!:D The Pt-grid would have a MCN of 16 if one consideres this kind of sets, the first 14 mentioned by unavoid leaves a full 9-digit set that requires 2 -digits in r789c258.

[edit: to further speed things up, not only does a 9 digit set like that require 2 given clues, it requires two clues that has to be in both different rows and different columns, giving only 18 possible ways to solve it uniquely with 2 clues.]

RW
Last edited by RW on Thu Aug 31, 2006 9:52 am, edited 2 times in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby udosuk » Thu Aug 31, 2006 1:45 pm

Thanks for all the kind replies, guys...:)

So the PT and MC are both special in their own ways... I think coloin has kept a list of all these special solution grids... Perhaps he could make a "Hall of Fame of solution grids" some time soon...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby coloin » Thu Aug 31, 2006 2:32 pm

I think many , if not all, of the grids with 6 and less fully entwined pairs will not have a 19, as well as many of the canonical varients.
Code: Select all
MC      123456789456789123789123456231564897564897231897231564312645978645978312978312645
PT      123456789457189326689327154231645897745891632896732541318264975574918263962573418

Code: Select all
          Bands                         No. of 20s    Max clues   MCN   Av.puzz.size
MC        1   1   1  ,   1   1   1         648           36        12      25.70
PT        132 132 132  , 414 414 414       6             34        15      25.55

Code: Select all
Canonvant  123456789789123456456789123231548967564937218897612345312875694645391872978264531   
Dukuso16   145726983837495261926381574293874156581269347674153892318547629459632718762918435   
Rw         123469785456187932789253164371694528698512347542378691215946873864735219937821456   
74-2digit  384217965512936478967458321841672593725349186693185247259763814136894752478521639   

Code: Select all
              Bands                      No. of 20s     Max clues   MCN   Av.puzz.size
Canonvant    1  53  53  ,   1 138 138       184           34         14   25.33
Dukuso16     97 139  52  ,  52  97 139       ?            34         16   24.89   
Rw           131 148 244  , 131 148 244      ?            35         13   24.81
74-2digit    51  70  70  ,  85 131  80       ?            ?          15   24.90


Updated as more data accumulated
C
Last edited by coloin on Fri Dec 01, 2006 7:42 pm, edited 3 times in total.
coloin
 
Posts: 1709
Joined: 05 May 2005

Postby Moschopulus » Thu Aug 31, 2006 3:39 pm

RW wrote:This search could probably be significantly speeded up if you introduced unavoidables that require 2-clues to checker


Yes, definitely. I first posted on these sets here and I called them (9,2) unavoidable sets.
(I can't believe you didn't find that:D )

We didn't cater for them in checker because most grids don't have any, so it didn't seem worth the extra effort.

dukuso here observed the same thing as you in the MC grid, and he used that to quickly check there is no 18.

In case anyone is running checker for the MC grid, I should say a couple of things. First, something that may be helpful. We have done some experiments and checker128 appears to be the fastest version for the MC grid.

Secondly, you may have noticed that after taking the usual 2 minutes (approx) to find the unavoidable sets, checker takes ages (maybe 15 minutes) before announcing the MCN and starting the search. The MC grid is "worst case" for checker in this way. Because the algorithm we use for finding the max clique is written by us and is really inefficient, it happens to be found out by this grid. For almost any grid our bad programming is not found out and the computation takes only a few seconds. For the MC grid all the unavoidable sets have size 6 (there are none of sizes 4, 8, 9, 10, 11, 12) and this causes the delay. Sorry.

We didn't write a way to save the max clique because for almost any grid it makes no difference. It wasn't worth the extra effort. Unfortunately for the MC grid it makes a difference of maybe 15 minutes.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby RW » Sat Sep 02, 2006 2:58 pm

coloin wrote:I think many , if not all, of the grids with 6 and less fully entwined pairs will not have a 19, as well as many of the canonical varients.


I think it's easier to find a connection between the total amount of 2-digit unavoidables and the abscense of 19 clue puzzles. The first puzzle found not to have a 19 (here) has 21 FE-pairs, but 68 2-digit unavoidables. If we assume Gordon's list to be complete, then no grid with more than 63 2-digit unavoidables can give a 17. My guess is that the upper limit for a grid that can give an 18 is somewhere around 67-68 and the upper limit for a 19 is 70 or 71. I printed out some quick statistics on the 2-digit unavoidables in 10 million random grids (2*5M):

Code: Select all
5M2.dat:
Grids with more than 63 2-digit unavoidables: 13644
Grids with more than 70 2-digit unavoidables: 2

5M3.dat:
Grids with more than 63 2-digit unavoidables: 13660
Grids with more than 70 2-digit unavoidables: 2


Only 0.27% of the grids are completely unsuitable for 17s in this sence and one grid in 2.5 million is unlikely to have a 19. Of course there is grids with 70 or less 2-digit unavoidables that give no 19s, so we cannot make any assumption on the total amount of such grids based on this.

Moschopulus wrote:Yes, definitely. I first posted on these sets here and I called them (9,2) unavoidable sets.
(I can't believe you didn't find that )


Sorry, still haven't read all of that thread... but I'm working on it.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Red Ed » Wed Sep 06, 2006 9:21 am

OK, so I said I'd get around to posting the 127 fully-entwined representative grids eventually and here they are. I have done a little analysis as follows. I call two sudoku grids quasi-equivalent iff you can get from one to the other by any combination of
  1. relabelling the digits
  2. transposing the whole grid
  3. permuting the order of the bands and stacks
  4. permuting the order of the minirows and minicols within each box independently
Note that of course (d) is not a validity-preserving transformation so is disallowed under the normal notion of grid equivalence.

Quasi-equivalence is weaker than ordinary equivalence, partitioning the full set of all 6.67e21 grids into approximately 3.8bn classes (cf. 5.4bn for ordinary equivalence). The fully-entwined grids make up exactly 18 of those classes. It is a nice feature of quasi-equivalence that a grid G is fully-entwined iff all of its quasi-equivalent friends are too.

I've listed the essentially-different members of each of the 18 fully-entwined classes (making 127 representative grids as originally advertised) in the following format:
Code: Select all
Class 1 : counts 122033 122033 122059 122059 123397 129624
  1a 123456789456789123789231564234178956695342817817695342368527491572914638941863275 (RV)
  1b 123456789456789123789231564234178956695342817817695342368914275572863491941527638
  1c 123456789456789123789231564234695817695178342817342956368527491572914638941863275
  1d 123456789456789123789231564234695817695178342817342956368914275572863491941527638
  1e 123456789456789123789231645267394851815627394934518276348175962571962438692843517
  1f 123456789456789123897231645234567918675918234918342567369174852582693471741825396
The "counts" are the number of grid completions from each of the six generalised diagonals. These counts are preserved by the operations (a,b,c,d) and were originally what made me notice the 18 classes: it turns out that same six counts <=> same one of the 18 classes. The classes are ordered by the "size" of the counts in some sense that I don't quite remember (not average, I don't think, but something like it). You might hope that the grids in the earlier classes (smallest counts) are more amenable to having low-clue puzzles than grids in the later classes.

The three fully-entwined (FE) grids found prior to this exhaustive search were SFB (a.k.a. FE 2e), RV (FE 1a) and RW's grid FE 8b. I believe SFB has been searched without success for a 16. I can also confirm that RV and FE 6a (the only FE grid to be the sole representative of its class) have no 16. I've not checked RW's grid.

All gripping stuff:) The full list of 127, from 1a to 18f, is enclosed below in tiny font. Enjoy ...

Class 1 : counts 122033 122033 122059 122059 123397 129624
1a 123456789456789123789231564234178956695342817817695342368527491572914638941863275 (RV)
1b 123456789456789123789231564234178956695342817817695342368914275572863491941527638
1c 123456789456789123789231564234695817695178342817342956368527491572914638941863275
1d 123456789456789123789231564234695817695178342817342956368914275572863491941527638
1e 123456789456789123789231645267394851815627394934518276348175962571962438692843517
1f 123456789456789123897231645234567918675918234918342567369174852582693471741825396

Class 2 : counts 123338 123338 124842 124842 139145 142355
2a 123456789456789123789231645267394851518627394934815276375148962692573418841962537
2b 123456789456789123789231645267394851518627394934815276375962418692148537841573962
2c 123456789456789123789231645267815394518394276934627851375962418692148537841573962
2d 123456789456789123798231645275148936639527418814963257347615892561892374982374561
2e 123456789456789123798231645275148936639527418814963257347892561561374892982615374 (SFB)
2f 123456789456789132789231564268573491375914628941862357512348976697125843834697215

Class 3 : counts 117944 118830 123393 139118 140788 146501
3a 123456789456789123798231564234178956619524837875693412367915248582347691941862375
3b 123456789456789123798231564275943618369815472841627395587362941612594837934178256

Class 4 : counts 122871 127727 127727 132673 132673 151155
4a 123456789456789123789231645267394851394518276815627934571863492638942517942175368
4b 123456789456789123789231645267394851394518276815627934571942368638175492942863517
4c 123456789456789123789231645267518934394627851815394276571942368638175492942863517
4d 123456789456789123798231645269345817345817962871962534582673491637194258914528376
4e 123456789456789123798231645269817534345962817871345962582673491637194258914528376
4f 123456789456789132789231564268194357375862941914573628592318476647925813831647295

Class 5 : counts 119803 121448 121497 132165 145417 155112
5a 123456789456789132789213645237964518618375294945821376374592861591638427862147953
5b 123456789456789132789213645294537861315968427867142953538671294672394518941825376

Class 6 : counts 126012 126116 129394 132055 139600 162605
6a 123456789457289163698713254261847935579362841834591627315928476786134592942675318

Class 7 : counts 130632 139448 153912 159778 161445 174288
7a 123456789456789123789231645234697851678125394915843276347562918562918437891374562
7b 123456789456789123789231645234697851678125394915843276347918562562374918891562437
7c 123456789456789123798231645239814567567392814814675392345968271672143958981527436
7d 123456789456789132789231564271864395635912847948573216397628451514397628862145973

Class 8 : counts 130974 147938 160941 163734 166677 171732
8a 123456789456789123798231645267843591815697234934125867372918456581364972649572318
8b 123456789456789132789231564235697418671842395948315627394178256567923841812564973 (RW)

Class 9 : counts 166961 168818 186404 186807 206053 206053
9a 123456789456789123789231564234567891615894237978312645367148952592673418841925376
9b 123456789456789123789231564234567891615894237978312645367925418592148376841673952
9c 123456789456789123789231564234567918615894372978312456367148295592673841841925637
9d 123456789456789123789231564234567918615894372978312456367925841592148637841673295
9e 123456789456789123789231564234675891615948237978123645367592418592814376841367952
9f 123456789456789123789231564234675891615948237978123645367814952592367418841592376
9g 123456789456789123789231564234675918615948372978123456367592841592814637841367295
9h 123456789456789123789231564234675918615948372978123456367814295592367841841592637
9i 123456789456789123897231645231897456568314297974562318349175862682943571715628934
9j 123456789456789123897231645231897456568314297974562318349628571682175934715943862
9k 123456789456789123897231645231978456568143297974625318349517862682394571715862934
9l 123456789456789123897231645231978456568143297974625318349862571682517934715394862
9m 123456789456789123897231645231978456568143972974625831349517268682394517715862394
9n 123456789456789123897231645231978456568143972974625831349862517682517394715394268
9o 123456789456789123897231645268394517571862394934517268312978456685143972749625831
9p 123456789456789123897231645268394517571862934934517268312978456689145372745623891

Class 10 : counts 181166 185256 185256 204364 206053 231114
10a 123456789456789123789231564238597416645312978971864352367148295592673841814925637
10b 123456789456789123789231564238597416645312978971864352367925841592148637814673295
10c 123456789456789123789231564238597641645312897971864235367148952592673418814925376
10d 123456789456789123789231564238597641645312897971864235367925418592148376814673952
10e 123456789456789123789231564238975416645123978971648352367592841592814637814367295
10f 123456789456789123789231564238975416645123978971648352367814295592367841814592637
10g 123456789456789123789231564238975641645123897971648235367592418592814376814367952
10h 123456789456789123789231564238975641645123897971648235367814952592367418814592376
10i 123456789456789123897231645231564897568397412974812356349175268682943571715628934
10j 123456789456789123897231645231564897568397412974812356349628571682175934715943268
10k 123456789456789123897231645231645897568973412974128356349517268682394571715862934
10l 123456789456789123897231645231645897568973412974128356349862571682517934715394268
10m 123456789456789123897231645238145976564978231971623458349517862682394517715862394
10n 123456789456789123897231645238145976564978231971623458349862517682517394715394862
10o 123456789456789123897231645268394517571862394934517862319625478645978231782143956
10p 123456789456789123897231645268394571571862934934517268312645897649178352785923416

Class 11 : counts 195708 195708 197193 197193 199755 227186
11a 123456789456789123789231564231645897645978312897312456368194275572863941914527638
11b 123456789456789123789231564231645897645978312897312456368527941572194638914863275
11c 123456789456789123789231564231978456645312897897645312368194275572863941914527638
11d 123456789456789123789231564231978456645312897897645312368527941572194638914863275
11e 123456789456789123897231645231564978645978231978312564369147852582693417714825396
11f 123456789456789123897231645231564978645978231978312564369825417582147396714693852

Class 12 : counts 196740 196740 199755 199755 199755 227186
12a 123456789456789231789123645231564897564897312978312564395248176617935428842671953
12b 123456789456789231789123645231564897564897312978312564395671428617248953842935176
12c 123456789456789231789123645231564978645897312897312456368275194572941863914638527
12d 123456789456789231789123645231564978645897312897312456368941527572638194914275863
12e 123456789456789231789123645231897456564231897978645123347518962692374518815962374
12f 123456789456789231789123645231897456564231897978645123347962518692518374815374962

Class 13 : counts 195708 195708 229088 229088 229088 229088
13a 123456789456789123789231645231564897564978312897312564348195276672843951915627438
13b 123456789456789123789231645231564897564978312897312564348627951672195438915843276
13c 123456789456789123789231645231978564564312897897564312348195276672843951915627438
13d 123456789456789231789123645237945168561378924894612573378561492612894357945237816

Class 14 : counts 197193 197193 228068 228068 229088 229088
14a 123456789456789123789231645231564897645897312978312456394175268517628934862943571
14b 123456789456789123789231645231564897645897312978312456394628571517943268862175934
14c 123456789456789123789231645231564897645978231897123456374692518518347962962815374
14d 123456789456789123789231645231564897645978231897123456374815962518692374962347518
14e 123456789456789123789231645231897456564123897978645231347518962692374518815962374
14f 123456789456789123789231645231897564564123978897564231375618492618942357942375816
14g 123456789456789231789123645234615897567948312891372456345297168678531924912864573
14h 123456789456789231789123645234975168567318924891642573345261897678594312912837456

Class 15 : counts 199755 227186 229088 229088 229088 229088
15a 123456789456789123789231564231564897564978312897312645348195276672843951915627438
15b 123456789456789123789231564231564897564978312897312645348627951672195438915843276
15c 123456789456789123789231564231897645564312978897645231375168492618924357942573816
15d 123456789456789123789231564231897645564312978897645231375924816618573492942168357
15e 123456789456789123789231564267195438591843276834627951312564897645978312978312645
15f 123456789456789123789231564267195438591843276834627951312978645645312897978564312
15g 123456789456789123789231564267843951591627438834195276312564897645978312978312645
15h 123456789456789123789231564267843951591627438834195276312978645645312897978564312
15i 123456789456789123897231645269347518581692374734815962312564897645978231978123456
15j 123456789456789123897231645269347851581692437734815296312564978645978312978123564
15k 123456789456789123897231645269815374581347962734692518312564897645978231978123456
15l 123456789456789123897231645269815437581347296734692851312564978645978312978123564

Class 16 : counts 227186 227186 228068 228068 229088 229088
16a 123456789456789123789231564231564897564897312897123645348672951672915438915348276
16b 123456789456789123789231564231564897564897312897123645348915276672348951915672438
16c 123456789456789123789231564231897456564312897897645231375168942618924375942573618
16d 123456789456789123789231564267348951591672438834915276312564897645897312978123645
16e 123456789456789123789231564267348951591672438834915276312897645645123897978564312
16f 123456789456789123789231564267915438591348276834672951312564897645897312978123645
16g 123456789456789123897231645231978456645312897789645231368194572572863914914527368
16h 123456789456789123897231645231978564645312978789645312368194257572863491914527836

Class 17 : counts 229088 229088 229088 229088 252136 252136
17a 123456789456789123789231564231564897645897231978312645367148952592673418814925376
17b 123456789456789123789231564231564897645897231978312645367925418592148376814673952
17c 123456789456789123789231564231564978645897312978312456367148295592673841814925637
17d 123456789456789123789231564231564978645897312978312456367925841592148637814673295
17e 123456789456789123789231564231645897645978231978123645367592418592814376814367952
17f 123456789456789123789231564231645897645978231978123645367814952592367418814592376
17g 123456789456789123789231564231645978645978312978123456367592841592814637814367295
17h 123456789456789123789231564231645978645978312978123456367814295592367841814592637
17i 123456789456789123789231564231897456645312978978564312367148295592673841814925637
17j 123456789456789123789231564231897645645312897978564231367148952592673418814925376
17k 123456789456789123789231564231978456645123978978645312367592841592814637814367295
17l 123456789456789123789231564231978645645123897978645231367592418592814376814367952
17m 123456789456789123897231645231897456564312897978564312349175268682943571715628934
17n 123456789456789123897231645231978456564123897978645312349517268682394571715862934
17o 123456789456789123897231645231978456564123978978645231349517862682394517715862394
17p 123456789456789123897231645268394517571862394934517862312978456645123978789645231

Class 18 : counts 252136 252136 252136 252136 278740 278740
18a 123456789456789231789123645231564897564897312897231456375618924618942573942375168
18b 123456789456789231789123645231564897564897312897231456375942168618375924942618573
18c 123456789456789231789123645231564978564897123897231564375942816618375492942618357
18d 123456789456789231789123645231645897564978312897312456375294168618537924942861573
18e 123456789456789231789123645231645897564978312897312456375861924618294573942537168
18f 123456789456789231789123645231978456564312897897645312375294168618537924942861573
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Wed Sep 06, 2006 7:50 pm

Good work Red Ed with the FE-grids. I think it seems somehow strange that one of them has three 17s and the other would have none, but that's probably just one more sudoku mystery.

I'd like to examine the 3-digit unavoidables in these grids too, they should probably contain the grid with least amount of 3-digit unavoidables and most fully entwined triples (remove all instances of three digits to get exactly 6 solutions). Counting the FE-triples shouldn't be hard, but counting all 3-digit unavoidables is at least a lot more complicated than counting 2-digit unavoidables.

Red Ed wrote:I believe SFB has been searched without success for a 16. I can also confirm that RV and FE 6a (the only FE grid to be the sole representative of its class) have no 16. I've not checked RW's grid.

I left my desktop scanning my FE-grid for 16s this morning, should be finished when I get back home next week.
[Edit: finished - suprise, suprise: no 16]

I wrote:My guess is that the upper limit for a grid that can give an 18 is somewhere around 67-68 and the upper limit for a 19 is 70 or 71.

Immediately after writing that I started doubting my words. I picked out a 72 with lowish MCN (13):
Code: Select all
694821357731564982258379416372495168815736249946182573583217694467953821129648735
004020300700500000008009000000000008010036200000000070000007094060000000120000000

and as you can see it has a 19. Next a 73 with higher MCN (15):
Code: Select all
234576198596281734178349562412765983965832417783194625347918256821657349659423871
200006000000001034000040000010700900005000000003000600000900050820000000600020001

and found a 19 there almost immediately. However, letting checker finish the search on these grids, it confirmed that both have only one 19. So after all it's not very easy to solve grids with 70+ 2-digit unavoidables with 19 clues, but it is possible.

And another grid to join the "No 19s Club" (71 2-digit unav, MCN 15):
Code: Select all
386214975549783621721569348865127439437695812912348567198432756274956183653871294


I really like the new checker, all full searches done in less than 16 hours each!:D

Almost forgot, I also got some better stats on 2-digit unavoidables. Here you can see the known 17s against the same amount of random grids:
Code: Select all
random 36628:    known 17:

36:              3
37:              1
38:              3
39:              6
40:              17
41: 1            58
42:              128
43: 7            295
44: 22           556
45: 40           871
46: 87           1275
47: 196          1800
48: 389          2560
49: 619          3307
50: 1205         3885
51: 1785         3997
52: 2715         4364
53: 3560         4227
54: 4337         3366
55: 4648         2512
56: 4686         1652
57: 4005         985
58: 3251         454
59: 2307         214
60: 1322         66
61: 768          23
62: 398          2
63: 162          1
64: 70           
65: 36           
66: 8             
67: 2             
68: 1             
69:               
70: 1

I think there's a quite clear difference to see in the table. Still haven't removed the duplicate grids, forgot all about it, but it helped me find this interesting grid:
Code: Select all
123457689456198327789326541294513876365782914817964235532641798648279153971835462

The only grid around with more than 60 2-digit unavoidbles (61) and more than one 17 (2).

RW
Last edited by RW on Tue Sep 12, 2006 3:33 pm, edited 1 time in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby Moschopulus » Wed Sep 06, 2006 10:00 pm

RW wrote:
Code: Select all
35 2-permutable pairs:
123456789456789132789213645264835917537194826891627453378561294615942378942378561




You were wondering if this had any 17s.

We searched for a 17 using the new checker, split into 4 jobs using -firstclues. Each job took a few days.

The result: no 17 in this grid.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Eioru » Thu Sep 07, 2006 3:32 am

Does this pattern have any puzzle?

Code: Select all
..*...*..
.*...*...
*...*...*
...*...*.
..*...*..
.*...*...
*...*...*
...*...*.
..*...*..


difficult to find one using program I have
Eioru
 
Posts: 182
Joined: 16 August 2006

Postby Red Ed » Thu Sep 07, 2006 6:18 am

when presenting the RV grid, I wrote:
  • Define a generalised diagonal to be three boxes no two of which are in the same band or stack (3! = 6 ways of achieving this). The number of grid completions from any generalised diagonal is always <130000. This beats SFB comfortably.
  • The generalised diagonals can be written D1~D2, D3~D4, D5, D6, where Di~Dj indicates isomorphism. SFB also has this unusual property.
The stuff about the generalised diagonals makes me wonder if perhaps we can do even better, perhaps with three isomorph-pairs (all with low completion count)
I did an exhaustive search for grids that have all six generalised diagonals isomorphic (like the MC and Pt grids). The ones with the highest completion count from any given generalised diagonal were the MC grid and its two quasi-equivalent friends, as expected. The one with the lowest completion count, a mere 113314 solutions, was this:
Code: Select all
123|456|789
456|789|123
897|231|564
---+---+---
248|573|691
369|814|257
571|692|348
---+---+---
682|147|935
734|925|816
915|368|472
You might hope that, with such a low completion count from each generalised diagonal, this grid should be good for low-clue puzzles, but with MCN 9 and 23 unavoidables of size 4 or 6 that does not appear to be the case!

Probably not a result worth remembering, but it was a fun exercise.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General