The New Sudoku Players' Forum

[Serg]

Hi, ronk!

Type 5 maps have next clue by box distributions (map of type 5 always has 6 non-empty boxes).

A. 1 1 1 1 1 6 - 5 boxes contain 1 clue, 1 box contains 6 clues.
B. 1 1 1 1 2 5 - 4 boxes contain 1 clue, 1 box contains 2 clues, 1 box contains 5 clues.
C. 1 1 1 1 3 4 - 4 boxes contain 1 clue, 1 box contains 3 clues, 1 box contains 4 clue.
D. 1 1 1 2 2 4 - 3 boxes contain 1 clue, 2 boxes contain 2 clues, 1 box contains 4 clues.
E. 1 1 1 2 3 3 - 3 boxes contain 1 clue, 1 box contains 2 clues, 2 boxes contain 3 clues.
F. 1 1 2 2 2 3 - 2 boxes contain 1 clue, 3 boxes contain 2 clues, 1 box contains 3 clues.

I'm curiouus as to why there's not a ...

G. 1 2 2 2 2 2 - 1 box contains 1 clue, 5 boxes contain 2 clues.

You are right, I missed distribution "1 2 2 2 2 2". Thank you for your correction! I am very surprised - I've decided to check my last post for any errors about a half an hour ago and really found error - absent distribution. I didn't see your post that moment. But when I logged in to edit my post I discovered your correction . Definitely our thoughts are moving at the speed of light! I think I was induced by your thouhgts, ronk!

It turns out some people read my posts . I'll edit an error in my previous post.

Serg

[Serg]

Hi, all!
I am finishing proof of 11-clue valid puzzles non-existance.
There are 2 remaining map types (type 6 and type 7) only. It is easy to prove non-existance of such maps.

Let's consider type 6.

Code: Select all

Type 6

X 0 0
0 X X
X X X


Type 6 maps have the next clue distribution (map of type 6 always has 6 non-empty boxes) after applying composition rule 2 - every distribution must have at least 1 box containing not less than 4 clues.

A. 1 1 1 1 1 6 - 5 boxes contain 1 clue, 1 box contains 6 clues.
B. 1 1 1 1 2 5 - 4 boxes contain 1 clue, 1 box contains 2 clues, 1 box contains 5 clues.
C. 1 1 1 1 3 4 - 4 boxes contain 1 clue, 1 box contains 3 clues, 1 box contains 4 clues.
D. 1 1 1 2 2 4 - 3 boxes contain 1 clue, 2 boxes contain 2 clues, 1 box contains 4 clues.

Variants "A", "B", "C" have 1 or 2 boxes having greater than 1 clue only. Hence maps of these variants must have at least 1 band and 1 stack with all boxes having not greater than 1 clue. So, maps of these variants are subsets of Magic Pattern and are prohibited by composition rule 3.

Here are all possible maps for distribution "D".

Code: Select all

Type 6
 N1        N2        N3        N4        N5        N6
4 0 0     4 0 0     4 0 0     4 0 0     4 0 0     4 0 0
0 1 1     0 2 1     0 2 2     0 1 1     0 2 1     0 1 2
2 2 1     2 1 1     1 1 1     1 2 2     1 2 1     1 2 1


Map N1 is prohibited by composition rule 3 (band B456 + stack B369). Map N2 is prohibited by composition rule 6 (band B456 + stack B369). Map N3 is prohibited by composition rule 6 (band B789 + stack B369). Maps N4, N5 are prohibited by composition rule 6 (band B456 + stack B369). Map N6 is prohibited by composition rule 7 (band B456 + stack B369). So, distribution "D" of type 6 has no valid puzzles.

Therefore, type 6 of 11-clue maps has no valid puzzles.

Let's consider type 7.

Code: Select all

Type 7

X 0 0
0 X X
0 X X


Type 7 maps have the next clue distribution (map of type 7 always has 5 non-empty boxes) after applying composition rule 2 - every distribution must have at least 1 box containing not less than 4 clues.

A. 1 1 1 1 7 - 4 boxes contain 1 clue, 1 box contains 7 clues.
B. 1 1 1 2 6 - 3 boxes contain 1 clue, 1 box contains 2 clues, 1 box contains 6 clues.
C. 1 1 1 3 5 - 3 boxes contain 1 clue, 1 box contains 3 clues, 1 box contains 5 clues.
D. 1 1 1 4 4 - 3 boxes contain 1 clue, 2 boxes contain 4 clues.
E. 1 1 2 2 5 - 2 boxes contain 1 clue, 2 boxes contain 2 clues, 1 box contains 5 clues.
F. 1 1 2 3 4 - 2 boxes contain 1 clue, 1 box contains 2 clues, 1 box contains 3 clues, 1 box contains 4 clue.
G. 1 2 2 2 4 - 1 box contains 1 clue, 3 boxes contain 2 clues, 1 box contains 4 clues.

Variants "A", "B", "C", "D" have 1 or 2 boxes having greater than 1 clue only. Hence maps of these variants must have at least 1 band and 1 stack with all boxes having not greater than 1 clue. So, maps of these variants are prohibited by composition rule 3.

Here are all possible maps for distribution "E".

Code: Select all

Type 7
 N1        N2
5 0 0     5 0 0
0 1 1     0 2 1
0 2 2     0 1 2


Maps N1, N2 are prohibited by composition rule 4 (band B456 + stack B369).

Here are all possible maps for distribution "F".

Code: Select all

Type 7
 N1        N2
4 0 0     4 0 0
0 1 1     0 2 1
0 2 3     0 1 3


Map N1 is prohibited by composition rule 4 (band B456 + stack B258). Map N2 is prohibited by composition rule 7 (band B456 + stack B258).

Here is the only possible map for distribution "G".

Code: Select all

Type 7
 N1
4 0 0
0 1 2
0 2 2


Map N1 is prohibited by composition rule 4 (band B456 + stack B258).

Therefore, type 7 of 11-clue maps has no valid puzzles, and 11-clue valid puzzles don't exist.

Summary of composition rules.

Code: Select all

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

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

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

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

Rule 4.  Map posted below has no valid puzzles

1 2 0
2 9 9
0 9 9

Rule 5.  Map posted below has no valid puzzles

0 1 2
1 9 9
2 9 9

Rule 6.  Map posted below has no valid puzzles

1 2 0
1 9 9
1 9 9

Rule 7.  Map posted below has no valid puzzles

2 1 0
1 9 9
0 9 9


Serg

[Serg]

Hi, people!
I saw my method works, so I met my goal. It isn't worth proving non-existance of 12,13,14,15-clue valid puzzles if 16-clue valid puzzles don't exist (non-existance of 16-clue valid puzzles proves non-existance of all valid puzzles having less clues). So, I intend to prove non-existance of 16-clue valid puzzles by "composition rules" method. Surely it is much more complicated than proving non-existance of 11-clue valid puzzles. I shall have to search for new "composition rules" maps having less than 4 boxes with 9 clues. Such small number of "fixed" boxes (having 9 clues exactly) makes such search more difficult. So, I need some time to optimize my program to be able for searching for such maps.

I am closing this thread. Hope I'll open in a time separate thread on the theme of proving non-existance of 16-clue valid puzzles.

See you later.
Serg

[Edit: I corrected a typo concerning 9-clue boxes statement.]

[eleven]

Congratulations, if you proved the 11 clue case. I dont have the time to verify it, but i do know, that it is a hard job.

But if you really want to prove the 16 clue case, i wish you an ingenious idea, a long life and a nanocomputer

[Serg]

Hi, eleven!

Congratulations, if you proved the 11 clue case.

Thanks. I've really proven non-existance of 11-clue valid puzzles (at least I am sure I've done it). The method looks like strange, I think, because it combines both logical proofs and computer search results. When I started with 8-clue valid puzzles analysis (having 2 composition rules only) I thought a number of composition rules will grow up fast during moving to higher clue puzzles. But it was surprise for me that number of composition rules didn't grow up substantially. It is optimistic observation.

But if you really want to prove the 16 clue case, i wish you an ingenious idea, a long life and a nanocomputer

Thank you. I have badminton racquet "Yonex Nanospeed". Maybe It can be useful too .

Serg