Structures of the solution grid

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

Postby Red Ed » Fri Aug 25, 2006 7:10 pm

coloin wrote:The SFB also had consistently low box interaction values - [eg filling of B4 for a given B1/B5]. see Presumablly RV has this property.
RV has each box interaction value equal to 400, exactly the same as SFB.

I don't think box interaction values are important, though: if you calculate the grid statistic BoxInt = sum of all 18 box interaction values, then you find 17-capable grids generally have slightly higher BoxInt stats than random grids, but only with an unimpressive good-ranking score of c. 56%. But maybe I'm just looking at it the wrong way.

Update: overnight, I found all 127 essentially-different ways of building a fully-entwined grid; the whole snake pit, you might say. I will report results from these soon but first I want to do a (completely pointless, I know) 16-clue search on one of the MCN 7 grids the popped out ...
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Sat Aug 26, 2006 10:30 am

Well done you charmer !

I dont think the box interactions are very user-friendly either. If you have a 384 it increases the higher ones - and it all gets messy ! They are a structure of the grid though. Did they help in getting the 127 snakes ?

The double 392 had the lowest B159 grid completion though.

I cant convince myself entirely that there aren't 36 - not 18 !

I think you need to find a grid with hundreds of 17s before you would have a chance to get a 16 ! And that is a brick wall we cannot climb.

C
coloin
 
Posts: 1711
Joined: 05 May 2005

Postby Red Ed » Sat Aug 26, 2006 9:09 pm

coloin wrote:I cant convince myself entirely that there aren't 36 - not 18 !
9c2 = 36 pairs of boxes, half of which share the same stack or band, leaving 18 offset pairs.
I think you need to find a grid with hundreds of 17s before you would have a chance to get a 16 !
I don't know about hundreds: 81 - 16 = 65 would do. But, like most people, I believe that no such grid exists.

You also asked if box interactions helped in finding the "snakes". No, they didn't. But some other ideas from the search can be adapted to help answer the following long-standing conjecture ...
On Jan 3rd in the Pseudo-puzzles thread, Moschopulus wrote:Conjecture: every grid has either a size 4 unavoidable set or a size 6 unavoidable set. (Most grids have both sizes)
... which I can now confirm is true. (More's the pity.)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Sun Aug 27, 2006 7:10 pm

Nice to see that this issue is investigated further! Both me and my computer are very busy with "real" work right now, so I haven't had time to do any more searches.

Red Ed wrote:
A little while ago, RW wrote:The SFB grid, with better properties, has three 17s in it. I have found no other grid with 36 2-perms yet.


I actually did find one shortly after I wrote that:

Code: Select all
978316245345827961216459387624735198781942536539681472163274859457198623892563714


but I wanted to scan it for 17s before posting. If Red Ed now have a collection of all 127, then this should be among them. I think I now have searched about 70 000 000 random grids, and found only one, so 127 sounds like a reasonable amount.

Now I'm very curious about the maximum amount of 2-digit unavoidables there can be in a grid. Random search has given one 74 and a few 73s. I'll modify my program to also print out more accurate statistics on these, right now it only gives one of the grids with the highest amount in every set and I usually run them in sets of a few millions so I don't know how many have > 70. 72 gives an average of two per pair, seems rare to get above this. I have several set of 5 million grids that don't even have a 72. All sets seem to have at least one 71 though.

I'll be back more actively on the thread in a few weeks.

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

Postby Red Ed » Sun Aug 27, 2006 9:32 pm

RW wrote:Now I'm very curious about the maximum amount of 2-digit unavoidables there can be in a grid.
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
Rather nicely, the generalised diagonals are all isomorphic. After much thinking, checker reports MCN 15.

I'm undecided on the wisdom of doing a full search over all 2-digit unavoidable configurations; give me some time to ponder that.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Mon Aug 28, 2006 6:46 am

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):


That grid is just amazing. My search in random grids haven't found any with less than 7 fully entwined pairs, now you present the 0! 30 4-perms and 6 8-perms gives 78 2-digit unavoidables. Interesting feature in this grid is that if you remove all instances of any digit n, then there has to be at least two givens of all the other digits to hit only the 2-digit unavoidables with n as one of the digit. Remove all digits n=1, 3, 4, 6, 7 or 9, and there has to be a least 18 clues to hit the 2-digit unavoidables including n (all of those are part of 2 8-perms). Maybe this would be a good candidate for a minimum 36...

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

Postby RW » Mon Aug 28, 2006 5:31 pm

Did you have to post the interesting grid right now, I really don't have time for this... but I couldn't resist to do some tests. I started checker128 on the Pt-grid looking for 18s. At 535/4096 my computer crashed and I had to reboot (apparently my audio applications don't like extra programs running in the background). At that time checker said "0 puzzles generated, no uniques found". So there wasn't even a way to place 18 clues that would hit the 128+15 unavoidables used. Optimistically I started a new check using a given clue from the other end and when my computer crashed again at 135/1024 it had only generated 2 puzzles. Seems there's very few ways to hit these unavoidables with 18 clues. The normal checker (using 192 sets) might not generate a single puzzle... I haven't seen anything like this before when checking for 18s. The whole searh would take about 20h but I can't afford that right now.

I can almost bet my head that there isn't a 19 in the grid, but what about the 20s...

Red Ed wrote:A systematic search for grids with no fully-entwined pairs yields just one answer, up to isomorphism


Does "systematic" mean that there is only one possible totally unentwined grid among all grids?

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

Postby Moschopulus » Mon Aug 28, 2006 7:44 pm

RW wrote:Optimistically I started a new check using a given clue from the other end and when my computer crashed again at 135/1024 it had only generated 2 puzzles. Seems there's very few ways to hit these unavoidables with 18 clues. The normal checker (using 192 sets) might not generate a single puzzle...


checker64 would probably be faster. It would generate more puzzles and spend more time using the solver. Finding a good balance is the way to optimise checker.

Ok.......I'll run it for a while!
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Red Ed » Mon Aug 28, 2006 7:49 pm

RW wrote:Does "systematic" mean that there is only one possible totally unentwined grid among all grids?
Up to isomorphism, yes. Pretty special, huh?:D

(My earlier comment, wondering whether or not I should do a full search over all configurations of 2-digit unavoidables, was only meant to address the question: "can we do better than 78?". The thought was that by allowing some pairs to be entwined, there might be more freedom to break up other pairs into 3+ unavoidables. On reflection, however, that search looks to be fiddly and quite possibly rather slow, so I don't think I'll bother.)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Moschopulus » Tue Aug 29, 2006 1:31 pm

RW wrote:I started checker128 on the Pt-grid looking for 18s.


The Pt grid has no 18. I ran checker64 overnight.

I'll start off searching for a 19, but I'll use the -firstclues option.

The unavoidable set from which you can choose a clue to fix is
{11,14,21,24}
so I will choose 11.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Tue Aug 29, 2006 6:54 pm

Wow, the limits of our grid search has expanded maximally in both directions.

The 127 series of unentwined grids - apart from the SFB [3-17s] none of these grids feature in Gfroyle's collection. Possibly a new 17 or two will emerge.

As far as the Pt grid goes - it has all the features [and more] which make it unlikely that there is a 19 in the grid.
High MCN, high number of unavoidabes of size 4 or 6 [more than the RW,Canonvant and 74-2digit grids] No 21s even were generated over 1000000 puzzles from the pt grid.

Provisionally I will put it in the list of grids. Note the Canon grid [most canonical] has recently been exposed as not having a 19 - and probably it has only one isomorphic 20-clue puzzle. [648 in total]


Code: Select all
Canon - 123456789456789123789123456231564897564897231897231564312645978645978312978312645
PT    - 123456789457189326689327154231645897745891632896732541318264975574918263962573418


Code: Select all
          Bands                        Number of 20s    Max clues   MCN   Av.puzz.size
Canon     1   1   1  ,   1   1   1          648           35         12      25.70
PT        132 132 132  , 414 414 414        ?             ?          15      25.55


I hope Red Ed will tell us how he found the PT grid - it sure has save a heck of a lot of random generation and pain in getting the elusive grids with 6 down to 2 entwined pairs of clues. [I am presuming they are around]

Alls left to do is to wait for checker to confirm the lack of 19s and the presence of 20s.

C
coloin
 
Posts: 1711
Joined: 05 May 2005

Postby RW » Tue Aug 29, 2006 7:58 pm

coloin wrote:I hope Red Ed will tell us how he found the PT grid - it sure has save a heck of a lot of random generation and pain in getting the elusive grids with 6 down to 2 entwined pairs of clues. [I am presuming they are around]


Here's the 6 and the 4 (generated by simply swapping size 4 unavoidables in the Pt-grid):
Code: Select all
4: 127456389453189726689327154231645897745891632896732541318264975574918263962573418

6: 123456789457189326689327154231645897745892631896731542318264975574918263962573418

Maybe it's possible to fill in the gaps also this way, only tried three grids, the third also was a 6. I also think it should be possible for a grid to have exactly one fully entwined pair, can't see a reason why that would be impossible.

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

Postby Red Ed » Tue Aug 29, 2006 10:14 pm

coloin wrote:I hope Red Ed will tell us how he found the PT grid
It was just another template-based search (I've long been a fan of templates):
  • Fix the position of all the 1s (the "1s template"). This fixed template happens to include a cell in row 1, column 1.
  • Enumerate all 2s templates subject to the constraints that each (a) has a cell in row 1, column 2; (b) does not make a minimal unavoidable with the 1s template. Call this latter property P(1,2); for the Ds and Es templates we'll call it P(D,E).
  • Enumerate all 3s ... 9s templates similarly.
  • Now run a 8-deep loop (perhaps I could convince myself that 7-deep is enough, but never mind) which looks something like this:
    Code: Select all
    for each 2s template {
        filter the 4s ... 9s templates w.r.t. the 2s
        for each filtered 3s template s.t. P(2,3) {
            filter the 5s ... 9s templates w.r.t. the 3s
            for each filtered 4s template s.t. P(3,4) {
                filter the 6s ... 9s templates w.r.t. the 3s
                for each filtered 5s template s.t. P(4,5) {
                    filter the 7s ... 9s templates w.r.t. the 3s
                    for each filtered 6s template s.t. P(5,6) {
                        filter the 8s,9s templates w.r.t. the 3s
                        for each filtered 7s template s.t. P(6,7) {
                            filter the 9s templates w.r.t. the 3s
                            for each filtered 8s template s.t. P(7,8) {
                                for each filtered 9s template s.t. P(8,9) {
                                    reconstruct grid and save to file
    }   }   }   }   }   }   }   }
  • (Here, filtering the Es templates w.r.t. the Ds means temporarily discarding those for which P(D,E) is false.)I can't remember how many grids you get out of that, but when canonicalised they all turn out to be equivalent to the Pt grid.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Moschopulus » Wed Aug 30, 2006 8:35 am

RW wrote:I can almost bet my head that there isn't a 19 in the grid, but what about the 20s...


My computer completed the search overnight for a 19 in the PT grid fixing one clue, the 1 in position 11. No 19 was found.

It remains to do a search fixing the other three clues in 14, 21, 24. I'll start on 14.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Red Ed » Wed Aug 30, 2006 2:39 pm

I don't think it helps in the search that you're doing right now, but I should mention that the Pt grid is 6-way automorphic, with automorphism group generated by the two operators (r,s12) and (r,s23) where:
  • r = swap rows 1,3 and rows 4,6 and rows 7,9
  • s12 = swap stacks 1 and 2
  • s23 = swap stacks 2 and 3
So any combination of these two operators (6 possibilities in all, including the identity) will give you back the grid you started with, modulo relabelling. An immediate consequence is that the generalised diagonals are isomorphic as stated a few messages ago.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General