Grid not containing a 16

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

Postby dukuso » Mon Sep 12, 2005 7:03 pm

I think, I can confirm Wolfgang's observation.

the average number of 3-unique pairs is

random grid obtained from completing a random of Gordon's 17-sudokus
3079 (50 samples) [varies from 1575 to 6110]

random grid obtained by including random clues into the empty grid
2379 (47 samples)

random canonical G-class member
2235(52 samples)

Gordon's grid with many 17s
5216

canonical grid:
0

Moschopulos' grid:
2654
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Tue Sep 13, 2005 12:53 am

dukuso wrote:random grid obtained from completing a random of Gordon's 17-sudokus
3079 (50 samples) [varies from 1575 to 6110]

random grid obtained by including random clues into the empty grid
2379 (47 samples)

random canonical G-class member
2235(52 samples)

Gordon's grid with many 17s
5216

canonical grid:
0

Moschopulos' grid:
2654


These numbers are opposite to the number of unavoidable sets (of a certain type). So perhaps canonical has more unavoidable sets than average, "strangely familiar" grid with many 17s has fewer, others are roughly the same, average. High variance in the first type though.

So if a 16 exists maybe it will be in a grid with few unavoidable sets.

On the other hand, in your earlier stats the "strangely familiar" grid (2) behaved just like a random grid (4). Mosch grid (5) behaved like (1).
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Here's a question

Postby gfroyle » Tue Sep 13, 2005 5:01 am

Here's a question...

This is the grid with 29 x 17s.. [Edit: as Dukuso pointed out, I switched them by mistake - this is the new grid]

Code: Select all
6 3 9  2 4 1  7 8 5 
2 8 4  7 6 5  1 9 3 
5 1 7  9 8 3  6 2 4 

1 2 3  8 5 7  9 4 6 
7 9 6  4 3 2  8 5 1 
4 5 8  6 1 9  2 3 7 

3 4 2  1 7 8  5 6 9 
9 6 1  5 2 4  3 7 8 
8 7 5  3 9 6  4 1 2


Here is a similar grid... in fact, it is the same except that I have swapped around the elements of an unavoidable set of size 6 in rows 8 and 9..


[Edit: and this is the original grid with 29 17s in it]

Code: Select all
6 3 9  2 4 1  7 8 5 
2 8 4  7 6 5  1 9 3 
5 1 7  9 8 3  6 2 4 

1 2 3  8 5 7  9 4 6 
7 9 6  4 3 2  8 5 1 
4 5 8  6 1 9  2 3 7 

3 4 2  1 7 8  5 6 9 
8 6 1  5 9 4  3 7 2 
9 7 5  3 2 6  4 1 8 


Does this have a lot of 17s as well?

Well, I don't know. I haven't been able to find any 17s in this second grid (yet)...

But to be honest, I have not been able to find any 17s in the first grid starting from the complete grid, and trying to work downwards..

How do these grids compare when the statistics on rookeries etc are computed? I don't have time to do these right now, so if someone with the code already written would give it a go, I would be grateful..

Cheers

Gordon
Last edited by gfroyle on Tue Sep 13, 2005 4:17 am, edited 1 time in total.
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby dukuso » Tue Sep 13, 2005 6:45 am

your first grid is the new one, it has 5421 unique pairs in 3-rookeries.
your 2nd grid is "strangely familiar" with 5216 unique pairs in 3-rookeries.

Pretty many, although I had some with >6000 in the sample of 50.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby gfroyle » Tue Sep 13, 2005 8:19 am

dukuso wrote:your first grid is the new one,.


Whoops.. sorry about that - you are correct.

I wonder what the results of the million tries with 17,18,19,20,21,22,23,24 randomly chosen clues would be for these two grids - would it be different? I will try it later if I have time, but very rushed at the moment, and if you feel like doing it, I would be interested in the outcome..

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby dukuso » Tue Sep 13, 2005 8:57 am

I usually just generate random locally minimal sudokus over that grid
and then count the clues. One million takes an hour,
often I just do 1e5 and then multiply by 10.

Result is almost the same as with gr16 (I called them gr16 and gr16b).
From these counts I won't be able to distinguish the two.

Well, slightly more 20s for the second, maybe I'll do the 1e6 run
later to see whether it's significant.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby dukuso » Tue Sep 13, 2005 12:36 pm

ratio of counts of random locally minimal sudokus starting from the full
grid and deleting clues at random in gr16b / gr16 is:

24:1.0042
23:1.0154
22:1.0209
21:1.0590
20:1.3187 (240/182)

so this might continue 2,5,20 or such when there would be 20times
more 17s in the new grid !

edit: this is highly speculative, of course
Last edited by dukuso on Wed Sep 14, 2005 11:10 am, edited 1 time in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby gfroyle » Tue Sep 13, 2005 1:42 pm

dukuso wrote:so this might continue 2,5,20 or such when there would be 20times
more 17s in the new grid !


I did some slightly different computations - just picking k clues at random, and checking whether it formed a uniquely completable subgrid..

I got the following results from a million tries for each grid (old = original one with 29 x 17s, new = switched one)

Code: Select all
k     old   new

23      1      2
24     15     20
25    141    187
26    782    970
27   2955   3501
28   8617  10003


Now, you would have to say that the new grid is actually MORE promising for uniquely completable subgrids than the original...

So why can't I find ANY 17s (or indeed 18s yet) in the new grid?

Obviously I need better techniques for finding puzzles contained in a given grid, rather than just blindly finding 17s and then seeing what the completion is.

[Added: for comparison, the Moschopulus grid for k=25 yields just 2 uniquely completable puzzles from the million tries]
gfroyle
 
Posts: 214
Joined: 21 June 2005

Re: Here's a question

Postby Moschopulus » Tue Sep 13, 2005 11:06 pm

gfroyle wrote:Here's a question...

This is the grid with 29 x 17s..

Here is a similar grid... in fact, it is the same except that I have swapped around the elements of an unavoidable set of size 6 in rows 8 and 9..

Does this have a lot of 17s as well?


Hmm. Intuitively I would expect so, but I can't think of a proof. Focusing on that unavoidable set, I looked at the first of the 29 puzzles with 17 clues from the "strangely familiar" grid. It has 2 clues from this unavoidable set. No other choice of 2 clues gives a 17. In the new grid, no choices of 2 clues from the unavoidable set give a 17. So there's no simple transformation, at any rate.

dukuso wrote:24:1.0042
23:1.0154
22:1.0209
21:1.0590
20:1.3187 (240/182)


I would be wary of these ratios since the numbers 240, 182, are too small.
Maybe the ratio for 24 is better since the numbers are bigger (I presume).
In the limit maybe all ratios are 1.

gfroyle wrote:Now, you would have to say that the new grid is actually MORE promising for uniquely completable subgrids than the original...

These numbers seem small for a million tries. dukuso said elsewhere that you have a 60% chance of a puzzle with a unique solution for k=25.
About 40% in general.
Only 2 for the Mosch grid! Interesting. These grids must be highly non-random.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Re: Here's a question

Postby gfroyle » Wed Sep 14, 2005 9:57 am

Moschopulus wrote:These numbers seem small for a million tries. dukuso said elsewhere that you have a 60% chance of a puzzle with a unique solution for k=25.
About 40% in general.
Only 2 for the Mosch grid! Interesting. These grids must be highly non-random.


I don't think he was talking about the same thing ... there is no way that ANY grid has 60% of the 25-clue subgrids being Sudokus....

Just to be sure, here is what I am talking about

- fix a grid
- select a 25-clue subgrid at random
- check if it is a sudoku

This is not the same as Guenter's procedure...

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Re: Here's a question

Postby dukuso » Wed Sep 14, 2005 3:04 pm

gfroyle wrote:[
- fix a grid
- select a 25-clue subgrid at random
- check if it is a sudoku

This is not the same as Guenter's procedure...

Gordon


it is the same. Just that I didn't say 60%.
It was 60 _grids_ (out of a million) or 0.006%.
Sorry if this was unclear.
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Wed Sep 14, 2005 10:34 pm

Thanks for clarification.
But you did say a random subset (for arbitrary k) has a 40% chance of having a unique solution?
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby dukuso » Thu Sep 15, 2005 6:02 am

Moschopulus wrote:Thanks for clarification.
But you did say a random subset (for arbitrary k) has a 40% chance of having a unique solution?


when k isn't fixed.
when you pick one of the 2^81 subsets at random
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby gfroyle » Thu Sep 15, 2005 7:36 am

Here are some interesting 17s...

http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=7

They look similar, but are different .. maybe they even PLAY essentially the same..

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby coloin » Thu Sep 15, 2005 7:14 pm

These unavoidable sets are very easy to overlook.

EDIT the program nppcsu.exe certainly pinpoints them - and highlights longer chains.

Groyles strangly familiar grid had
9 triples
2 pairs

They are all appear to be inter connected - why did I think that being interconnected stopped them being unavoidable ?......I had presumed that any series of interconnected unavoidable sets would only need 1 clue.

Gfroyles new grid has
8 triples
1 pair

So Gfroyle is trying to make two stacks with repeating minirows but without the unavoidable pairs.....
Is it possible to get a grid with the minirows repeating but with a low unavoidable pair rate.

Has combinations of the 416 set been looked at ?

I have a grid which I thought was quite good - it has 56 clues paired up -but I now think is quite bad ! It has many 4 element pairs....and only 1 six element pair....
[but the program reads out many other long chains which I cant quite see]

+---+---+---+
|832|591|764|
|496|387|251|
|571|264|983|
+---+---+---+
|185|746|392|
|267|953|418|
|943|812|675|
+---+---+---+
|714|638|529|
|329|175|846|
|658|429|137| solved in 25 with diff.
+---+---+---+


What prediction would we getfor this one ?
Rookery rating ?
Interestingly this grid had lower overall 9x"B1245" solutions than Gfroyles strangely familiar grid.

Regards
coloin
 
Posts: 1662
Joined: 05 May 2005

PreviousNext

Return to General