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
How to prove non-existance of 8-clue valid puzzles?
50 posts
• Page 2 of 4 • 1, 2, 3, 4
Re: How to prove non-existance of 8-clue valid puzzles?
by 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:
Serg
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:
Serg
- Serg
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
by Afmob » Sat Jul 02, 2011 1:12 pm
You forgot some cases (for 8 clues, I haven't checked your 9 clues analysis):
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.
- 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: 132
- Joined: 28 June 2011
Re:
by Serg » Sat Jul 02, 2011 5:32 pm
Hello, Afmob!
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
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
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: How to prove non-existance of 8-clue valid puzzles?
by 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:
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
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: 1010
- Joined: 16 March 2006
Re: How to prove non-existance of 8-clue valid puzzles?
by Serg » Sun Jul 03, 2011 2:45 pm
Hi, RW!
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.
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
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: 890
- Joined: 01 June 2010
- Location: Russia
Re: How to prove non-existance of 8-clue valid puzzles?
by 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: 1010
- Joined: 16 March 2006
Re: How to prove non-existance of 8-clue valid puzzles?
by Serg » Tue Jul 05, 2011 7:20 am
Hi, all!
So, we must prove that patterns with these maps
have no valid puzzles to prove impossibility of 9-clue valid puzzles. We need another "magic pattern". Let's check map
Unfortunately, it has valid puzzles. Here is an example:
It is well known, that pattern "3 Holes"
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:
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:
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
It turns out that such patterns have no valid puzzles (I've done exhaustive search). This map excludes 9-clue valid puzzles with map
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
It is obviuos that map
contains it as subset.
But we can get even more if map
has no valid puzzles. We must examine 5 variants of the band B123 to prove that this map has no valid puzzles:
(Continuation follows)
Serg
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
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re:
by Serg » Mon Jul 11, 2011 9:28 am
Hi, Afmob!
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
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: 890
- Joined: 01 June 2010
- Location: Russia
Re: How to prove non-existance of 8-clue valid puzzles?
by Serg » Tue Jul 12, 2011 3:13 pm
Hi, all!
It turns out, that map
has valid puzzles, so it cannot be used in "composition rules".
But map
has no valid puzzles. To prove this statement I had to analyze all 15 non-isomorphic patterns having this map. Here they are.
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
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.
Non-existance of 9-clue valid puzzles is proven.
Let me refresh composition rule's list.
Serg
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
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re:
by 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: 2494
- Joined: 05 May 2005
- Location: Devon
Re: How to prove non-existance of 8-clue valid puzzles?
by 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).
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.
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).
Obviously it is subset of Magic Pattern (composition rule 3).
Serg
(Continuation follows)
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
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
Re: How to prove non-existance of 8-clue valid puzzles?
by 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.
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
Let's swap bands B456 and B789 in these maps:
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.
Maps
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
You can see both maps are prohibited by composition rule 4, because both maps are subsets of the map from this rule:
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.]
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
- 2018 Supporter
- Posts: 890
- Joined: 01 June 2010
- Location: Russia
by 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.
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: 132
- Joined: 28 June 2011
Re: How to prove non-existance of 8-clue valid puzzles?
by coloin » Wed Jul 13, 2011 8:48 pm
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
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: 2494
- Joined: 05 May 2005
- Location: Devon
50 posts
• Page 2 of 4 • 1, 2, 3, 4
