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

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

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

Sorry,
I've just noticed that "map A" and "map B" are isomorphic to each other. So, we need to prove non-existance of 2 maps only:
Code: Select all
`2 1 0     2 1 01 0 1     1 0 20 2 2     0 2 1`

Serg
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

You forgot some cases (for 8 clues, I haven't checked your 9 clues analysis):

Code: Select all
`Type 51 1 0   2 1 01 0 1   1 0 10 1 3   0 1 2`

Both cannot yield valid puzzles because they are subset of "magic-pattern".

Type 7 is also not complete, but all other cases have less than 4 clues in B1.
Afmob

Posts: 130
Joined: 28 June 2011

### Re:

Hello, Afmob!
Afmob wrote:You forgot some cases (for 8 clues, I haven't checked your 9 clues analysis):

Code: Select all
`Type 51 1 0   2 1 01 0 1   1 0 10 1 3   0 1 2`

Both cannot yield valid puzzles because they are subset of "magic-pattern".

Type 7 is also not complete, but all other cases have less than 4 clues in B1.

I didn't forget type 5 and type 7 variants, but I didn't publish these variants because I thought they were obvious. In any case "composition rule 2" and "composition rule 3" (Magic Pattern) exclude all possible 8-clue variants.

Serg
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

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

Another way to prove these would be to look at different rookeries. Some data about the 17s a year ago:
dukuso wrote:checking gordon's 17s, the minimum numbers of clues required to uniquely
solve a 1,2,..,9 rookery are 0,1,2,3,5,7,10,13,17

If it can be proved that a 5-rookery cannot be solved in 4 clues, then we have proved that 8-clue puzzles cannot exist. I actually thought there was a proof for this 5-rookery case, but I couldn't find it searching the forums...

Even better, if it can be proved that a 6-rookery cannot be solved in 6 clues, then we have proved that 12-clue puzzles cannot exist. With only 92053 different 6-rookeries, this shouldn't even be impossible, I think.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

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

Hi, RW!
RW wrote:Another way to prove these would be to look at different rookeries. Some data about the 17s a year ago:
dukuso wrote:checking gordon's 17s, the minimum numbers of clues required to uniquely
solve a 1,2,..,9 rookery are 0,1,2,3,5,7,10,13,17

Interesting. I read another interesting thread, concerning rookery analysis approach to the proof of 16-clue valid puzzles non-existance. (See thread Structures of the solution grid.) But I have no good idea yet in what way it can be done by rookery analysis approach.
RW wrote:If it can be proved that a 5-rookery cannot be solved in 4 clues, then we have proved that 8-clue puzzles cannot exist. I actually thought there was a proof for this 5-rookery case, but I couldn't find it searching the forums...

Even better, if it can be proved that a 6-rookery cannot be solved in 6 clues, then we have proved that 12-clue puzzles cannot exist. With only 92053 different 6-rookeries, this shouldn't even be impossible, I think.

Can you explain your ideas about 8-clue and 12-clue puzzles non-existance proving by statements "5-rookery cannot be solved in 4 clues" and "6-rookery cannot be solved in 6 clues"?

Serg
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

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

Serg wrote:Can you explain your ideas about 8-clue and 12-clue puzzles non-existance proving by statements "5-rookery cannot be solved in 4 clues" and "6-rookery cannot be solved in 6 clues"?

A valid 8-clue puzzle must have the digit distribution 011111111, otherwise there would be two missing digits = multiple solutions. A 5-rookery solved in 4 clues must have the digit distribution 01111 for the same reason. If the second is impossible, then so is the first.

If a 6-rookery cannot be solved in 6-clues, then the digit distribution in any puzzle must be such that choosing any 6 digits, there must always be a total of at least 7 given clues. This is imposible with 12 clues. The closest you get is 111111222, the first 6 digits have only a total of 6 clues.

[Edit: about the 5-rookery in 4 clues, JPF did some tries here but I don't know how exhaustive the search was. And looking for a 5-rookery with 120 solutions is not quite the same as looking for a 5-rookery that can be solved with only 4 clues.]

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

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

Hi, all!
So, we must prove that patterns with these maps
Code: Select all
`2 1 0     2 1 01 0 1     1 0 20 2 2     0 2 1`

have no valid puzzles to prove impossibility of 9-clue valid puzzles. We need another "magic pattern". Let's check map
Code: Select all
`1 9 09 9 90 9 9`

Unfortunately, it has valid puzzles. Here is an example:
Code: Select all
`+-----+-----+-----+|1 . .|4 5 7|. . .||. . .|1 8 9|. . .||. . .|2 3 6|. . .|+-----+-----+-----+|2 3 1|5 4 8|7 9 6||5 6 4|7 9 1|3 2 8||8 9 7|3 6 2|1 5 4|+-----+-----+-----+|. . .|8 7 4|9 6 2||. . .|9 2 3|5 7 1||. . .|6 1 5|8 4 3|+-----+-----+-----+`

It is well known, that pattern "3 Holes"
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 x x|x x x|+-----+-----+-----+`

has no valid puzzles. Adding 1 clue to the box B1 transformed it to the pattern having valid puzzles. So, this pattern is good candidate for maximal pattern. It turns out that adding 1 clue to the box B3 transforms this pattern to the pattern having valid puzzles. Here is an example:
Code: Select all
`+-----+-----+-----+|. . .|4 5 8|. . 9||. . .|1 7 9|. . .||. . .|2 3 6|. . .|+-----+-----+-----+|2 1 4|3 6 5|7 9 8||3 9 8|7 1 2|5 4 6||5 6 7|9 8 4|2 3 1|+-----+-----+-----+|. . .|6 9 7|3 1 5||. . .|5 4 3|9 8 2||. . .|8 2 1|4 6 7|+-----+-----+-----+`

So, pattern "3 Holes" is maximal, i.e. it has no valid puzzles, but adding 1 clue transforms it to the puzzle having valid puzzles. Let me reaarange its empty boxes to nicer view:
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 x x|x x x|+-----+-----+-----+`

Though it is rather interesting (for me, at least), but gives nothing for impossibility of 9-clue valid puzzles proving.

So, let's consider patterns with map
Code: Select all
`1 1 09 9 90 9 9`

It turns out that such patterns have no valid puzzles (I've done exhaustive search). This map excludes 9-clue valid puzzles with map
Code: Select all
`2 1 01 0 10 2 2`

To see it more clear let's swap bands B123 and B456 of the map posted above, then swap stacks B258 and B369. We'll get map
Code: Select all
`1 1 02 0 10 2 2`

It is obviuos that map
Code: Select all
`1 1 09 9 90 9 9`

contains it as subset.

But we can get even more if map
Code: Select all
`1 2 09 9 90 9 9`

has no valid puzzles. We must examine 5 variants of the band B123 to prove that this map has no valid puzzles:
Code: Select all
`+-----+-----+-----+     Variant A|x . .|. . .|. . .||. . .|x x .|. . .||. . .|. . .|. . .|+-----+-----+-----++-----+-----+-----+     Variant B|x . .|x . .|. . .||. . .|x . .|. . .||. . .|. . .|. . .|+-----+-----+-----++-----+-----+-----+     Variant C|x . .|. . .|. . .||. . .|x . .|. . .||. . .|x . .|. . .|+-----+-----+-----++-----+-----+-----+     Variant D|x . .|x . .|. . .||. . .|. x .|. . .||. . .|. . .|. . .|+-----+-----+-----++-----+-----+-----+     Variant E|x . .|. . .|. . .||. . .|x . .|. . .||. . .|. x .|. . .|+-----+-----+-----+`

(Continuation follows)

Serg
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

I did a run on the 11 clues case and got the following results:

Patterns: 2,047,365
Puzzles: 8,183,602,790 with none of them having a unique solution

The search took about 50.5 hours. I won't try the 12 clues case.
Afmob

Posts: 130
Joined: 28 June 2011

### Re:

Hi, Afmob!
Afmob wrote:I did a run on the 11 clues case and got the following results:

Patterns: 2,047,365
Puzzles: 8,183,602,790 with none of them having a unique solution

The search took about 50.5 hours. I won't try the 12 clues case.

Thank you for posted results. 11-clue case looks like an ultimate for the method you are using. I think my method ("composition rules") has similar limitation.

Now I am still searching for the map for "composition rule 4" to prove impossibility of 9-clue valid puzzles.

Serg
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

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

Hi, all!
It turns out, that map
Code: Select all
`1 2 09 9 90 9 9`

has valid puzzles, so it cannot be used in "composition rules".
But map
Code: Select all
`1 2 02 9 90 9 9`

has no valid puzzles. To prove this statement I had to analyze all 15 non-isomorphic patterns having this map. Here they are.
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 .|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|     |. . .|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 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 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 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 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 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 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|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 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 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|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 took me not so much CPU time to do exhaustive search for these 15 patterns (CPU time varied from seconds to tens of seconds for given patterns; about 5 minutes of CPU time were consumed in total for all patterns).

So, map
Code: Select all
`1 2 02 9 90 9 9`

has no valid patterns and can be used as "composition rule". Everyone can see that this map excludes existance of the both remaining maps for 9-clue case, because both maps produce patterns being subsets of considered map.
Serg wrote:So, we need to prove non-existance of 2 maps only:
Code: Select all
`2 1 0     2 1 01 0 1     1 0 20 2 2     0 2 1`

Serg

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

Let me refresh composition rule's list.
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 0X X X    X X X    X X X    X X X    X 0 X    0 X X    0 X XX X X    X X X    X X X    0 X X    0 X X    X X X    0 X XRule 2.  Map posted below has no valid puzzles when A < 4A 0 09 9 99 9 9Rule 3.  Map posted below has no valid puzzles1 1 11 9 91 9 9Rule 4.  Map posted below has no valid puzzles1 2 02 9 90 9 9`

Serg
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

### Re:

Afmob wrote:I did a run on the 11 clues case and got the following results:

Patterns: 2,047,365
Puzzles: 8,183,602,790 with none of them having a unique solution

The search took about 50.5 hours. I won't try the 12 clues case.

Just to confirm - bearing in mind your concerted effort !

Was this the case for 11 clues on its own - or 11 clues plus a full box 5 ?

Well done in any case.

C
coloin

Posts: 1702
Joined: 05 May 2005

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

Hi, people!
Now I am starting to prove impossibility of 10-clue valid puzzles. I'll show my proof in more details to simplify cross-check of my results.

Let's consider all possible maps for 10-clue valid puzzles of type 1 (there is only one non-isomorph. map).
Code: Select all
`Type 11 1 11 1 11 1 2`

It is obvious that this map has no valid puzzles, because it subset of Magic Pattern (composition rule 3).

Let's consider all possible maps of type 2.
Code: Select all
`Type 21 1 0     1 2 0     1 1 0     1 1 0     1 1 0     1 1 0     1 1 0     1 1 01 1 2     1 1 2     1 2 2     1 1 2     1 2 1     1 2 1     1 1 3     1 3 11 1 2     1 1 1     1 1 1     1 2 1     1 2 1     2 1 1     1 1 1     1 1 1`

In any way there must exist a band having boxes which contain no more than 1 clue only and a stack having boxes which contain no more than 1 clue only. Hence all these maps are subsets of Magic Pattern (composition rule 3), 10-clue valid puzzles of type 2 are impossible.

Let's consider all possible maps of type 3 after applying composition rule 2 (there is only one non-isomorph. map).
Code: Select all
`Type 34 0 01 1 11 1 1`

Obviously it is subset of Magic Pattern (composition rule 3).

Serg
(Continuation follows)
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

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

Hi, all!
This post continues proof of 10-clue valid puzzles impossibility.

Let's consider all possible maps for 10-clue valid puzzles of type 6 after applying composition rule 2.
Code: Select all
`Type 64 0 0     4 0 0     4 0 0     5 0 00 1 1     0 1 1     0 2 1     0 1 12 1 1     1 2 1     1 1 1     1 1 1`

It is obvious that 2 last maps are prohibited by composition rule 3 (i.e. by Magic Pattern). So, we need to prove impossibility of the first 2 maps
Code: Select all
`Type 64 0 0     4 0 00 1 1     0 1 12 1 1     1 2 1`

Let's swap bands B456 and B789 in these maps:
Code: Select all
`Type 64 0 0     4 0 02 1 1     1 2 10 1 1     0 1 1`

You can see that these 2 maps are also prohibited by composition rule 3 (i.e. by Magic Pattern).

Let's consider all possible maps of type 7 after applying composition rule 2.
Code: Select all
`Type 76 0 0   5 0 0   4 0 0   4 0 0   4 0 00 1 1   0 2 1   0 3 1   0 2 2   0 1 20 1 1   0 1 1   0 1 1   0 1 1   0 2 1`

Maps
Code: Select all
`Type 76 0 0   5 0 0   4 0 00 1 1   0 2 1   0 3 10 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.
We have to prove impossibility of remaining maps
Code: Select all
`Type 74 0 0   4 0 00 2 2   0 1 20 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 09 9 20 2 1`

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

(Continuation follows)

Serg

[Edited: A mistake in type 7 maps analysys was corrected. Thanks to Afmob.]
Last edited by Serg on Thu Jul 14, 2011 8:44 pm, edited 1 time in total.
Serg
2018 Supporter

Posts: 573
Joined: 01 June 2010
Location: Russia

coloin wrote:Just to confirm - bearing in mind your concerted effort !

Was this the case for 11 clues on its own - or 11 clues plus a full box 5 ?

Well done in any case.

Sorry for my late reply, I didn't see your post between Serg's large posts.
I checked all cases without a full box 5, so just all patterns with 11 clues excluding ones with more than one free row/column per band.

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 76 0 0   5 0 0   4 0 0   4 0 0   4 0 00 1 1   0 2 1   0 3 1   0 2 2   0 2 10 1 1   0 1 1   0 1 1   0 1 1   0 1 2`
Afmob

Posts: 130
Joined: 28 June 2011

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

Thanks Afmob. Thats some job. Sterling work Serg too.

Since you have done the 11 clues ......

Proving there isnt a clues in bands count of 3/4/27 also confirms that there isnt a 3/4/5 ie no 12 clue puzzle.
Edit - a 4/4/9 does exist so that scuppers that one....
The lack of a 3/4/27 would eliminate many of your patterns Serg

Proving that there isnt a 9plus11 puzzle confirms that there is no 13 clue puzzle.

C
coloin

Posts: 1702
Joined: 05 May 2005

PreviousNext