The New Sudoku Players' Forum

[evert]

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.

[dukuso]

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.

[evert]

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.

[dukuso]

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

[gfroyle]

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

[evert]

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?

[Wolfgang]

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)

[Lardarse]

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

[evert]

Forgive me my probably concise formulation.
By 8-proof I meant the prove that we need at least 9.

[Lardarse]

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]

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.

[evert]

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

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.

[Wolfgang]

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.