How to prove non-existance of 8-clue valid puzzles?

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

Re:

Postby Serg » Thu Jul 14, 2011 8:27 am

Hi, Afmob!
Afmob wrote:To Serg, since you are now talking about the 10 clues case (you posted the 9 clues maps of type 7) there are 5 cases of type 7 maps:

Code: Select all
Type 7

6 0 0   5 0 0   4 0 0   4 0 0   4 0 0
0 1 1   0 2 1   0 3 1   0 2 2   0 2 1
0 1 1   0 1 1   0 1 1   0 1 1   0 1 2

You are right. I published all possible 9-clue maps of type 7. My mistake. Thank you for your correction. You really published all possible 10-clue maps of type 7.

But it is easy to prove non-existance of all 10-clue maps of type 7.
Maps
Code: Select all
6 0 0   5 0 0   4 0 0
0 1 1   0 2 1   0 3 1
0 1 1   0 1 1   0 1 1

are subsets of Magic Pattern (band B789 and stack B369 contain boxes having not greater than 1 clues only), so they are prohibited by composition rule 3.
Let's swap bands B456 and B789 in the last (5th) map in your list. We have remaining maps
Code: Select all
4 0 0   4 0 0
0 2 2   0 1 2
0 1 1   0 2 1

You can see both maps are prohibited by composition rule 4 because both maps are subsets of the map from this rule:
Code: Select all
9 9 0
9 9 2
0 2 1

Therefore no 10-clue valid puzzles of type 7 do exist.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Thu Jul 14, 2011 8:46 am

Hi, coloin!
coloin wrote:Sterling work Serg too.

Thanks.
coloin wrote:The lack of a 3/4/27 would eliminate many of your patterns Serg

I agree with you. But it is too complicated task - to prove non-existance of valid puzzles having 2 bands with not greater than 3 and 4 clues.
coloin wrote:Proving that there isnt a 9plus11 puzzle confirms that there is no 13 clue puzzle. :roll:

You are right provided exhaustive search for 9plus11 was done.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Thu Jul 14, 2011 9:43 pm

Hi, all!
I continue to prove non-existance of 10-clue valid puzzles.
I still should consider 2 types of maps:
Code: Select all
Type 4   Type 5

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

These types are the most complicated ones. I am surprised that patterns with diagonally arranged empty boxes have so many variants of filling.

Let's first consider type 5.

Type 5 maps have the next clue frequency distribution (map of type 5 always has 6 non-empty boxes).

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

Variants "C", "D", "E" have 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.

(Continuation follows)

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Fri Jul 15, 2011 6:57 am

Hi, people!
I continue to prove 10-clue valid puzzles impossibility (type 5).

I must consider remaining 2 distributions for type 5 filling (see my previous post).

A. 1 1 2 2 2 2 - 2 boxes contain 1 clue, 4 boxes contain 2 clues.
B. 1 1 1 2 2 3 - 3 boxes contain 1 clue, 2 boxes contain 2 clues, 1 box contains 3 clues.

Here are all possible non-isomorphic maps for clue distribution "A".
Code: Select all
Type 5

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

Both possible maps are prohibited by composition rule 4.

Here are all possible non-isomorphic maps for clue distribution "B".
Code: Select all
Type 5

1 1 0     1 1 0     1 2 0     2 1 0     1 2 0     2 1 0
1 0 2     2 0 1     1 0 1     1 0 1     2 0 1     2 0 1
0 2 3     0 2 3     0 2 3     0 2 3     0 1 3     0 1 3

All of these maps but 2 are prohibited by composition rule 4. Remaining 2 maps are posted below.
Code: Select all
Type 5

2 1 0     2 1 0
1 0 1     2 0 1
0 2 3     0 1 3

We can swap stacks B147/B258 and bands B456/B789 for both maps. We'll get such maps
Code: Select all
Type 5

1 2 0     1 2 0
2 0 3     1 0 3
0 1 1     0 2 1

It is obvious that both these maps are also prohibited by composition rule 4.

10-clue valid puzzles impossibility for puzzles, having type 5 maps, is proven.

So, I need consider maps of type 4 only to prove 10-clue valid puzzles impossibility.

(Continuation follows)

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Fri Jul 15, 2011 9:46 am

Hi, all!
I continue to prove non-existance of 10-clue valid puzzles.
I still should consider maps of type 4 :
Code: Select all
Type 4

X X 0
X X X
0 X X

Type 4 maps have the next clue frequency distribution (map of type 4 always has 7 non-empty boxes).

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

Variants "B", "C", have 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 non-isomorphic maps for clue distribution "A" (hope, I am not wrong).
Code: Select all
Type 4
 N1        N2        N3        N4        N5        N6       
1 1 0     1 1 0     1 1 0     1 1 0     1 1 0     1 1 0
1 1 2     1 2 1     1 2 2     2 1 1     2 1 2     2 1 2
0 2 2     0 2 2     0 2 1     0 2 2     0 1 2     0 2 1

 N7        N8        N9        N10       N11       N12
1 1 0     1 1 0     1 1 0     2 1 0     2 1 0     2 1 0
2 2 1     2 2 1     2 2 2     1 1 1     1 1 2     1 2 1
0 1 2     0 2 1     0 1 1     0 2 2     0 2 1     0 1 2

Maps N1, N2, N3, N5, N8 are prohibited by composition rule 3 (all these maps are subsets of Magic Pattern). Maps N4, N6, N7, N9, N11 are prohibited by composition rule 4.
Here are remaining maps:
Code: Select all
Type 4
 N10       N12
2 1 0     2 1 0
1 1 1     1 2 1
0 2 2     0 1 2

These maps cannot be excluded by existing composition rules. So, I should find additional composition rule. I need some time to do it.

(Continuation follows)

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Sun Jul 17, 2011 11:41 am

Hi, all!
I continue to prove non-existance of 10-clue valid puzzles.

I have 2 maps of type 4 only requiring non-existance proof:
Code: Select all
Type 4

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

To prove it I was forced to search for additional composition rule, excluding both maps. I found such rule:
Code: Select all
Rule 5.  Map posted below has no valid puzzles

0 1 2
1 9 9
2 9 9

you can notice map of rule 5 is very similar to map of rule 4:
Code: Select all
Rule 4.  Map posted below has no valid puzzles

1 2 0
2 9 9
0 9 9

Both maps belong to the same kind of maps (letters denote non-empty boxes):
Code: Select all
A B C
D 9 9
E 9 9

Moreover, both maps have the same "pattern" of filled boxes in band B123 and stack B147. So, I could use the same program for exhaustive search for valid puzzles to prove the new map has no valid puzzles. But map from rule 5 has substantially less automorphisms, hence the search required 2.5 CPU hours instead of 5 minutes for map of rule 4. Though I could optimize the program taking into account all possible automorphisms (I used not all possible automorphisms to simplify coding), it could take me much more time than 2.5 hours.

You can see that composition rule 5 excludes both remaining 10-clue maps, because both maps are subsets of the map of rule 5.

Non-existance of 10-clue valid puzzles is proven.

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Sun Jul 17, 2011 12:37 pm

Hi, people!
Now I am starting to prove impossibility of 11-clue valid puzzles.

Here is actual collection 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:

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

Let's first consider type 1.
Code: Select all
Type 1

X X X
X X X
X X X

Type 1 maps have the next clue distribution (map of type 1 always has 9 non-empty boxes).

A. 1 1 1 1 1 1 1 2 2 - 7 boxes contain 1 clue, 2 boxes contain 2 clues.
B. 1 1 1 1 1 1 1 1 3 - 8 boxes contain 1 clue, 1 box contains 3 clues.

Both variants have 2 or 1 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.

Let's consider maps of type 2.
Code: Select all
Type 2

X X 0
X X X
X X X

Type 2 maps have the next clue distribution (map of type 2 always has 8 non-empty boxes).

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

Variants "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 non-isomorphic maps for clue distribution "A":
Code: Select all
Type 2
 N1        N2        N3        N4        N5        N6        N7        N8        N9        N10
2 1 0     1 1 0     2 1 0     2 1 0     2 1 0     1 1 0     1 1 0     1 1 0     1 1 0     1 1 0
1 1 2     1 2 2     1 2 1     1 1 1     1 1 1     1 1 1     2 2 1     1 2 1     1 2 1     1 2 1
1 1 2     1 1 2     1 1 2     1 2 2     2 1 2     2 2 2     1 1 2     1 2 2     2 1 2     2 2 1

Maps N2, N5, N8, N10 are prohibited by composition rule 3 (all these maps are subsets of Magic Pattern). Maps N3, N4, N6, N7, N9 are prohibited by composition rule 5.
Here is remaining map:
Code: Select all
Type 2
 N1
2 1 0
1 1 2
1 1 2

Unfortunately, none of composition rules can exclude this map. I need additional composition rule ...

(Continuation follows)

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby dobrichev » Wed Jul 20, 2011 10:39 pm

Hi Serg,

Your approach is original and very interesting.

What about this alternative.

Each grid is composed of 3 disjoint and compatible 3-rookeries.
According to dukso there are 92048 distinct 3-rookeries.
Each of them has fixed minimal number of clues that solve the rookery. The minimal is 2.

The problem for proving the non-existence of n-clue puzzle could be transformed to demonstration of incompatibility of all combinations of 3-rookeries having sum(minclues) <= n. [Edit: This is wrong, only lower limit can be determined in this way. See the next post.]

The tricky part is how to check for compatibility in some optimal way. Checking canonical representation of the first rookery with all permutations of the second then third sounds desperate.

Maybe scanning the catalog of the essentially different grids, combining the 1-rookeries into 3 triplets of 3-rookeries in all possible ways, canonicalizing the 3-rookeries, making a lookup in the minclue catalog, and summing the minclues will give fast(?) answer for minimal clues required to define each grid? If it works it will be a revolution in our knowledge and will close most low-clue issues.

Or I am missing something obvious?
[Edit: I missed at least 2 details: the 4+ digit UA sets and the difference between 3-rookery and 3-template. See the next post.]

MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: How to prove non-existance of 8-clue valid puzzles?

Postby dobrichev » Thu Jul 21, 2011 8:20 am

Mixing the dreams with reality I totally forgot about the plenty of 4+ digit unavoidables awaiting to be hit. They are interaction between 3-rookeries.

Some details on the terms.
dukuso wrote:a k-rookery is a subset of the 81 cells in a 9*9 square which contains exactly k-cells
from each row,column,block

a k-template is a k-rookery whose 9*k cells are filled with numbers from {1,2,..,k},
such that the rookery-cells from each row,column,block contain each digit from {1,..,k}
exactly once

a sudokugrid is a 9-template, there are ~6.67e21 of them

for some k-rookeries there is no k-template, for others there are many
what's the maximum number of ways(k) to fill the cells in a k-rookery
to obtain a k-template ?

(1):1
(2):16? (O..O..... O..O..... ......OO. ......OO. .O..O.... .O..O.... .....O..O ..O..O... ..O.....O)
(8):1.59e16?
(9):6.67e21

So, the number of distinct 3-templates is 259272. The first and last of them alphabetically are respectively
Code: Select all
......123...123...123............231...231...231............312...312...312......
..1..2..3.2..3..1.3..1..2....2..3..1.3..1..2.1..2..3....3.2.1...1.3....22....1.3.

The number of 3-rookeries having at least one valid 3-template is 92048 (confirming dukso's count).
Code: Select all
......111...111...111............111...111...111............111...111...111......
..1..1..1.1..1..1.1..1..1....1..1.1..1..1.1..1..1....1..1.1..1..1.1..1..1....1..1


Nevertheless I will try to build a catalog of the minimal number of clues required to solve each of the 259272 3-template.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Thu Jul 21, 2011 9:37 pm

Hi, dobrichev!
dobrichev wrote:Hi Serg,

Your approach is original and very interesting.

Thanks.
dobrichev wrote:What about this alternative.

Each grid is composed of 3 disjoint and compatible 3-rookeries.
According to dukso there are 92048 distinct 3-rookeries.
Each of them has fixed minimal number of clues that solve the rookery. The minimal is 2.

Mladen, thank you for your links. They are very interesting, as usual. (I think you missed the letter in the name dukuso.) "Rookeries-analysis" approach looks like very attractive, but I feel lack of the rookery properties knowlege. I had an idea to limit analysis to the band B123 to investigate rookery properties better. (I mean subrookeries, spanning band B123 only and having 9*k cells instead of 27*k cells of odinary rookeries.) There are 162 (=9*6*3) such 1-subrookeries only, so it could be simpler to investigate their compatibility and other properties. Unfortunately I have not enough time now to investigate this theme. But I'll be glad to read your results in this area.
Good luck!

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Sat Jul 23, 2011 10:17 pm

Hi, all!
I checked several maps (while searching for a "composition rule 6" map), which could enable me to exclude the last map of type 2 for 11-clue maps analysis.
First of all, I found that maps
Code: Select all
1 1 2     2 1 1
1 9 9     1 9 9
1 9 9     1 9 9

have valid puzzles. More strictly saying, some patterns having one of these maps have valid puzzles, but others have no valid puzzles. In any case I cannot use these maps for composition rules. Really I proved more general result. Let's consider a class of maps (boxes B4, B5, B8, B9 are whole filled, boxes B1, B2, B3, B4, B7 contain nonzero number of clues each):
Code: Select all
A B C     # Boxes A, B, C, D, E are not empty
D 9 9
E 9 9

What maps belonging to this class have no valid puzzles? The answer is simple. The map from "composition rule 3" has no valid puzzles only. Here it is.
Code: Select all
Rule 3.  Map posted below has no valid puzzles

1 1 1
1 9 9
1 9 9

No other maps of this class can be used for composition rules.

Fortunately, I succeeded in finding "composition rule 6". It turns out that map
Code: Select all
Rule 6.  Map posted below has no valid puzzles

1 2 0
1 9 9
1 9 9

has no valid puzzles (it took me several minutes of CPU time to do exhaustive search).
Let me recall the last map of type 2 which should be proven to be non-existant:
Code: Select all
Type 2
 N1
2 1 0
1 1 2
1 1 2

If we swap stacks B147 and B258, we'll get such map:
Code: Select all
Type 2
 N1
1 2 0
1 1 2
1 1 2

You can see that posted above map of composition rule 6 contains this map as subset. Hence the map "N1" of type 2 has no valid puzzles.
Therefore all 11-clue maps of type 2 have no valid puzzles.

(Continuation follows)

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Sun Jul 24, 2011 12:09 pm

Hi, all!
I continue to prove non-existance of 11-clue valid puzzles.

Let me remind current composition rules list.
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

Let's consider maps of type 3.
Here are all possible non-isomorphic maps of type 3:
Code: Select all
Type 3
 N1        N2        N3
4 0 0     4 0 0     5 0 0
2 1 1     1 2 1     1 1 1
1 1 1     1 1 1     1 1 1

All variants are prohibited by composition rule 3 (see combination of band B789 and stack B369).

Let's consider maps of type 4.
Code: Select all
Type 4

X X 0
X X X
0 X X

Type 4 maps have the next clue distribution (map of type 4 always has 7 non-empty boxes).

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

Variants "C", "D", "E" 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.

Let's consider all possible non-isomorphic maps for clue distribution "B". We can assume that alone box having 3 clues is one of boxes B5, B8, B9:
Code: Select all
Type 4

X X 0     X X 0     X X 0
X 3 X     X X X     X X X
0 X X     0 3 X     0 X 3

What are possible boxes B1, B2, B4 (left top corner) configurations, provided they don't contain 3 clues? Here they are:
Code: Select all
Type 4
 N1        N2        N3        N4        N5
1 1 0     1 2 0     2 1 0     1 2 0     2 1 0
1 X X     1 X X     1 X X     2 X X     2 X X
0 X X     0 X X     0 X X     0 X X     0 X X

Map N1 is prohibited by composition rule 3. Map N2 is prohibited by composition rule 6. Map N4 is prohibited by composition rule 4.
Here are remaining maps:
Code: Select all
Type 4
 N3        N5
2 1 0     2 1 0
1 X X     2 X X
0 X X     0 X X

Now we can construct all possible non-isomorphic maps for clue distribution "B".
Code: Select all
Type 4
 A1       A2       A3       A4       A5       A6       A7       A8       A9       A10      A11
2 1 0    2 1 0    2 1 0    2 1 0    2 1 0    2 1 0    2 1 0    2 1 0    2 1 0    2 1 0    2 1 0
1 1 1    1 2 1    1 1 1    1 1 2    1 2 1    1 3 1    1 3 1    2 1 1    2 1 1    2 1 3    2 3 1
0 2 3    0 1 3    0 3 2    0 3 1    0 3 1    0 1 2    0 2 1    0 1 3    0 3 1    0 1 1    0 1 1

Maps A1, A3 are prohibited by composition rule 6 (see combination of band B456 and stack B147). Map A4, A5, A6, A7, A9 are prohibited by composition rule 5 (see combination of band B123 and stack B369). Maps A8, A10 are prohibited by composition rule 6 (see combination of band B123 and stack B258). Map A11 is prohibited by composition rule 3 (see combination of band B789 and stack B369). Here is remaining map:
Code: Select all
Type 4
 A2
2 1 0
1 2 1
0 1 3

This map seems cannot be prohibited by existing composition rules ...

(Continuation follows)

Serg

[Edited: 2 errors were corrected - distribution "D" of type 4 was wrong, distribution "E" was missed. These errors didn't effect proof though.]
Last edited by Serg on Mon Jul 25, 2011 10:34 pm, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Sun Jul 24, 2011 10:09 pm

Hi, all!
I continue proving non-existance of 11-clue valid puzzles.
Now I consider distribution "B" of type 4 maps.
My previous post finished at map
Code: Select all
Type 4
 A2
2 1 0
1 2 1
0 1 3

which couldn't be prohibited by available composition rules. So, I needed to find additional composition rule. One can guess that map
Code: Select all
2 1 0
1 9 9
0 9 9

has no valid puzzles. It does really have no valid puzzles. (I've done exhaustive search which took me about 5 min CPU time.) So, it is new composition rule:
Code: Select all
Rule 7.  Map posted below has no valid puzzles

2 1 0
1 9 9
0 9 9

You can see that composition rule 7 prohibits having valid puzzles for map A2 of type 4 distribution "B" (map A2 is subset of the rule7 map).

It is curious but all possible combinations of band+stack having "0 1 2" map (1 empty box, 1 box containing 1 clue, 1 box containing 2 clues) are present in composition rules list (rules 4, 5, 7). One can say the same for all possible combinations of band+stack having "1 1 1" map (all 3 boxes contain 1 clue each), because such bands/stacks are "automorphic" - they remain the same after boxes order changing.

So, distribution "B" of type 4 has no valid puzzles. Let's consider distribution "A":

A. 1 1 1 2 2 2 2 - 3 boxes contain 1 clue, 4 boxes contain 2 clues.

Let's consider "corner" of type 4 map (it marked by letter "C" in the map posted below):
Code: Select all
C C 0
C X X
0 X X

To be not excluded by available composition rules, such "corner" must contain 2 or 3 boxes having 2 clues. Two configurations only are possible (up to isomorph.):
Code: Select all
2 2 0     2 2 0
1 X X     2 X X
0 X X     0 X X

"Corner" cannot really contain 3 boxes having 2 clues, because the second "corner" of the map would contain 1 box having 2 clues (distribution "A" has 4 boxes containing 2 clues each). So, we should consider only maps having 2 2-clue boxes in both "corners":
Code: Select all
Type 4

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

The first map is excluded by composition rule 6 (see band B456 and stack B369). The second map is excluded by composition rule 5 (see band B123 and stack B369).

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

Serg
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby Serg » Wed Jul 27, 2011 11:32 pm

Hi, all!
I continue proving non-existance of 11-clue valid puzzles.

Now I am considering type 5.
Code: Select all
Type 5

X X 0
X 0 X
0 X X

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.
G. 1 2 2 2 2 2 - 1 box contains 1 clue, 5 boxes contain 2 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.

To limit maps variants which must be checked out, I'll prove the statement that contents of any non-empty box of type 5 map can be moved to any other non-empty box by some validity preserving transformations.

Let's consider 2 VPT.

VPT 1
1. Swap stacks B147/B258.
2. Swap bands B456/B789.

VPT 2
1. Swap stacks B258/B369.
2. Swap bands B123/B456.

Here are illustrations for these VPTs.
Code: Select all
VPT 1
        swap              swap                      Box contents exchanges
A B 0   stacks    B A 0   bands   B A 0     B1 <---> B2     B4 <---> B8     B6 <---> B9
C 0 D   ------>   0 C D   ----->  E 0 F
0 E F             E 0 F           0 C D

VPT 2
        swap              swap                      Box contents exchanges
A B 0   stacks    A 0 B   bands   C D 0     B1 <---> B4     B2 <---> B6     B8 <---> B9
C 0 D   ------>   C D 0   ----->  A 0 B
0 E F             0 F E           0 F E

If we'll apply VPT 1 and VPT 2 in turn to type 5 map (VPT 1, VPT 2, VPT 1, ...), the contents of box B1 will move to other boxes in such sequence: B1 --> B2 --> B6 --> B9 --> B8 --> B4 --> B1. All non-empty boxes of type 5 map are represented in this sequence. So, there must exist a VPT sequence (VPT 1, VPT 2, ... , VPT N; where N - "1" or "2"), moving any non-empty box contents to any "target" non-empty box.

Let's analyze distribution "D".

D. 1 1 1 2 2 4 - 3 boxes contain 1 clue, 2 boxes contain 2 clues, 1 box contains 4 clues.

We can move 4-clue box contents to any type 5 non-empty box. So, we can treat box B9 containing 4 clues.
Let's consider left top "corner" of type 5 map marked by letters "C":
Code: Select all
C C 0
C 0 X
0 X X

To be not excluded by available composition rules, such "corner" must contain 2 or 3 boxes having 2 clues. Only such maps are possible (up to isomorph.):
Code: Select all
 Type 5
 N1        N2
2 2 0     1 2 0
1 0 1     2 0 1
0 1 4     0 1 4

One can see that map N1, N2 are prohibited by composition rule 5 (band B456 + stack B258). So, distribution "D" of type 5 has no valid puzzles.

Let's analyze distribution "E".

E. 1 1 1 2 3 3 - 3 boxes contain 1 clue, 1 box contains 2 clues, 2 boxes contain 3 clues.

Each of both "corners" of this distribution maps must contain the box having 3 clues, otherwise (one corner contains both boxes having 3 clues) the corner not containing boxes having 3 clues would contain 1 box having 2 clues only and several boxes having 1 clue. It is impossible (see beginning of this post). We can treat box B9 containing 3 clues. Only such maps are possible (up to isomorph.):
Code: Select all
 Type 5
 N1        N2        N3        N4        N5
3 2 0     2 3 0     1 3 0     1 3 0     1 3 0
1 0 1     1 0 1     2 0 1     1 0 2     1 0 1
0 1 3     0 1 3     0 1 3     0 1 3     0 2 3

Map N1 is prohibited by composition rule 5 (band B456 + stack B258), map N2 is prohibited by composition rule 4 (band B456 + stack B147), map N3 is prohibited by composition rule 7 (band B456 + stack B147), map N4 is prohibited by composition rule 4 (band B456 + stack B147), map N5 is prohibited by composition rule 3 (band B456 + stack B147). So, distribution "E" of type 5 has no valid puzzles.

Let's analyze distribution "F".

F. 1 1 2 2 2 3 - 2 boxes contain 1 clue, 3 boxes contain 2 clues, 1 box contains 3 clues.

We can treat box B9 containing 3 clues. Left top corner must contain not less than 2 boxes having 2 clues, and cannot contain 1 clue in the box B1 (excluded by composition rule 4). Only such maps are possible (up to isomorph.):
Code: Select all
 Type 5
 N1        N2        N3
2 2 0     2 2 0     2 2 0
2 0 1     1 0 2     1 0 1
0 1 3     0 1 3     0 2 3

Maps N1, N2 are prohibited by composition rule 5 (band B456 + stack B258), map N3 is prohibited by composition rule 4 (band B456 + stack B147). So, distribution "F" of type 5 has no valid puzzles.

Let's analyze distribution "G".

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

We can move 1-clue box contents (by series of VPT 1, VPT 2, VPT 1, ... transformations) to B1 box, and we can see only one possible map:
Code: Select all
1 2 0
2 0 2
0 2 2

You can see that this map is prohibited by composition rule 4. So, distribution "G" of type 5 has no valid puzzles.

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

(I hardly believe that anyone can check my statements. For what puposes am I writing my huge posts? I don't know.)

(Continuation follows)

Serg

[Edited: I corrected the error in my proof - distribution "G" for type 5 was missed. Thanks to ronk for his correction]
Last edited by Serg on Thu Jul 28, 2011 1:11 pm, edited 1 time in total.
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: How to prove non-existance of 8-clue valid puzzles?

Postby ronk » Thu Jul 28, 2011 10:15 am

Serg wrote: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.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to General