Ask for patterns that they dont have puzzles 2

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

Ask for patterns that they dont have puzzles 2

Postby coloin » Thu Aug 15, 2013 8:58 pm

This is a follow-on post to ask for patterns that they dont have puzzles here

A while ago i posted here on various patterns of clues which dont have puzzles.
Somewhat unsatisfactorily proof was distinctly lacking however.
So this thread takes it furthur - if it is possible.

Serg and blue have taken careful work to tabulate patterns which cant have puzzles with proof.
one clue box patterns
investigation of one band free patterns
investigation of one crossing free patterns

Proof that patterns dont have puzzles is established either by
iterating through all possible ED options for the clues
or
showing that all ways to fill the empty spaces in a puzzle will always have an unavoidable set not hit by a clue.

Potential patterns can be disregarded if they are solely composed of clues from proven invalid maximal patterns.

3 Invalid patterns

1.Trivially this was first done with this pattern which needs 1 clue in 2 rows [always at least 1 UA]
2.Three empty box pattern was shown - to require one clue. [always at least 1 UA]here.
3.this also means that the four box pattern therefore requires at least two clues and this is indeed the case. [always at least 2 UAs]

Code: Select all
Maximal Pattern
1.+---+---+---+  2.+---+---+---+  3.+---+---+---+
  |...|...|...|    |...|...|xxx|    |x..|...|xxx|
  |...|...|...|    |...|...|xxx|    |...|...|xxx|
  |xxx|xxx|xxx|    |...|...|xxx|    |...|...|xxx|
  +---+---+---+    +---+---+---+    +---+---+---+
  |xxx|xxx|xxx|    |...|xxx|xxx|    |...|...|xxx|
  |xxx|xxx|xxx|    |...|xxx|xxx|    |...|...|xxx|
  |xxx|xxx|xxx|    |...|xxx|xxx|    |...|...|xxx|
  +---+---+---+    +---+---+---+    +---+---+---+
  |xxx|xxx|xxx|    |xxx|xxx|xxx|    |xxx|xxx|xxx|
  |xxx|xxx|xxx|    |xxx|xxx|xxx|    |xxx|xxx|xxx|
  |xxx|xxx|xxx|    |xxx|xxx|xxx|    |xxx|xxx|xxx|
  +---+---+---+    +---+---+---+    +---+---+---+
 
Valid puzzle example with one added clue 
1.+---+---+---+  2.+---+---+---+  3.+---+---+---+
  |...|...|..6|    |7..|...|298|    |5..|...|672|
  |...|...|...|    |...|...|536|    |...|...|134|
  |123|456|789|    |...|...|471|    |...|...|895|
  +---+---+---+    +---+---+---+    +---+---+---+
  |812|547|963|    |...|981|623|    |...|9..|428|
  |674|293|518|    |...|364|857|    |...|...|517|
  |539|861|274|    |...|572|914|    |...|...|963|
  +---+---+---+    +---+---+---+    +---+---+---+
  |756|938|421|    |123|456|789|    |123|456|789|
  |298|174|635|    |678|293|145|    |749|218|356|
  |341|625|897|    |495|817|362|    |658|379|241|
  +---+---+---+    +---+---+---+    +---+---+---+

4.Red Ed classically
showed that this pattern would always have an uncovered unavoidable set [UA].
The computation was made many times easier using the fact that the empty area had many planes of symmetry.

Code: Select all
  +---+---+---+    +---+---+---+
  |xxx|xxx|xxx|    |...|..x|..x|
  |xxx|...|xxx|    |...|..x|..x|
  |xxx|...|xxx|    |..x|..x|..x|
  +---+---+---+    +---+---+---+
  |x..|...|..x|    |...|xxx|xxx|
  |x..|.x.|..x| -> |...|xxx|xxx|
  |x..|...|..x|    |xxx|xxx|xxx|
  +---+---+---+    +---+---+---+
  |xxx|...|xxx|    |...|xxx|xxx|
  |xxx|...|xxx|    |...|xxx|xxx|
  |xxx|xxx|xxx|    |xxx|xxx|xxx|
  +---+---+---+    +---+---+---+   [morph]

a variation produced similarly is maximal......with no clue in central box
Code: Select all
  +---+---+---+    +---+---+---+
  |xxx|xxx|xxx|    |...|..x|.xx|
  |xxx|...|xxx|    |...|..x|.xx|
  |xxx|...|xxx|    |...|..x|.xx|
  +---+---+---+    +---+---+---+
  |x..|...|.xx|    |...|xxx|xxx|
  |x..|...|.xx| -> |...|xxx|xxx|
  |x..|...|.xx|    |xxx|xxx|xxx|
  +---+---+---+    +---+---+---+
  |xxx|...|xxx|    |...|xxx|xxx|
  |xxx|xxx|xxx|    |xxx|xxx|xxx|
  |xxx|xxx|xxx|    |xxx|xxx|xxx|
  +---+---+---+    +---+---+---+   [morph] 

3 clues in the 49 cells cant therefore give valid puzzles
Code: Select all
+---+---+---+   
|...|..x|.xx|         
|...|...|.xx|         
|...|...|.xx|         
+---+---+---+         
|...|...|.xx|         
|...|...|.xx|         
|x..|..x|.xx|         
+---+---+---+         
|...|...|.xx|         
|xxx|xxx|xxx|         
|xxx|xxx|xxx|         
+---+---+---+

4 clues in the 49 empty cells are can give valid puzzles

But these 2 ED ways can be shown to be invalid
Code: Select all
+---+---+---+   +---+---+---+
|x..|x..|.xx|   |x..|.x.|.xx|
|...|...|.xx|   |...|...|.xx|
|...|...|.xx|   |...|...|.xx|
+---+---+---+   +---+---+---+
|x..|x..|.xx|   |x..|x..|.xx|
|...|...|.xx|   |...|...|.xx|
|...|...|.xx|   |...|...|.xx|
+---+---+---+   +---+---+---+
|...|...|.xx|   |...|...|.xx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|
+---+---+---+   +---+---+---+ [blue]

here
And these 4 other ED ways can be shown to have valid puzzles [blue]
Code: Select all
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
|x..|.x.|.xx|   |x..|x..|.xx|   |x..|.x.|.xx|   |x..|...|.xx|
|...|...|.xx|   |...|...|.xx|   |...|...|.xx|   |...|.x.|.xx|
|...|...|.xx|   |...|...|.xx|   |...|...|.xx|   |...|...|.xx|
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
|...|x..|.xx|   |...|x..|.xx|   |.x.|x..|.xx|   |...|x..|.xx|
|x..|...|.xx|   |x..|...|.xx|   |...|...|.xx|   |.x.|...|.xx|
|...|...|.xx|   |...|...|.xx|   |...|...|.xx|   |...|...|.xx|
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+
|...|...|.xx|   |...|...|.xx|   |...|...|.xx|   |...|...|.xx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|   |xxx|xxx|xxx|   |xxx|xxx|xxx|
|xxx|xxx|xxx|   |xxx|xxx|xxx|   |xxx|xxx|xxx|   |xxx|xxx|xxx|
+---+---+---+   +---+---+---+   +---+---+---+   +---+---+---+

Finally blue also easily proved that a crossing pattern with 2 rows and 2 columns
was shown to always need more than one clue [always at 2 least UAs] and his methods gave rise to many other maximal patterns.
Code: Select all
+---+---+---+        +---+---+---+
|...|...|...|        |2..|...|...|
|.x.|...|...|        |.6.|...|...|
|..x|xxx|xxx|        |..4|861|792|
+---+---+---+        +---+---+---+
|..x|xxx|xxx|        |..9|123|846|
|..x|xxx|xxx|        |..2|456|379|
|..x|xxx|xxx|        |..6|789|215|
+---+---+---+        +---+---+---+
|..x|xxx|xxx|        |..1|937|528|
|..x|xxx|xxx|        |..3|548|167|
|..x|xxx|xxx|        |..5|612|934|
+---+---+---+        +---+---+---+ 

More to follow
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Thu Aug 15, 2013 8:59 pm

Here are the patterns which have been proven.
Code: Select all
Needs 1 clue      Needs 1 clue     
+---+---+---+     +---+---+---+                 
|...|...|...|     |...|...|xxx|                 
|...|...|...|     |...|...|xxx|                 
|xxx|xxx|xxx|     |...|...|xxx|                 
+---+---+---+     +---+---+---+                 
|xxx|xxx|xxx|     |...|xxx|xxx|                 
|xxx|xxx|xxx|     |...|xxx|xxx|                 
|xxx|xxx|xxx|     |...|xxx|xxx|                 
+---+---+---+     +---+---+---+                 
|xxx|xxx|xxx|     |xxx|xxx|xxx|                 
|xxx|xxx|xxx|     |xxx|xxx|xxx|                 
|xxx|xxx|xxx|     |xxx|xxx|xxx|                 
+---+---+---+     +---+---+---+ 
   

These patterns needs at least 2 clues added                 
+---+---+---+     +---+---+---+      +---+---+---+
|...|...|...|     |...|...|...|      |...|...|xxx|
|...|...|...|     |...|...|...|      |...|...|xxx|
|...|...|...|     |..x|xxx|xxx|      |...|...|xxx|
+---+---+---+     +---+---+---+      +---+---+---+
|xxx|xxx|xxx|     |..x|xxx|xxx|      |...|...|xxx|
|xxx|xxx|xxx|     |..x|xxx|xxx|      |...|...|xxx|
|xxx|xxx|xxx|     |..x|xxx|xxx|      |...|...|xxx|
+---+---+---+     +---+---+---+      +---+---+---+
|xxx|xxx|xxx|     |..x|xxx|xxx|      |xxx|xxx|xxx|
|xxx|xxx|xxx|     |..x|xxx|xxx|      |xxx|xxx|xxx|
|xxx|xxx|xxx|     |..x|xxx|xxx|      |xxx|xxx|xxx|
+---+---+---+     +---+---+---+      +---+---+---+

Needs at least 4 clues       
+---+---+---+                 
|...|...|.xx|                 
|...|...|.xx|                 
|...|...|.xx|                 
+---+---+---+                 
|...|...|.xx|                 
|...|...|.xx|                 
|...|...|.xx|                 
+---+---+---+                 
|...|...|.xx|                 
|xxx|xxx|xxx|                 
|xxx|xxx|xxx|                 
+---+---+---+                 
                             
Needs 5 clues... but         
If no empty box needs 6 clues
If empty box 1 needs 7 clues 
+---+---+---+                 
|...|...|...|                 
|...|...|...|                 
|...|...|...|                 
+---+---+---+                 
|...|xxx|xxx|                 
|...|xxx|xxx|                 
|...|xxx|xxx|                 
+---+---+---+                 
|...|xxx|xxx|                 
|...|xxx|xxx|                 
|...|xxx|xxx|                 
+---+---+---+                 
                             
Needs 7 clues                 
+---+---+---+                 
|...|...|...|                 
|...|...|...|                 
|...|...|...|                 
+---+---+---+                 
|...|...|...|                 
|...|...|...|                 
|...|...|...|                 
+---+---+---+                 
|xxx|xxx|xxx|                 
|xxx|xxx|xxx|                 
|xxx|xxx|xxx|                 
+---+---+---+                 
Last edited by coloin on Mon Feb 29, 2016 2:15 pm, edited 2 times in total.
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Thu Aug 15, 2013 9:03 pm

And these are ? unproven patterns with n clues to be added - in order of possible ease !
Probably they are all correct ! Apologies if they have indeed been proven in former posts.....

The fact that we havnt got proof probably means that it is not an easy task !

Code: Select all
Adding 2 clues is never enough ?

 1+---+---+---+    2+---+---+---+     
  |xxx|xxx|xxx|     |...|...|xxx|     
  |x..|...|..x|     |...|...|xxx|     
  |x..|...|..x|     |...|...|xxx|     
  +---+---+---+     +---+---+---+     
  |x..|...|..x|     |...|xxx|...|     
  |x..|...|..x|     |...|xxx|...|     
  |x..|...|..x|     |...|xxx|...|     
  +---+---+---+     +---+---+---+     
  |x..|...|..x|     |xxx|...|...|     
  |x..|...|..x|     |xxx|...|...|     
  |xxx|xxx|xxx|     |xxx|...|...|     
  +---+---+---+     +---+---+---+ 

Code: Select all
Adding 3 clues is never enough ?
 
 3+---+---++---
  |...|...|...|
  |...|...|...|
  |...|...|...|
  +---+---+---+
  |...|xxx|...|
  |...|xxx|...|
  |...|xxx|...|
  +---+---+---+
  |xxx|xxx|xxx|
  |xxx|xxx|xxx|
  |xxx|xxx|xxx|
  +---+---+---+

Code: Select all
Adding 4 clues is never enough ? 
               
 4+---+---+---+    5+---+---+---+     6+---+---++---   
  |x..|...|..x|     |xxx|xxx|xxx|      |...|...|...|     
  |x..|...|..x|     |...|...|...|      |...|...|...|       
  |x..|...|..x|     |...|...|...|      |...|...|...|     
  +---+---+---+     +---+---+---+      +---+---+---+     
  |x..|...|..x|     |xxx|xxx|xxx|      |...|xxx|...|     
  |x..|...|..x|     |...|...|...|      |...|xxx|...|     
  |x..|...|..x|     |...|...|...|      |...|xxx|...|     
  +---+---+---+     +---+---+---+      +---+---+---+   
  |x..|...|..x|     |...|...|...|      |xxx|...|xxx|   
  |x..|...|..x|     |...|...|...|      |xxx|...|xxx|       
  |xxx|xxx|xxx|     |xxx|xxx|xxx|      |xxx|...|xxx|     
  +---+---+---+     +---+---+---+      +---+---++---     

Code: Select all
Adding 5 clues is never enough ?
 
7+---+---+---+
 |...|...|...| 
 |...|...|...| 
 |...|...|...| 
 +---+---+---+ 
 |...|...|xxx| 
 |...|...|xxx| 
 |...|...|xxx| 
 +---+---+---+ 
 |...|xxx|xxx| 
 |...|xxx|xxx| 
 |...|xxx|xxx| 
 +---+---+---+ 
 

Code: Select all
Adding 6 clues is never enough ?
 
9+---+---+---+
 |...|...|..x|
 |...|...|..x|
 |...|...|..x|
 +---+---+---+
 |...|...|..x|
 |...|...|..x|
 |...|...|..x|
 +---+---+---+
 |...|...|xxx|
 |...|...|xxx|
 |xxx|xxx|xxx|
 +---+---+---+
 


Code: Select all
Adding 7 clues is never enough ?                                                                           
                                                                                                                 
10+---+---+---+      11+---+---+---+                                                                             
  |xxx|xxx|xxx|        |xxx|...|...|                                                                             
  |...|...|...|        |xxx|...|...|                                                                             
  |...|...|...|        |xxx|...|...|                                                                             
  +---+---+---+        +---+---+---+                                                                             
  |...|...|...|        |...|xxx|...|                                                                             
  |...|...|...|        |...|xxx|...|                                                                             
  |...|...|...|        |...|xxx|...|                                                                             
  +---+---+---+        +---+---+---+                                                                             
  |...|...|...|        |...|...|...|                                                                             
  |...|...|...|        |...|...|...|                                                                             
  |xxx|xxx|xxx|        |...|...|...|                                                                             
  +---+---+---+        +---+---+---+


Code: Select all
Adding 8 clues is never enough ?                                                                           
                                                                                                                 
 12+---+---+---+                        13+---+---++---                                                           
   |...|...|..x|                          |...|...|...|                                                           
   |...|...|..x|                          |...|...|...|                                                           
   |...|...|..x|                          |...|...|...|                                                           
   +---+---+---+                          +---+---+---+                                                           
   |...|...|..x|                          |...|...|...|                                                           
   |...|...|..x|                          |...|...|...|                                                           
   |...|...|..x|                          |...|...|...|                                                           
   +---+---+---+                          +---+---+---+                                                           
   |...|...|..x|                          |...|...|xxx|                                                           
   |...|...|..x|                          |...|...|xxx|                                                           
   |xxx|xxx|xxx|                          |xxx|xxx|xxx|                                                           
   +---+---+---+  > 70000 9plus17s        +---+---+---+   only 4 9plus15s of this pattern have been found.


Code: Select all
Adding 11 clues is never enough ?

14+---+---+---+   15+---+---+---+
  |...|...|...|     |xxx|xxx|xxx|
  |...|...|...|     |...|...|...|
  |...|...|...|     |...|...|...|
  +---+---+---+     +---+---+---+
  |...|xxx|...|     |...|...|...|
  |...|xxx|...|     |...|...|...|
  |...|xxx|...|     |...|...|...|
  +---+---+---+     +---+---+---+
  |...|...|...|     |...|...|...|
  |...|...|...|     |...|...|...|
  |...|...|...|     |...|...|...|
  +---+---+---+     +---+---+---+    only 9plus12s have been found - see 9plus12 game

C
Last edited by coloin on Wed Sep 21, 2016 8:53 pm, edited 9 times in total.
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Thu Aug 15, 2013 9:25 pm

Actually on reading eleven's post here where he proved that the map

Code: Select all
111
112
999
does not have valid puzzle
On furthur thinking ......EDIT
also
Code: Select all
011
299
999
does not have a valid puzzle

But before we can say
Code: Select all
 9+---+---+---+   
  |...|...|...|   
  |...|...|...|     
  |...|...|...|     
  +---+---+---+     
  |...|...|...|     
  |...|...|...|     
  |...|...|...|     
  +---+---+---+     
  |xxx|xxx|xxx|     
  |xxx|xxx|xxx|     
  |xxx|xxx|xxx|     
  +---+---+---+   Adding 7 clues will not give a valid puzzle - EDIt - a few and actually all of the possible 27plus7 puzzles have actually been found

i reckon one would actually need to prove
EDIT rather a lot more than i have shown here .......see later post !
Code: Select all
012   012   012   022   013   004
211   121   112   111   111   111
999   999   999   999   999   999

C
Last edited by coloin on Thu Nov 19, 2015 11:53 pm, edited 3 times in total.
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby Serg » Fri Aug 16, 2013 4:03 pm

Hi, coloin!
You consider rather interesting classes of patterns, but, I think, proof of these conjectures would have limited practical usage. For example, knowlege of all maximal patterns having 2 free bands (the 3rd band must consist of boxes containing 9 clues each; I think there should be several hundreds of such patterns) will be (I think) much more effective than rule "Each 2 bands of any valid puzzle must contain more 7 clues". (Maybe you remember my experiment in filtering out 18-clue vertically symmetric patterns - your rule considered (if it could be proven) could exclude about 7300 patterns from 200000 only.)

Anyway, it would be interesting to study your conjectures. Unfortunately I cannot see any smart way to do such search, but instead - a huge amount of patterns that must be analysed. Maybe someone can propose shorter way of proving your conjectures. I'll ponder methods of doing that.

I'll be out of Internet next week (on vacations), so I'll have possibility to reply to you posts in a week only.

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

Re: Ask for patterns that they dont have puzzles 2

Postby Serg » Sun Sep 29, 2013 5:26 am

Hi, coloin!
Here are a few simple consideration about your conjections:
- Coloin's rule 1 (not proven yet): any 2 bands (stacks) of valid sudoku puzzle must contain not less than 8 clues;
- Coloin's rule 2 (not proven yet): any 8 boxes of valid sudoku puzzle must contain not less than 12 clues.

If "Coloin's rule 1" is true, then any valid sudoku puzzle must have not less than 12 clues.

Proof.
Let's denote by S1, S2 and S3 sums of clues in B123, B456 and B789 bands. Suppose "Coloin's rule 1" is true. Then we'll have system of 3 inequalities:
1. S1 + S2 >= 8
2. S1 + S3 >= 8
3. S2 + S3 >= 8
Then we'll add all these inequalities and divide them by 2. We'll get inequality S1 + S2 + S3 >= 12. QED

In similar way it is possible to prove the statement: "If Coloin's rule 2 is true, then any valid sudoku puzzle must have not less than 14 clues".

Maybe both these observations are known to sudoku people. It is interesting - is it possible to prove opposite statements. For example, "If any valid sudoku puzzle has not less than 12 clues, then "Coloin's rule 1" is true"?

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

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Thu Oct 10, 2013 12:54 pm

Yes that logic is good ! - ut we are far from proving #9
i have omitted #15 which has been proven of course
Code: Select all
15+---+---+---+   
  |...|...|...|   
  |...|...|...|     
  |...|...|...|     
  +---+---+---+       
  |...|...|...|
  |...|...|...|   
  |...|...|...|     
  +---+---+---+     
  |...|...|...|     
  |...|...|...|     
  |...|...|...|     
  +---+---+---+ needs 17 clues


So...............
having proved part of #9 - these patterns dont have valid puzzles
Code: Select all
111
211
999

this is also invalid
Code: Select all
003
999
999

and these have 3 empty boxes - so are invalid
Code: Select all
011    012     012                                                                     
005    004     040                                                                     
999    999     999

which of these patterns has Serg already proved as invalid ?
Code: Select all
A.011   B.011   C.011   D.011   E.011   F.011   G.011   H.011   I.011   J.011   K.011               
  122     212     320     230     023     311     131     410     014     140     500               
  999     999     999     999     999     999     999     999     999     999     999               
                                                                                                     
                                                                                                     
L.012   M.012   N.012   O.012   P.012   Q.012   R.012   S.012   T.012   U.012   V.012   W.012   X.012
  211     121     112     130     310     301     103     031     013     400     220     202     022
  999     999     999     999     999     999     999     999     999     999     999     999     999
 

Rather more pattterns than I first thought !

C
Last edited by coloin on Fri Aug 29, 2014 12:09 am, edited 1 time in total.
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Fri Oct 11, 2013 1:08 am

Well ..... looking back eleven has confirmed that
Code: Select all
0 1 1                                 
2 2 9                                       
9 9 9
has no valid puzzles.

Therefore A,B,D,E,G,I and J are all invalid.

C
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby Serg » Sat Oct 12, 2013 6:11 pm

Hi, coloin!
Some words about patterns having 7 clues in 2 bands (stacks).
I have slightly different list of possible maps for patterns, potentially having valid puzzles.
I didn't include maps being subsets of these (evident) maps:
Code: Select all
003   009
999   099
999   999

Here is my list of 25 maps to be checked for having valid puzzles.
Code: Select all
M1    M2    M3    M4    M5    M6    M7    M8    M9    M10   M11   M12   M13

004   005   004   011   011   012   012   012   011   011   011   011   012
120   110   111   014   023   013   022   031   104   203   302   401   103
999   999   999   999   999   999   999   999   999   999   999   999   999


M14   M15   M16   M17   M18   M19   M20   M21   M22   M23   M24   M25   M26   M27   M28

012   012   011   011   011   011   012   012   012   013   022   111   013   021   021
202   301   113   122   212   311   112   121   211   111   111   112   201   301   202
999   999   999   999   999   999   999   999   999   999   999   999   999   999   999

What maps can be excluded by 40-patterns list? Analisys shows we can add 3 "exclusive" maps not having valid puzzles to cited above 2 maps evidently not having valid puzzles.
Code: Select all
N1   based on   P98

012     +-----+-----+-----+
099     |. . .|. . .|x x x|
999     |. . .|. . .|x x x|
        |. . .|. . .|x x x|
        +-----+-----+-----+
        |. . .|x x x|x x x|
        |. . .|x x x|x x x|
        |x x x|x x x|x x x|
        +-----+-----+-----+
        |. . .|x x x|x x x|
        |x x x|x x x|x x x|
        |x x x|x x x|x x x|
        +-----+-----+-----+


N2   based on   P110

011     +-----+-----+-----+
991     |. . .|. . x|x x x|
999     |. . .|. . x|x x x|
        |. . x|. . x|x x x|
        +-----+-----+-----+
        |. . .|x x x|x x x|
        |. . .|x x x|x x x|
        |. x .|x x x|x x x|
        +-----+-----+-----+
        |. . .|x x x|x x x|
        |. . .|x x x|x x x|
        |. . .|x x x|x x x|
        +-----+-----+-----+


N3   based on   P123

011     +-----+-----+-----+
299     |. . .|. x x|x x x|
999     |. . .|. x x|x x x|
        |. . .|. x x|x x x|
        +-----+-----+-----+
        |. . .|x x x|x x x|
        |. . .|x x x|x x x|
        |x x x|x x x|x x x|
        +-----+-----+-----+
        |. . .|x x x|x x x|
        |. . .|x x x|x x x|
        |x x x|x x x|x x x|
        +-----+-----+-----+

Applying these maps (N1-N3) enable us to exclude 14 maps from 25-map list. (I didn't use eleven's maps because they are not independenly comfirmed.) So, finally we have 14 maps to be checked. Here is list of maps, which potentially can have valid puzzles, with number of essentially different patterns for each map.
Code: Select all
Map Number of e-d patterns
M1  .....42
M3  .....64
M13 ....182
M14 ....258
M15 ....156
M20 ....454
M21 ....442
M22 ....390
M23 ....270
M24 ....236
M25 ....394
M26 ....162
M27 ....144
M28 ....234

Total: 3428

So, to prove "Coloin's rule 1 (any 2 bands (stacks) of valid puzzle must contain greater than 7 clues)", one should do exhaustive search in 3428 patterns.

Serg

[Edited. I missed 3 maps (thanks to coloin for his correction). Now 28-maps list is presented.]
[Edited2. I calculated number of e-d patterns for M26-M28 maps and increased properly total number of patterns to be checked. (Previously published number of patterns - 3062 - was wrong.)]
[Edited3. As coloin pointed, we can filtered out maps M2 and M11 by "exclusive" map N2 applying. I removed these maps from the list of maps potentially having valid puzzles and corrected total number of potentially valid patterns.]
Last edited by Serg on Tue Oct 15, 2013 3:53 pm, edited 3 times in total.
Serg
2017 Supporter
 
Posts: 496
Joined: 01 June 2010
Location: Russia

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Sat Oct 12, 2013 7:00 pm

Yes very good ......
And yes, always better to do a complete run on it.
still a lot of patterns and there is many ways to fill in even the bottom band !

however i seem to have more than you and i havent included the 4 patterns with

111
xxx
999

which adds up to 28 in total ?
i did mine by eye - so i could be in error, except

you dont have
Code: Select all
012
220
999

012
130
999

012
310
999


It may be easier with patterns with
Code: Select all
011
xxx
999

As this is band 29 and there are only a few ways [edit 9] to complete it with 2 clues
here

C
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby Serg » Sat Oct 12, 2013 8:49 pm

Hi, coloin!
coloin wrote:however i seem to have more than you and i havent included the 4 patterns with

111
xxx
999

which adds up to 28 in total ?

You are right. I missed 3 maps ("O", "P" and "V" in your list), but you missed my 4 maps (M3, M23, M24 and M25). So, it seems correct number of maps is 28. (I'll edit my post.)

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

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Mon Oct 14, 2013 7:10 pm

Looks like 28 maps
This maximal pattern gets rid of many
Code: Select all
       P110       
+-----+-----+-----+
|. . .|. . x|x x x|
|. . .|. . x|x x x|
|. . x|. . x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. x .|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. . .|x x x|x x x|
+-----+-----+-----+

including M2 and M11
:)

As the pattern
101
199
999 is invalid - which means there must always be 2 under the 1

giving
101
2?2
999
[P123] deems ? >2
so
101
222
999 is invalid [although in reality ? is probably is >/= 3]

The
011
0??
999 is covered in all circumstances with [P98]

So the 011 cases with 5 clues in the 2nd band are all invalid

C
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Tue Oct 15, 2013 12:51 am

So i think we have progressed to
Code: Select all
101
222
999
is invalid
here is a
Code: Select all
101
232
999
+---+---+---+
|5..|...|...|
|...|...|6..|
|...|...|...|
+---+---+---+
|.1.|..3|.4.|
|.7.|.4.|..5|
|...|2..|...|
+---+---+---+
|123|456|789|
|765|892|134|
|894|371|256|
+---+---+---+

C
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: Ask for patterns that they dont have puzzles 2

Postby Serg » Tue Oct 15, 2013 3:46 pm

Hi, coloin!
coloin wrote:Looks like 28 maps
This maximal pattern gets rid of many
Code: Select all
       P110       
+-----+-----+-----+
|. . .|. . x|x x x|
|. . .|. . x|x x x|
|. . x|. . x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. x .|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|. . .|x x x|x x x|
+-----+-----+-----+

including M2 and M11
:)

Good point! We must exclude M2 and M11 maps (I'll edit my post with numbers of patterns). I was not carefull enough, but this news is pleasant :). I couldn't find other maps to be excluded by this rule.
coloin wrote:As the pattern
101
199
999 is invalid - which means there must always be 2 under the 1

giving
101
2?2
999
[P123] deems ? >2
so
101
222
999 is invalid [although in reality ? is probably is >/= 3]

The
011
0??
999 is covered in all circumstances with [P98]

So the 011 cases with 5 clues in the 2nd band are all invalid

I agree with your logic. If a map has band 011 (i.e. 1 empty box and 2 boxes containing exactly 1 clue each), then each remaining band must have 322 configuration, at least, to have valid puzzles. Hence any puzzle with band 011 must contain at least 9 clues in 2 bands or 16 clues in a puzzle to have valid puzzles.

I think we could go further if we could have list of possible patterns having 7 clues in 2 bands. Maximal patterns have higher exclusive potential than maps constructed on their bases. I think, we could obtain about 1000 possible patterns only if we would apply 40 maximal patterns to that list of potentially valid patterns. But I see another way of going forward in this direction. I hope in some time I'll be capable of studying "two-band-free" patterns. If it will be the case, we'll get exhaustive search results for possible patterns containing 7 clues in 2 bands.

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

Re: Ask for patterns that they dont have puzzles 2

Postby coloin » Sun Oct 20, 2013 10:08 pm

Well ..... i have been thinking too about how to proceed .....
On the adding the [3+4] clues to a band of 27.....
It struck me that one would "only" need to use one each of the 44 ganster representatives.
[The order of the 3 vertical clues in the band is academic]
i generated 1600 random [4+4+27]puzzles over the weekend.
I had hoped that maybe only a select few gangsterswould have puzzles - unfortunatly all but 3 of the 44 [1,40 & 44] had valid puzzles.

Anhow ..... probably i could add 5 clues to 5 boxes. addding 2 clues would complete the search.

I will see if that is possible with ganster 33 - it seemed to have a good few puzzles

C
coloin
 
Posts: 1539
Joined: 05 May 2005

Next

Return to General