Minimum number of clues ---> proves for low numbers of cl

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

Minimum number of clues ---> proves for low numbers of cl

Postby evert » Mon Aug 29, 2005 8:10 am

Has anyone so far been able to prove for a certain number of clues
that a unique-solution sudoku with that number of clues is impossible?
The "Minimum number of clues" topic has already pointed out that a 7 clues sudoku
does not exist. This topic has become very large so I prefer to put
this approximation into a new topic.

Maybe I overlooked something in there?

An 8- or 9-number proof looks like a nice challenge.
evert
 
Posts: 186
Joined: 26 August 2005

Re: Minimum number of clues ---> proves for low numbers o

Postby dukuso » Mon Aug 29, 2005 8:35 am

evert wrote:Has anyone so far been able to prove for a certain number of clues
that a unique-solution sudoku with that number of clues is impossible?
The "Minimum number of clues" topic has already pointed out that a 7 clues sudoku
does not exist. This topic has become very large so I prefer to put
this approximation into a new topic.

Maybe I overlooked something in there?

An 8- or 9-number proof looks like a nice challenge.




it should be possible to prove that if one band only has 2 clues,
then the other 2 together must have 7 at least.
Bands with 2 clues are limited to "gangster" 42.
There can't be so many different cases.
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Minimum number of clues ---> proves for low numbers o

Postby evert » Mon Aug 29, 2005 3:30 pm

dukuso wrote:Bands with 2 clues are limited to "gangster" 42.

Can you explain this or do you have a link to an explanation?
I spent quite some time looking for it.
evert
 
Posts: 186
Joined: 26 August 2005

Re: Minimum number of clues ---> proves for low numbers o

Postby dukuso » Mon Aug 29, 2005 3:39 pm

evert wrote:
dukuso wrote:Bands with 2 clues are limited to "gangster" 42.

Can you explain this or do you have a link to an explanation?
I spent quite some time looking for it.



we had this in the "minimum number of clues" -thread,
which is unfortunately hard to search meanwhile.
I think it was page 9

I found it :
http://forum.enjoysudoku.com/viewtopic.php?t=605&postdays=0&postorder=asc&start=90
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Minimum number of clues ---> proves for low numbers o

Postby gfroyle » Thu Sep 01, 2005 8:16 am

evert wrote:An 8- or 9-number proof looks like a nice challenge.


This should not be too difficult to do I think...

The basic idea would be to first list all valid patterns of 9 cells up to equivalence. Although there are a huge number of choices for 9-out-of-81 cells, I think the requirement that no "chute" has 2 empty rows or columns will reduce this dramatically. Then take only one representative for each equivalence class, and use that as the underlying pattern.

Then partition those 9 cells in all possible ways into 8 or 9 parts - this is trivial in that either all 9 numbers appear, one per cell, or only 8 numbers appear, in which case there are 36 choices for two cells sharing a number, and the remaining 7 cells collect one number each.

Then it will be trivial to show that each of these configurations has either zero or more than one solution.

The only "unknown" here is that I have not tried to estimate how many valid patterns there are, but I can't imagine it is too big...

(Now I wait for Guenter to prove me wrong by showing it is too large...)

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Re: Minimum number of clues ---> proves for low numbers o

Postby evert » Thu Sep 01, 2005 7:40 pm

gfroyle wrote:the requirement that no "chute" has 2 empty rows or columns will reduce this dramatically.

?

Do you mean by this that no horizontal block can have two empty rows
or no vertical block can have two empty columns?

I started like this whith the 8-prove:

Applying the operations mentioned here:
http://www.csse.uwa.edu.au/~gordon/sudokumin.php

we can assume that
1 is in the upper left corner
2 is in the 2nd column
3 is in the 4th column
4 is in the 5th column
5 is in the 7th column
6 is in the 8th column
7 is in one of the 75 remaining cells
8 is in one of the 74 remaining cells

This gives us 9^5*75*74 grids to check.

Is there any further reduction of possibilities?
Last edited by evert on Fri Sep 02, 2005 4:37 am, edited 1 time in total.
evert
 
Posts: 186
Joined: 26 August 2005

Re: Minimum number of clues ---> proves for low numbers o

Postby Wolfgang » Fri Sep 02, 2005 7:19 am

evert wrote:I started like this whith the 8-prove:

Isnt it trivial that you need 8 clues? Otherwise you will have at least 2 solutions (you can always exchange the missing numbers)
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby Lardarse » Fri Sep 02, 2005 8:40 am

I think that's the proof!

I don't mean to offend you when I say this, but I often find that very difficult puzzles are shown to be very easy when you apply a "child's logic" to it...

LA
Lardarse
 
Posts: 106
Joined: 01 July 2005

Postby evert » Fri Sep 02, 2005 8:41 am

Forgive me my probably concise formulation.
By 8-proof I meant the prove that we need at least 9.
evert
 
Posts: 186
Joined: 26 August 2005

Postby Lardarse » Fri Sep 02, 2005 8:58 am

I think it's trivial hat you need at least 10 clues, because with just 9 clues, you are either evenly spaced throughout the grid, which doesn't give you enough information, or you have to become unbalanced enough that you have somewhere logical to start, which leads to you never being able to get enough information about the opposite areas...

LA
Lardarse
 
Posts: 106
Joined: 01 July 2005

Postby Moschopulus » Sat Sep 03, 2005 1:26 pm

Lardarse wrote:I think it's trivial hat you need at least 10 clues, because with just 9 clues, you are either evenly spaced throughout the grid, which doesn't give you enough information, or you have to become unbalanced enough that you have somewhere logical to start, which leads to you never being able to get enough information about the opposite areas...

LA

That's not a proof. This thread is about proofs.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby evert » Mon Sep 05, 2005 5:48 pm

In next grid
Code: Select all
1; ; ; ; ; ; ; ; ;
 ; ; ; ; ; ; ;3; ;
 ; ; ; ;5; ; ; ; ;
 ; ; ; ; ; ; ; ; ;
 ; ;4; ; ; ; ; ; ;
 ; ; ; ; ; ;7; ; ;
 ; ; ; ; ;6; ; ; ;
 ;2; ; ; ; ; ; ; ;
 ; ; ; ; ; ; ; ;8;

the options for 9s are located in a symmetrical way.

So it's no coincidence that both next grids:
Code: Select all
1;9;3;4;6;7;8;2;5;
5;4;8;2;1;9;6;3;7;
6;7;2;8;5;3;1;9;4;
2;1;7;9;3;5;4;8;6;
8;6;4;7;2;1;3;5;9;
3;5;9;6;8;4;7;1;2;
9;8;1;5;7;6;2;4;3;
4;2;6;3;9;8;5;7;1;
7;3;5;1;4;2;9;6;8;

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

are solutions.
(I exchanged 2/3, 4/5, 6/7 and transposed in order to get the
2nd solution out of the 1st one.)

So if we can force this kind of symmetry with operations like
permutation etc in any 8 clues grid we're done.

Any thoughts about this direction?


:(or is this a symmetrical grid by definition? Then I could have known I need at least 18 clues from the other minimum topic
scrose wrote:From what I've read, so far 17 is the minimum for a non-symmetrical grid and 18 is the minimum for a symmetrical grid.
evert
 
Posts: 186
Joined: 26 August 2005

Postby Wolfgang » Tue Sep 06, 2005 11:07 am

evert wrote:So if we can force this kind of symmetry with operations like
permutation etc in any 8 clues grid we're done.

I suppose, it cannot be possible for all 8 clues that have at least 2 numbers in the same unit (box, row, column), because in the above grid this is not the case.
(Otherwise i have to think about new solving techniques:) )

But im quite sure it is possible for all 1-per-unit-8-clues. At least it was no problem to transform the above one to this nice one:
Code: Select all
1; ; ; ; ; ; ; ; ;
 ; ; ;3; ; ; ; ; ;
 ; ; ; ; ; ;6; ; ;
 ;2; ; ; ; ; ; ; ;
 ; ; ; ;5; ; ; ; ;
 ; ; ; ; ; ; ;8; ;
 ; ;4; ; ; ; ; ; ;
 ; ; ; ; ;7; ; ; ;
 ; ; ; ; ; ; ; ; ;

Then it would be proved, that a 1-per-unit-9-clue cannot be unique.
Wolfgang
 
Posts: 208
Joined: 22 June 2005


Return to General