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?

Postby Serg » Sat Jul 02, 2011 10:29 am

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 0
1 0 1     1 0 2
0 2 2     0 2 1


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

Postby Afmob » Sat Jul 02, 2011 1:12 pm

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

Code: Select all
Type 5

1 1 0   2 1 0
1 0 1   1 0 1
0 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:

Postby Serg » Sat Jul 02, 2011 5:32 pm

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

Code: Select all
Type 5

1 1 0   2 1 0
1 0 1   1 0 1
0 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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

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

Postby RW » Sun Jul 03, 2011 8:43 am

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?

Postby Serg » Sun Jul 03, 2011 2:45 pm

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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

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

Postby RW » Sun Jul 03, 2011 3:48 pm

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?

Postby Serg » Tue Jul 05, 2011 7:20 am

Hi, all!
So, we must prove that patterns with these maps
Code: Select all
2 1 0     2 1 0
1 0 1     1 0 2
0 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 0
9 9 9
0 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 0
9 9 9
0 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 0
1 0 1
0 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 0
2 0 1
0 2 2

It is obviuos that map
Code: Select all
1 1 0
9 9 9
0 9 9

contains it as subset.

But we can get even more if map
Code: Select all
1 2 0
9 9 9
0 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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Postby Afmob » Mon Jul 11, 2011 7:48 am

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:

Postby Serg » Mon Jul 11, 2011 9:28 am

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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

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

Postby Serg » Tue Jul 12, 2011 3:13 pm

Hi, all!
It turns out, that map
Code: Select all
1 2 0
9 9 9
0 9 9

has valid puzzles, so it cannot be used in "composition rules".
But map
Code: Select all
1 2 0
2 9 9
0 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 0
2 9 9
0 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 0
1 0 1     1 0 2
0 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 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


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

Re:

Postby coloin » Tue Jul 12, 2011 9:22 pm

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: 1629
Joined: 05 May 2005

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

Postby Serg » Tue Jul 12, 2011 10:19 pm

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 1

1 1 1
1 1 1
1 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 2

1 1 0     1 2 0     1 1 0     1 1 0     1 1 0     1 1 0     1 1 0     1 1 0
1 1 2     1 1 2     1 2 2     1 1 2     1 2 1     1 2 1     1 1 3     1 3 1
1 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 3

4 0 0
1 1 1
1 1 1

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

Serg
(Continuation follows)
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

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

Postby Serg » Wed Jul 13, 2011 7:12 am

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 6

4 0 0     4 0 0     4 0 0     5 0 0
0 1 1     0 1 1     0 2 1     0 1 1
2 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 6

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

Let's swap bands B456 and B789 in these maps:
Code: Select all
Type 6

4 0 0     4 0 0
2 1 1     1 2 1
0 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 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 1 2
0 1 1   0 1 1   0 1 1   0 1 1   0 2 1

Maps
Code: Select all
Type 7

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.
We have to prove impossibility of remaining maps
Code: Select all
Type 7

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.

(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
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Postby Afmob » Wed Jul 13, 2011 4:13 pm

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. :lol:
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 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
Afmob
 
Posts: 130
Joined: 28 June 2011

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

Postby coloin » Wed Jul 13, 2011 8:48 pm

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

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. :roll:

C
coloin
 
Posts: 1629
Joined: 05 May 2005

PreviousNext

Return to General