The New Sudoku Players' Forum

[Serg]

Hi, colleagues!
As far as I know (but maybe I am wrong) the only sort of valid puzzles, having less than 17 clues, for which non-existance was proven is 7-clue puzzles. It is well known that valid puzzle must contain at least 8 different digits, otherwise we would obtain additional solutions renaming absent digits. But can anyone prove non-existance of 8-clue valid puzzles? Non-minimal 8-clue puzzles are impossible, because deleting of clue lead us to 7-clue puzzle which surely don't exist. So, it is sufficient to prove non-existance of minimal 8-clue valid puzzles (all clue digits of such puzzles must be different).

I have general idea to start analysis from low-clue puzzles, moving step-by-step to 16-clue puzzles. Any ideas?

Serg

[Serg]

Hi, all!
It looks like there is no proof of non-existance of 8-clue minimal valid puzzles. Ok, I'd like to propose my own approach based on "puzzle composition rules".

First, I have to define new term "puzzle map".
Let's consider a puzzle and compute numbers of clues for every box of sudoku grid. We'll obtain 9 digits (minimal possible value is 0, maximal possible value is 9). If we'll arrange these digits in 3 x 3 matrix, in correspondence with boxes positions, we'll get puzzle map. For example, let's consider (invalid) 16-clue puzzle

Code: Select all

 . . . | . . . | 9 6 .
 6 9 . | . 1 . | 8 . .
 . . 2 | . . . | 1 . .
-------+-------+------
 4 . . | . . 9 | . 8 .
 . . 9 | . . . | . . .
 . . . | . . . | . 1 .
-------+-------+------
 . . . | . . . | . . .
 . 4 . | . . . | . . .
 . . . | . 4 . | . . 9

This puzzle has such puzzle map:

Code: Select all

3 1 4
2 1 2
1 1 1

Variable (unknown), but non-zero number of clues in a box can be denoted by letter. For example, puzzle map (or simply "map")

Code: Select all

X 0 0
X X X
X X X

denotes a class of puzzles having non-zero numbers of clues in the boxes B1, B4-B9 and having no clues in the boxes B2 and B3. This notation was not so new (see well-known thread Empty Boxes - I).

Let's classify all possible valid puzzles by number of empty boxes (taking in account their arrangements to get nonisomorphic cases). There are 7 nonisomorphic types of valid puzzles only:

Code: Select all

Type 1   Type 2   Type 3   Type 4   Type 5   Type 6   Type 7

X X X    X X 0    X 0 0    X X 0    X X 0    X 0 0    X 0 0
X X X    X X X    X X X    X X X    X 0 X    0 X X    0 X X
X X X    X X X    X X X    0 X X    0 X X    X X X    0 X X

(I've copied Ocean's list from thread Empty Boxes - I, adding obvious "Type 1" and rearranging empty boxes to get more convinient for further analysis configurations.)

Let's now consider 8-clue valid puzzles and account for each type all possible maps. Type 1 is impossible because 8-clue puzzle must contain at least 1 empty box. Type 3 is impossible too, because such patterns must contain at least 4 clues in the box B1 to have valid puzzles (see thread Investigation of one-band-free patterns). Type 6 is impossible for the same reason as type 3.

Code: Select all

Type 2

1 1 0
1 1 1
1 1 1

Type 4

1 1 0     1 1 0     1 1 0
1 1 1     1 1 1     1 2 1
0 1 2     0 2 1     0 1 1

Type 5

1 1 0     1 1 0
1 0 1     1 0 2
0 2 2     0 2 1

Type 7

4 0 0
0 1 1
0 1 1

Now we should prove impossibility of 8-clue valid puzzles having one of the possible maps posted above.

I hope I was not wrong in determining of all possible maps.

(Continuation follows.)

Serg

[Serg]

Hi!
Let me remind classification scheme of all possible valid puzzles which is used in the approach being described.

Code: Select all

Valid puzzles hierarchy
-----------------------

Types
  |
Maps
  |
Patterns
  |
Puzzles

I've used in the previous post knowlege about possible configurations of empty boxes in valid puzzles and known restrictions on number of clues in the box B1 for class of patterns having empty boxes B2, B3 and entirely filled boxes B4-B9. This knowlege can be expressed in the "maps" term. I call these expressions "puzzle composition rules".

Code: Select all

Valid puzzles composition rules
-------------------------------

Rule 1.   Map of any valid puzzle must be isomorphic to one of these maps:

X X X    X X 0    X 0 0    X X 0    X X 0    X 0 0    X 0 0
X X X    X X X    X X X    X X X    X 0 X    0 X X    0 X X
X X X    X X X    X X X    0 X X    0 X X    X X X    0 X X

Rule 2.   Map posted below has no valid puzzles when Q < 4

Q 0 0
9 9 9
9 9 9

These composition rules can greatly limit search space during exhaustive search for valid puzzles. Please, note that these rules are universal, they are not specific to 8-clue puzzles. This is advantage of the approach described. Composition rules found during exhaustive search for low-clue puzzles can be used to limit search space for high-clue puzzles.

One can observed that almost all possible maps for 8-clue puzzles (posted in my previous post) are subsets of the map

Code: Select all

1 1 0
1 9 9
0 9 9

This map is good candidate for composition rule number 3. (I need some time for analysis of this map.)

Serg

[Afmob]

I think it has already been proven that there is no (valid) 8 clues 3x3 Sudoku. As far as I know even the case with 11 clues has been dealt with.

The easiest way to solve such a problem is to generate all possible patterns under consideration of some type of normal form (for instance, row-minlex) and then afterwards test every possible numbers placement with regards to pattern automorphisms and a fixed order of the numbers (e.g. ascending order).

In this 8 clues case you get 1131 patterns (excluding patterns with more than one free row/column per band) with each having only one possible number placement (12345678). Of course, not one is valid.

9 clues yields 18,663 patterns with a total of non-unique 438,735 puzzles.
10 clues yields 223,756 patterns with a total of non-unique 78,971,397 puzzles. This computation took about 47 minutes (2,2 GHz on one core).

[Serg]

Hi, Afmob!
Thank you for interesting information. Could you describe in more details cited method of exhaustive search for n-clue valid puzzles (for example, for 8-clue puzzles)?

Serg

[Afmob]

First, I go through all patterns which are in Row-MinLex form, for example

Code: Select all

*-----------*
|...|...|..X|
|...|.XX|...|
|..X|..X|...|
|---+---+---|
|...|...|.X.|
|.X.|.X.|X..|
|.X.|X..|...|
|---+---+---|
|...|X..|...|
|X..|...|.X.|
|X..|...|X..|
*-----------*


and which have not more than one row/column per band without any given number.

If a pattern is in this standard form, I compute every transformation which does not change the pattern. These are called (pattern) automorphisms. Afterwards I test every possible number placement of this pattern, which
has at least every number between 1 and 8 once and which is ordered, e.g. 1 appearing first, 2 before 3, 3 before 4 and so on. Then, I'll check if one of the automorphisms produces a smaller number placement. If not, I'll finally test
if the puzzle yields a unique solution.

This would be the first puzzle for the above pattern which only has the identity as an automorphism.

Code: Select all

 *-----------*
 |...|...|..1|
 |...|.12|...|
 |..1|..3|...|
 |---+---+---|
 |...|...|.1.|
 |.1.|.2.|3..|
 |.2.|1..|...|
 |---+---+---|
 |...|4..|...|
 |5..|...|.6.|
 |7..|...|8..|
 *-----------*


If you have more questions, please be specific or ask me on the programmers forum, if you want to talk about the algorithms.

[Serg]

Hello, Afmob!
Thank you for clarification of your method. I think finishing of my work (proving of 8-clue valid puzzles non-existance) it is still worth doing - to check possibilities of my method.

Serg

[coloin]

I could refer you to here where blue confirmed the 8 digit and 9 digit computations. [1131 and 18663]

Given that there is no 17 with less than 8 clues in 2 of the 3 horizontal bands - this makes for strong circumctancial evidence that a 12 clue puzzle will never be valid.

But thinking on

here i went on to find as many as puzzles with a complete central box as i could

a 9plus12

Code: Select all

+---+---+---+
|...|5..|1..|
|.98|...|...|
|...|...|.4.|
+---+---+---+
|5..|123|.7.|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|2.9|
|1..|3..|...|
|...|...|8..|
+---+---+---+

I found 55 "9plus12"s

I didnt find a 9plus11

Is this proof enough ?

C

[Serg]

Hi, coloin!
Thank you for your links. (I have no access to setbb.com because I am living in Russia.)

I'd like to ask you some questions about your investigation of patterns having central box (B5) filled. Have you done exhaustive search? If you have done it - have you check configurations with empty boxes (B1-B4, B6-B9)?

Serg

[coloin]

I didnt know about restrictions in russia.

I was maybe thinking Afmob and Blue were one and the same [?]

rMy search is pretty exhaustive - i did find 400,000 9plus13s.
I dont think the empty box search adds anything.

Thinking on again.....

If we know that in any sudoku puzle with more than 9 clues there will always be 2 clues in at least one box. This means that if there is no 9plus11 puzzle then that means that there is actually no 13 clue puzzle.

Proving there is no 9plus11 puzzle for certain might be a tricky one though.

C

[Serg]

Hi, coloin!

If we know that in any sudoku puzle with more than 9 clues there will always be 2 clues in at least one box. This means that if there is no 9plus11 puzzle then that means that there is actually no 13 clue puzzle.

I agree with you. If you have done exhaustive search for "9plus11 puzzles" and found nothing, this proves that there is no 13-clue puzzles. Maybe it is highest n-clues case for which non-existance was proven.

Serg

[coloin]

Well - rather than exaustive search for the [its actually 60] different 9plus12s - - probably it was more of an exausting search.

Dont know if it can be done easily though,

all 60 had these clues

Code: Select all

+---+---+---+
|1..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|123|...|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|..1|
+---+---+---+

still a lot of ways to add 9 more clues

C

[Serg]

Hi, coloin!

Well - rather than exaustive search for the [its actually 60] different

9plus12s - - probably it was more of an exausting search.

Dont know if it can be done easily though,

all 60 had these clues

Code: Select all

+---+---+---+
|1..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|123|...|
|...|456|...|
|...|789|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|..1|
+---+---+---+

still a lot of ways to add 9 more clues

Sorry, I am not understanding you. Do your propose to prove impossibility of 9plus11?

Serg

[Serg]

Hi, all!
Now I am finishing proof of non-existance 8-clue valid puzzles.

Let me recall well-known (and very useful) "Magic Pattern".

Code: Select all

x x x | x x x | x x x
x x x | . . . | x x x
x x x | . . . | x x x
------+-------+------
x . . | . . . | . . x
x . . | . x . | . . x
x . . | . . . | . . x
------+-------+------
x x x | . . . | x x x
x x x | . . . | x x x
x x x | x x x | x x x

It was discussed in 2007 (see thread Ask for some patterns that they don't have puzzles). Red Ed proved, that this pattern has no valid puzzles. Let me rearrange boxes of this pattern to such form:

Code: Select all

. . . | . . x | . . x
. x . | . . x | . . x
. . . | . . x | . . x
------+-------+------
. . . | x x x | x x x
. . . | x x x | x x x
x x x | x x x | x x x
------+-------+------
. . . | x x x | x x x
. . . | x x x | x x x
x x x | x x x | x x x

As you can see, Magic Pattern prohibits existance of valid puzzles with map

Code: Select all

1 1 1
1 9 9
1 9 9

because each pattern with this map will be subset of Magic Pattern.

So, we derived "Composition rule 3":

Code: Select all

Valid puzzles composition rules
-------------------------------

Rule 1.   Map of any valid puzzle must be isomorphic to one of these maps:

X X X    X X 0    X 0 0    X X 0    X X 0    X 0 0    X 0 0
X X X    X X X    X X X    X X X    X 0 X    0 X X    0 X X
X X X    X X X    X X X    0 X X    0 X X    X X X    0 X X

Rule 2.   Map posted below has no valid puzzles when A < 4

A 0 0
9 9 9
9 9 9

Rule 3.   Map posted below has no valid puzzles

1 1 1
1 9 9
1 9 9

All 8-clue puzzles variants posted above are subsets of the map from Rule 3, hence they have no valid puzzles.

Non-existance of 8-clue puzzles is proven.

Serg

[Serg]

Hi, people!
I'd like to prove non-existance of 9-clue valid puzzles.

There are 7 possible maps for valid puzzles.

Code: Select all

Type 1   Type 2   Type 3   Type 4   Type 5   Type 6   Type 7

X X X    X X 0    X 0 0    X X 0    X X 0    X 0 0    X 0 0
X X X    X X X    X X X    X X X    X 0 X    0 X X    0 X X
X X X    X X X    X X X    0 X X    0 X X    X X X    0 X X

9-clue valid puzzles of type 1 and type 2 are prohibited by "Composition rule 3" (i.e. by Magic Pattern). 9-clue valid puzzles of type 3 is impossible, because 10 clues at least are necessary to fill such map.

9-clue valid puzzles of type 4 are prohibited by "Composition rule 3", because for any clue placement will be at least 1 column and 1 row, containing no less than 1 clue in their boxes. For example, look at one possible map of type 4.

Code: Select all

1 1 0
1 2 1
0 1 2

In this example band B123 and stack B147 have no boxes, containing greater than 1 clue. So, this map can be morphed to Magic Pattern subset.

Type 6 has one possible map

Code: Select all

4 0 0
0 1 1
1 1 1

Obviously this map is subset of Magic Pattern.

Type 7 has 2 possible non-isomorphic maps

Code: Select all

4 0 0     5 0 0
0 2 1     0 1 1
0 1 1     0 1 1

Both maps are subsets of Magic Pattern.

So we must consider possible maps for type 5 only. Here are maps of type 5 being not prohibited by Magic Pattern.

Code: Select all

1 1 0   # map A     2 1 0   # map B     1 2 0   # map C
2 0 1               1 0 1               2 0 1
0 2 2               0 2 2               0 1 2

So we only need to prove non-existance of 3 maps above ("A","B","C").

Serg