## 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

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

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

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

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.

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

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

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

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

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

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

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

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

Moschopulus

Posts: 256
Joined: 16 July 2005

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.

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

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