Minimum number of clues

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

Postby Moschopulus » Mon Aug 01, 2005 11:25 am

I meant to say:
can you choose the 18 clues to guarantee a unique solution?

There are lots of obvious choices that do not give a unique solution, e.g. leave two rows/columns/boxes empty.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby gfroyle » Mon Aug 01, 2005 1:05 pm

dukuso wrote:Or has anyone ever seen a sudoku with only 3 clues
in one 3*9-chunk ?


Here's a more interesting one...

Code: Select all
.6. 4.. 75.
21. 8.. ...
..9 ... ...

... .15 2..
4.. ... .6.
... .9. ...

8.. 3.. ...
... ... ..1
... ... ...


Just 17 clues, but still a chunk with only 3 clues required..

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby dukuso » Tue Aug 02, 2005 7:02 am

OK, I examined the minimum number of clues for a band.
And - surprise - there is even one of the 44 , where only
two clues are needed !

here is it:
Code: Select all
+-------+-------+-------+
| . . . | . . . | . . 8 |
| . . . | . . . | . . . |
| . . 9 | . . . | . . . |
+-------+-------+-------+
| 9 3 4 | 8 5 1 | 6 7 2 |
| 6 7 2 | 9 4 3 | 5 8 1 |
| 5 8 1 | 6 2 7 | 4 9 3 |
+-------+-------+-------+
| 4 1 3 | 5 9 2 | 8 6 7 |
| 7 2 5 | 3 6 8 | 9 1 4 |
| 8 9 6 | 7 1 4 | 2 3 5 |
+-------+-------+-------+



only one solution !
All horizontal bands are formed by gangster 42.
Vertical stacks : two by gangster 3 and one by gangster 5.

It'is my favourite candidate to make a 16-clue sudoku from.

As for Moschopulus' question to construct a 18-clue sudoku for
the gang1 canonical grid - I haven't tried. Maybe Gordon
can try it with his 17-clues program, or just walk through
his huge list of 18-clue-sudokus.




Below is the complete list of my examination.
I didn't examine all possibilities for the
clues, just a million random tries.


gang:1 , bands:1728 , clues:2 , unique solution:0 , out of 1000000 tries
gang:2 , bands:576 , clues:2 , unique solution:0 , out of 1000000 tries
gang:3 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:4 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:5 , bands:96 , clues:2 , unique solution:0 , out of 1000000 tries
gang:6 , bands:576 , clues:2 , unique solution:0 , out of 1000000 tries
gang:7 , bands:864 , clues:2 , unique solution:0 , out of 1000000 tries
gang:8 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:9 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:10 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:11 , bands:288 , clues:2 , unique solution:0 , out of 1000000 tries
gang:12 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:13 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:14 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:15 , bands:288 , clues:2 , unique solution:0 , out of 1000000 tries
gang:16 , bands:96 , clues:2 , unique solution:0 , out of 1000000 tries
gang:17 , bands:144 , clues:2 , unique solution:0 , out of 1000000 tries
gang:18 , bands:168 , clues:2 , unique solution:0 , out of 1000000 tries
gang:19 , bands:144 , clues:2 , unique solution:0 , out of 1000000 tries
gang:20 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:21 , bands:144 , clues:2 , unique solution:0 , out of 1000000 tries
gang:22 , bands:168 , clues:2 , unique solution:0 , out of 1000000 tries
gang:23 , bands:264 , clues:2 , unique solution:0 , out of 1000000 tries
gang:24 , bands:144 , clues:2 , unique solution:0 , out of 1000000 tries
gang:25 , bands:168 , clues:2 , unique solution:0 , out of 1000000 tries
gang:26 , bands:144 , clues:2 , unique solution:0 , out of 1000000 tries
gang:27 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:28 , bands:168 , clues:2 , unique solution:0 , out of 1000000 tries
gang:29 , bands:120 , clues:2 , unique solution:0 , out of 1000000 tries
gang:30 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:31 , bands:288 , clues:2 , unique solution:0 , out of 1000000 tries
gang:32 , bands:228 , clues:2 , unique solution:0 , out of 1000000 tries
gang:33 , bands:276 , clues:2 , unique solution:0 , out of 1000000 tries
gang:34 , bands:168 , clues:2 , unique solution:0 , out of 1000000 tries
gang:35 , bands:180 , clues:2 , unique solution:0 , out of 1000000 tries
gang:36 , bands:216 , clues:2 , unique solution:0 , out of 1000000 tries
gang:37 , bands:156 , clues:2 , unique solution:0 , out of 1000000 tries
gang:38 , bands:228 , clues:2 , unique solution:0 , out of 1000000 tries
gang:39 , bands:120 , clues:2 , unique solution:0 , out of 1000000 tries
gang:40 , bands:96 , clues:2 , unique solution:0 , out of 1000000 tries
gang:41 , bands:192 , clues:2 , unique solution:0 , out of 1000000 tries
gang:42 , bands:516 , clues:2 , unique solution:1664 , out of 1000000 tries
gang:43 , bands:168 , clues:2 , unique solution:0 , out of 1000000 tries
gang:44 , bands:120 , clues:2 , unique solution:0 , out of 1000000 tries
gang:1 , bands:1728 , clues:3 , unique solution:0 , out of 1000000 tries
gang:2 , bands:576 , clues:3 , unique solution:0 , out of 1000000 tries
gang:3 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:4 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:5 , bands:96 , clues:3 , unique solution:0 , out of 1000000 tries
gang:6 , bands:576 , clues:3 , unique solution:0 , out of 1000000 tries
gang:7 , bands:864 , clues:3 , unique solution:0 , out of 1000000 tries
gang:8 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:9 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:10 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:11 , bands:288 , clues:3 , unique solution:177 , out of 1000000 tries
gang:12 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:13 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:14 , bands:192 , clues:3 , unique solution:0 , out of 1000000 tries
gang:15 , bands:288 , clues:3 , unique solution:95 , out of 1000000 tries
gang:16 , bands:96 , clues:3 , unique solution:0 , out of 1000000 tries
gang:17 , bands:144 , clues:3 , unique solution:309 , out of 1000000 tries
gang:18 , bands:168 , clues:3 , unique solution:325 , out of 1000000 tries
gang:19 , bands:144 , clues:3 , unique solution:173 , out of 1000000 tries
gang:20 , bands:192 , clues:3 , unique solution:126 , out of 1000000 tries
gang:21 , bands:144 , clues:3 , unique solution:63 , out of 1000000 tries
gang:22 , bands:168 , clues:3 , unique solution:80 , out of 1000000 tries
gang:23 , bands:264 , clues:3 , unique solution:565 , out of 1000000 tries
gang:24 , bands:144 , clues:3 , unique solution:471 , out of 1000000 tries
gang:25 , bands:168 , clues:3 , unique solution:219 , out of 1000000 tries
gang:26 , bands:144 , clues:3 , unique solution:178 , out of 1000000 tries
gang:27 , bands:192 , clues:3 , unique solution:251 , out of 1000000 tries
gang:28 , bands:168 , clues:3 , unique solution:372 , out of 1000000 tries
gang:29 , bands:120 , clues:3 , unique solution:289 , out of 1000000 tries
gang:30 , bands:192 , clues:3 , unique solution:424 , out of 1000000 tries
gang:31 , bands:288 , clues:3 , unique solution:415 , out of 1000000 tries
gang:32 , bands:228 , clues:3 , unique solution:427 , out of 1000000 tries
gang:33 , bands:276 , clues:3 , unique solution:192 , out of 1000000 tries
gang:34 , bands:168 , clues:3 , unique solution:450 , out of 1000000 tries
gang:35 , bands:180 , clues:3 , unique solution:531 , out of 1000000 tries
gang:36 , bands:216 , clues:3 , unique solution:751 , out of 1000000 tries
gang:37 , bands:156 , clues:3 , unique solution:607 , out of 1000000 tries
gang:38 , bands:228 , clues:3 , unique solution:593 , out of 1000000 tries
gang:39 , bands:120 , clues:3 , unique solution:613 , out of 1000000 tries
gang:40 , bands:96 , clues:3 , unique solution:0 , out of 1000000 tries
gang:41 , bands:192 , clues:3 , unique solution:499 , out of 1000000 tries
gang:42 , bands:516 , clues:3 , unique solution:1228 , out of 1000000 tries
gang:43 , bands:168 , clues:3 , unique solution:629 , out of 1000000 tries
gang:44 , bands:120 , clues:3 , unique solution:991 , out of 1000000 tries
gang:1 , bands:1728 , clues:4 , unique solution:0 , out of 1000000 tries
gang:2 , bands:576 , clues:4 , unique solution:0 , out of 1000000 tries
gang:3 , bands:192 , clues:4 , unique solution:119 , out of 1000000 tries
gang:4 , bands:192 , clues:4 , unique solution:100 , out of 1000000 tries
gang:5 , bands:96 , clues:4 , unique solution:608 , out of 1000000 tries
gang:6 , bands:576 , clues:4 , unique solution:0 , out of 1000000 tries
gang:7 , bands:864 , clues:4 , unique solution:17 , out of 1000000 tries
gang:8 , bands:192 , clues:4 , unique solution:166 , out of 1000000 tries
gang:9 , bands:192 , clues:4 , unique solution:327 , out of 1000000 tries
gang:10 , bands:192 , clues:4 , unique solution:290 , out of 1000000 tries
gang:11 , bands:288 , clues:4 , unique solution:261 , out of 1000000 tries
gang:12 , bands:192 , clues:4 , unique solution:257 , out of 1000000 tries
gang:13 , bands:192 , clues:4 , unique solution:102 , out of 1000000 tries
gang:14 , bands:192 , clues:4 , unique solution:309 , out of 1000000 tries
gang:15 , bands:288 , clues:4 , unique solution:207 , out of 1000000 tries
gang:16 , bands:96 , clues:4 , unique solution:582 , out of 1000000 tries
gang:17 , bands:144 , clues:4 , unique solution:460 , out of 1000000 tries
gang:18 , bands:168 , clues:4 , unique solution:642 , out of 1000000 tries
gang:19 , bands:144 , clues:4 , unique solution:617 , out of 1000000 tries
gang:20 , bands:192 , clues:4 , unique solution:509 , out of 1000000 tries
gang:21 , bands:144 , clues:4 , unique solution:503 , out of 1000000 tries
gang:22 , bands:168 , clues:4 , unique solution:527 , out of 1000000 tries
gang:23 , bands:264 , clues:4 , unique solution:335 , out of 1000000 tries
gang:24 , bands:144 , clues:4 , unique solution:758 , out of 1000000 tries
gang:25 , bands:168 , clues:4 , unique solution:511 , out of 1000000 tries
gang:26 , bands:144 , clues:4 , unique solution:494 , out of 1000000 tries
gang:27 , bands:192 , clues:4 , unique solution:573 , out of 1000000 tries
gang:28 , bands:168 , clues:4 , unique solution:705 , out of 1000000 tries
gang:29 , bands:120 , clues:4 , unique solution:859 , out of 1000000 tries
gang:30 , bands:192 , clues:4 , unique solution:646 , out of 1000000 tries
gang:31 , bands:288 , clues:4 , unique solution:402 , out of 1000000 tries
gang:32 , bands:228 , clues:4 , unique solution:517 , out of 1000000 tries
gang:33 , bands:276 , clues:4 , unique solution:385 , out of 1000000 tries
gang:34 , bands:168 , clues:4 , unique solution:760 , out of 1000000 tries
gang:35 , bands:180 , clues:4 , unique solution:787 , out of 1000000 tries
gang:36 , bands:216 , clues:4 , unique solution:706 , out of 1000000 tries
gang:37 , bands:156 , clues:4 , unique solution:885 , out of 1000000 tries
gang:38 , bands:228 , clues:4 , unique solution:760 , out of 1000000 tries
gang:39 , bands:120 , clues:4 , unique solution:1245 , out of 1000000 tries
gang:40 , bands:96 , clues:4 , unique solution:634 , out of 1000000 tries
gang:41 , bands:192 , clues:4 , unique solution:694 , out of 1000000 tries
gang:42 , bands:516 , clues:4 , unique solution:287 , out of 1000000 tries
gang:43 , bands:168 , clues:4 , unique solution:964 , out of 1000000 tries
gang:44 , bands:120 , clues:4 , unique solution:1290 , out of 1000000 tries
gang:1 , bands:1728 , clues:5 , unique solution:0 , out of 1000000 tries
gang:2 , bands:576 , clues:5 , unique solution:25 , out of 1000000 tries
gang:3 , bands:192 , clues:5 , unique solution:110 , out of 1000000 tries
gang:4 , bands:192 , clues:5 , unique solution:107 , out of 1000000 tries
gang:5 , bands:96 , clues:5 , unique solution:246 , out of 1000000 tries
gang:6 , bands:576 , clues:5 , unique solution:36 , out of 1000000 tries
gang:7 , bands:864 , clues:5 , unique solution:24 , out of 1000000 tries
gang:8 , bands:192 , clues:5 , unique solution:140 , out of 1000000 tries
gang:9 , bands:192 , clues:5 , unique solution:168 , out of 1000000 tries
gang:10 , bands:192 , clues:5 , unique solution:179 , out of 1000000 tries
gang:11 , bands:288 , clues:5 , unique solution:109 , out of 1000000 tries
gang:12 , bands:192 , clues:5 , unique solution:154 , out of 1000000 tries
gang:13 , bands:192 , clues:5 , unique solution:125 , out of 1000000 tries
gang:14 , bands:192 , clues:5 , unique solution:165 , out of 1000000 tries
gang:15 , bands:288 , clues:5 , unique solution:108 , out of 1000000 tries
gang:16 , bands:96 , clues:5 , unique solution:217 , out of 1000000 tries
gang:17 , bands:144 , clues:5 , unique solution:209 , out of 1000000 tries
gang:18 , bands:168 , clues:5 , unique solution:230 , out of 1000000 tries
gang:19 , bands:144 , clues:5 , unique solution:275 , out of 1000000 tries
gang:20 , bands:192 , clues:5 , unique solution:214 , out of 1000000 tries
gang:21 , bands:144 , clues:5 , unique solution:256 , out of 1000000 tries
gang:22 , bands:168 , clues:5 , unique solution:235 , out of 1000000 tries
gang:23 , bands:264 , clues:5 , unique solution:140 , out of 1000000 tries
gang:24 , bands:144 , clues:5 , unique solution:258 , out of 1000000 tries
gang:25 , bands:168 , clues:5 , unique solution:219 , out of 1000000 tries
gang:26 , bands:144 , clues:5 , unique solution:218 , out of 1000000 tries
gang:27 , bands:192 , clues:5 , unique solution:199 , out of 1000000 tries
gang:28 , bands:168 , clues:5 , unique solution:248 , out of 1000000 tries
gang:29 , bands:120 , clues:5 , unique solution:321 , out of 1000000 tries
gang:30 , bands:192 , clues:5 , unique solution:233 , out of 1000000 tries
gang:31 , bands:288 , clues:5 , unique solution:168 , out of 1000000 tries
gang:32 , bands:228 , clues:5 , unique solution:205 , out of 1000000 tries
gang:33 , bands:276 , clues:5 , unique solution:183 , out of 1000000 tries
gang:34 , bands:168 , clues:5 , unique solution:289 , out of 1000000 tries
gang:35 , bands:180 , clues:5 , unique solution:258 , out of 1000000 tries
gang:36 , bands:216 , clues:5 , unique solution:216 , out of 1000000 tries
gang:37 , bands:156 , clues:5 , unique solution:294 , out of 1000000 tries
gang:38 , bands:228 , clues:5 , unique solution:239 , out of 1000000 tries
gang:39 , bands:120 , clues:5 , unique solution:419 , out of 1000000 tries
gang:40 , bands:96 , clues:5 , unique solution:247 , out of 1000000 tries
gang:41 , bands:192 , clues:5 , unique solution:256 , out of 1000000 tries
gang:42 , bands:516 , clues:5 , unique solution:75 , out of 1000000 tries
gang:43 , bands:168 , clues:5 , unique solution:341 , out of 1000000 tries
gang:44 , bands:120 , clues:5 , unique solution:333 , out of 1000000 tries
Last edited by dukuso on Tue Aug 02, 2005 5:29 am, edited 2 times in total.
dukuso
 
Posts: 479
Joined: 25 June 2005

No 42

Postby coloin » Tue Aug 02, 2005 8:34 am

Very very Impressive
A look at Gordons 17 interestingly has very few examples where there are no clues in a box - and when that happened there was no single clue boxes.

I will take a look at this grid !!!

Gangster 42 is "select" of the 44 I feel

Of course as you rightly qualify the grid as having other gangular components - I believe that there are 3 horizontal gang and three vertical gang "components" to every valid suduku - as indeed you do !.

It is the interaction between them which makes a grid valid and in your case gives us a grid which can be represented with only two clues in one of the horizontal bands.

Did it turn out by chance that the horizontal bands are all a representation of 42 ? [ Are you sure the lower band is a 42 ?]

On this note - in discussing Red Ed's Gang members - it hasnt been pointed out that each member is a palindrome - ie when rearranged it is in the same gang when looked at from right to left - this has to be I think.

On finding the 16 - It is the last clue to be added which does the "damage" in completing the grid - this makes logical addition/removal and analysis perhaps difficult to interpret. The 16 grid, even though unique, when "found" may not be the easiest grid to complete.

Good Luck
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Moschopulus » Tue Aug 02, 2005 12:06 pm

>As for Moschopulus' question to construct a 18-clue sudoku for
>the gang1 canonical grid - I haven't tried. Maybe Gordon
>can try it with his 17-clues program, or just walk through
>his huge list of 18-clue-sudokus.

You proved that at least 18 clues are needed for this gang1 canonical grid.
I conjecture that *more* than 18 are needed.

The conjecture is based on rather flimsy evidence, so may well be wrong.
What I have in mind is that any puzzle whose unique completion has a large symmetry group needs to have a relatively large number of clues. Puzzles with few clues will have completions whose symmetry group is small.

Now this is all just conjecture, I can't prove any of it. I would be interested if someone could compute the symmetry groups of gfroyle's list of 17ers.

If this principle (large symmetry groups correspond to lots of clues) is correct, then one should stick to grids with small symmetry groups when looking for a 16.

The words "small" and "large" are used in a relative sense, of course.
Apologies if this has been covered already, I am new to the group.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

How do you know when a 16 has only one solution ?

Postby coloin » Tue Aug 02, 2005 12:55 pm

How are you going about checking your 16 combinations for unique solutions ?

How difficult would it be to compile a "list" of all 6*10^21 grids ?

Maybe we only need to compile a "mini-list" to get an idea whether a combination of 16 numbers might be unique. How long would this need to be ?

We could take out 9! for box 1

That would be 72 numbers per grid - Say 10^10 grids to start. Is this doable ?

If you do get a fit then it is not unique. If it has a chance of being unique - our random 16 combination will not coincide with any other suduku amonst our mini-list. [Apart from the original].

Then subject the grids which get through to a solver program to impart the ultimate check.

How long would it take to analyse some of the 81! / 65! 16ers in our grid ? in this way !!

Im prepared for failure here.

Colin
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby dukuso » Tue Aug 02, 2005 1:05 pm

here is another curiosity which I just discovered :

our "canonical" grid :

123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
345678912

with all bands formed by gangster 1,
which requires 18 clues at least, is just ...
one of the 2-clue-band-grids with all
3 bands formed by gangster 42,
when rotated by 90' !

so, this :

1..456789
...789123
...123456
...567891
...891234
...234567
...678912
...912345
..2345678

is a valid sudoku with exactly one solution !
This means, that there must be 16=5+6+5 clues at least
in the right 6 columns.

This makes me a little suspicious about Moschopolus'
conjecture - and also about my optimism that a
42,42,42 - grid could be used to construct
a 16-clues sudoku, sigh.


Guenter.
dukuso
 
Posts: 479
Joined: 25 June 2005

42 42 42

Postby coloin » Tue Aug 02, 2005 3:28 pm

A bit of a coincidence - that your grid was pulled out after so much analysis - and it was essentially the same as Moschopulus' except rotated by 90 degrees.

It was a trifle symetrical - which implies that it would need more clues - I agree.

I dont know how to take the choice of a suitable grid furthur - it seems that it may be a chance occurance. May be a good mix is what is needed !

44^6 = 7256313856

[5472730538 is the number Red Ed calculated for "essentially different grids", this is fairly healthily similar but below the 44^6.]

Are these two numbers meaningfully depicting the same thing.

44^6 minus the ones where there was no solution = 5472730538 ?

[ As I understand it - the fact that a grid can or cannot be transposed into another has been felt fairly unimportant - maybe it IS significant if it cant be transposed]

What is the breakdown [gangsterwise] of Gfroyles 17s ? I wonder
coloin
 
Posts: 1637
Joined: 05 May 2005

Re: 42 42 42

Postby dukuso » Tue Aug 02, 2005 3:59 pm

coloin wrote:A bit of a coincidence - that your grid was pulled out - and it was essentially the same as Moschopulus' except rotated by 90 degrees.

It was a trifle symetrical - which implies that it would need more clues - I agree.

I dont know how to take the choice of a suitable grid furthur - it seems that it may be a chance occurance. May be a good mix is what is needed !

44^6 = 7256313856

** you can divide this by at least 3!^2*2=72 for transformations

[5472730538 is the number Red Ed calculated for "essentially different grids", this is fairly healthily similar but below the 44^6.]

Are these two numbers meaningfully depicting the same thing.

44^6 minus the ones where there was no solution = 5472730538 ?

**no

[ As I understand it - the fact that a grid can or cannot be transposed into another has been felt fairly unimportant - maybe it IS significant if it cant be transposed]

What is the breakdown [gangsterwise] of Gfroyles 17s ? I wonder


I posted a statistics earlier. Should be my first post in this thread
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby dukuso » Tue Aug 02, 2005 4:06 pm

Moschopulus wrote:I meant to say:
can you choose the 18 clues to guarantee a unique solution?

There are lots of obvious choices that do not give a unique solution, e.g. leave two rows/columns/boxes empty.



we have 9^9=4e8 choices to place the 18 clues.
I tried 1e6 of these randomly and found
1 with 3 solutions
1 with 5 solutions
1 with 10 solutions
1 with 12 solutions
1 with 13 solutions
1 with 15 solutions
the rest with >20 solutions

Now, I had assumed that there were still some symmetries which
could be reduced in these 4e8, but well, these 6 were all unique.
The whole calculation might take some days, if someone wants to
do it, I can send a program.

here is the one with 3 solutions:

Code: Select all

.......89
4........
...123...
.3......1
......2..
8....4.6.
..5......
.....234.
91.......
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby Moschopulus » Tue Aug 02, 2005 5:47 pm

dukuso wrote:we have 9^9=4e8 choices to place the 18 clues.
I tried 1e6 of these randomly and found
1 with 3 solutions
1 with 5 solutions
1 with 10 solutions
1 with 12 solutions
1 with 13 solutions
1 with 15 solutions
the rest with >20 solutions



Interesting. So my conjecture is still alive!


Also you said
>1..456789
>...789123
>...123456
>...567891
>...891234
>...234567
>...678912
>...912345
>..2345678
>
>is a valid sudoku with exactly one solution !
>This means, that there must be 16=5+6+5 clues at least
>in the right 6 columns.
>
>This makes me a little suspicious about Moschopolus'
>conjecture - and also about my optimism that a
>42,42,42 - grid could be used to construct
>a 16-clues sudoku, sigh.

This is also very interesting!
Sorry, could you explain why there have to be at least 16 clues in the right 6 columns? [edit - I get it now]

I would have thought it would make you believe more in the conjecture, not less. Or do you think you can make exactly 16 clues on the right and exactly 2 clues on the left?

Coloin said
>How are you going about checking your 16 combinations for unique solutions ?

I am not doing any checking. I was just wondering (conjecturing if I may) whether small numbers of clues correspond to small symmetry groups, and large numbers of clues to large symmetry groups. There are two ways to deal with this,
1) prove or disprove it theoretically,
2) do some computer experiments to see if the correlation holds up.

Since I can't do either, I was wondering if anyone has done 2). Or 1) for that matter!

Based on this conjecture, since dukuso's gangster 1 canonical grid has a large symmetry group, I conjecture it doesn't have any "small number of clues" puzzles in it. In particular I conjecture it doesn't have an 18 in it.

Maybe I'm way off base here....
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby coloin » Tue Aug 02, 2005 6:30 pm

No I dont think you are. I am as inept if not more so !
It would appear to have much more than 18 - [no proof however]

I cant recall anyone coming up with even an average figure for the "minimum number of clues" .

gfroyle wrote:I am absolutely certain that not every valid solution has a 17-hint "starter", though of course PROVING this might be more difficult....

Gordon

We also dont know what the largest "minimum "! is if that were at all relevant !

Guenter had just postulated that a certain grid was the only one out of 44 million or so that solved a certain way - and this turned out remarkably similar to the canonical grid in a prior post. [perhaps it is not that surprising - just coincidence]

I was asking G how he was checking his solutions ! - in particular how can you reliably check that a certain combination does/doesnt have a single solution - surely that takes a long time if it envolves multiple guess logic - [maybe he has a solver do do this reliably]

dukuso wrote:we have 9^9=4e8 choices to place the 18 clues.
[/code]


Why isnt this 81!/63! - [any 18 anywhere] or 9^9*9^8 [two clues to a box] ?

Regards
Last edited by coloin on Tue Aug 02, 2005 3:06 pm, edited 1 time in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby dukuso » Tue Aug 02, 2005 7:02 pm

just wanted to tell you, that my computer found the 18-clues
example now. I'll answer the other posts tomorrow.

Code: Select all

12.......
...78...3
..9......
234......
...891...
.........
..5...91.
.....2...
...34....
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby coloin » Tue Aug 02, 2005 7:11 pm

I cant imagine how you have done it ?
So every grid can be reduced to 18 - I doubt it
Maybe this grid is special after all !
Great work
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Moschopulus » Tue Aug 02, 2005 8:50 pm

gfroyle wrote:
Here's the process... start off by listing all of the easy "exchangeable" sets - in other words, sets of cells whose entries can be permuted to get a new grid, for which we must therefore select at least one cell in our clue set.


To go back to the exchangeable sets (could I suggest the name "unavoidable" sets):

There are sometimes unavoidable sets of size 4:
12.......
.........
.........
21.......
.........etc

Has anyone found a completed grid with no unavoidable sets of size 4?
If not, what is the fewest known?

edit: silly me. the canonical one with rows
x, x+3, x+6, x+1, x+4, x+7, x+2, x+5, x+8, where x is any top row and arithmetic done mod 9, has no unavoidable sets of size 4.

Seems like a good candidate grid for a 16 would have the following properties:
1. no unavoidable sets of size 4
2. 14 (well 16 really) unavoidable sets of size 6 whose union is all 81 cells

I say 14 sets because 13*6 = 78 so 13 won't be enough.
Choosing one clue from these 14 sets is then a possible sudoku with 14 clues. Okay, change 14 to 16 for the moment.

The canonical one doesn't have unavoidable sets of size 6. It has 9 disjoint unavoidable sets of size 9 which each require 2 clues.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

PreviousNext

Return to General