minimum number of clues per band/stack

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

minimum number of clues per band/stack

Postby champagne » Thu Oct 16, 2014 1:28 am

I don't know whether that question has already been answered.

It is clear that no valid pattern can have less than 2 clues in a band stack. Moreover, the 2 clues must be in different rows/columns.

But what is the minimum number of clues per band/ stack.

I checked the 17 clues file, we have several puzzles with 3 clues in a band stack.

Is it the minimum or do we have puzzles with 2 clues only in a band/stack.
champagne
2017 Supporter
 
Posts: 5576
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby dobrichev » Thu Oct 16, 2014 5:50 am

dobrichev
2016 Supporter
 
Posts: 1302
Joined: 24 May 2010

Re: minimum number of clues per band/stack

Postby Serg » Thu Oct 16, 2014 7:20 am

Hi, champagne!
See my post at February, 10 (2011) in the thread Investigation of one-band-free patterns with example of such "two-clue in a band" valid puzzle (but it contains 56 clues!).

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

Re: minimum number of clues per band/stack

Postby champagne » Thu Oct 16, 2014 7:32 am

Serg wrote:Hi, champagne!
See my post at February, 10 (2011) in the thread Investigation of one-band-free patterns with example of such "two-clue in a band" valid puzzle (but it contains 56 clues!).

Serg


This is more or less the kind of answer I expected.
BTW, do you have an idea of the percentage of solution grids where such examples can be found

I reproduce here below your example

Code: Select all
+-----+-----+-----+
|. . .|. . .|. . .|
|. . .|1 . .|. . .|
|7 . .|. . .|. . .|
+-----+-----+-----+
|2 1 4|3 5 6|7 8 9|
|3 6 5|8 9 7|2 1 4|
|8 9 7|2 1 4|3 6 5|
+-----+-----+-----+
|5 3 1|4 6 2|9 7 8|
|6 4 2|9 7 8|5 3 1|
|9 7 8|5 3 1|6 4 2|
+-----+-----+-----+



To mladen, I did not find such an example in your thread, and your proof is not so easy to digest.
Thanks for help.
champagne
2017 Supporter
 
Posts: 5576
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby coloin » Thu Oct 16, 2014 9:20 am

champagne wrote:BTW, do you have an idea of the percentage of solution grids where such examples can be found

a clever guess would be ~ 6/416
only one band allows 2 clues
there can be no 17-puzzles with 2 clues in a band.
all 18s have to be ... from work here

033
132
123
or
033
133
122

heres another one i just found
Code: Select all
+---+---+---+
|...|...|...|
|...|123|...|
|...|...|456|
+---+---+---+
|...|..6|...|
|...|.5.|..4|
|.8.|9..|.1.|
+---+---+---+
|...|...|9..|
|...|8..|.7.|
|4..|.6.|..3|
+---+---+---+

C
coloin
 
Posts: 1598
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby blue » Thu Oct 16, 2014 10:25 am

champagne wrote:BTW, do you have an idea of the percentage of solution grids where such examples can be found

It's just one canonical band type, that can have two clues in a valid puzzle -- #29 in dobrichev's table.

Code: Select all
1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 2 3 1
7 8 9 | 2 3 1 | 5 6 4

The clues can be in the any of the (9) "same letter" cell pairs below:

Code: Select all
a b c | d e f | g h i
. . . | . . . | . . .
d e f | g h i | b c a

The band has 18 automorphisms, and the 9 2-clue solutions, are related by isomorphism.
E.g. these two are isomorphic:

Code: Select all
. 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 2 3 1
7 8 9 | 2 3 1 | 5 6 .

1 2 3 | . 5 6 | 7 8 9
4 5 6 | 7 8 9 | 2 3 1
. 8 9 | 2 3 1 | 5 6 4

The band occurs one or more times, in 5498768 solution grids (of 5472730538), or about one in 995.

For grids with known 17's, it's in about one in 165.
One of those has 8 17's, and another has 6. Most have only one.
Just one 17-grid has the band appearing twice. (It has only one 17).
It's band 1 and stack 2, in the solution to this puzzle:

Code: Select all
. . 3 | 4 5 . | . . .
. . . | . . . | 2 . .
. . . | . . . | . 6 .
------+-------+------
. 1 4 | 3 . . | . . .
. . . | . 6 . | . 9 .
. . 8 | . . 2 | . . .
------+-------+------
. . . | . . . | . . 5
6 . . | . 7 . | . . .
. . . | . . . | 4 . 3

Oddly enough, (3r1c3, 6r3c8) and (3r4c4, 7r8c5) are part of the puzzle, and they're both valid clue pairs for thier bands.
Added: I missed 3rd pair ... (4r1c4, 6r5c5)
Last edited by blue on Thu Oct 16, 2014 4:35 pm, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby champagne » Thu Oct 16, 2014 12:15 pm

blue wrote:
champagne wrote:BTW, do you have an idea of the percentage of solution grids where such examples can be found

It's just one canonical band type, that can have two clues in a valid puzzle -- #29 in dobrichev's table.
...
...


impressive, I suspected that some investigations had been done, but not that deep.
champagne
2017 Supporter
 
Posts: 5576
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby Serg » Thu Oct 16, 2014 12:17 pm

coloin wrote:heres another one i just found
Code: Select all
+---+---+---+
|...|...|...|
|...|123|...|
|...|...|456|
+---+---+---+
|...|..6|...|
|...|.5.|..4|
|.8.|9..|.1.|
+---+---+---+
|...|...|9..|
|...|8..|.7.|
|4..|.6.|..3|
+---+---+---+

Nice example! You published great work in the thread Ask for patterns that they dont have puzzles 2. I'd like to say here, that first example of "2-clue in a band" puzzles (having the same pattern as my example, published by champagne) was coloin's example (at setbb.com).

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

Re: minimum number of clues per band/stack

Postby champagne » Thu Oct 16, 2014 1:02 pm

blue wrote:
For grids with known 17's, it's in about one in 165.
One of those has 8 17's, and another has 6. Most have only one.
Just one 17-grid has the band appearing twice. (It has only one 17).
It's band 1 and stack 2, in the solution to this puzzle:

Code: Select all
. . 3 | 4 5 . | . . .
. . . | . . . | 2 . .
. . . | . . . | . 6 .
------+-------+------
. 1 4 | 3 . . | . . .
. . . | . 6 . | . 9 .
. . 8 | . . 2 | . . .
------+-------+------
. . . | . . . | . . 5
6 . . | . 7 . | . . .
. . . | . . . | 4 . 3
.


Hi blue,

It's good to have an example to understand the wording.

in that example, the 17 clues pattern has no band with 2 clues.

(BTW this means that any 18 clues derived for that pattern has none either)

So my understanding is that the solution grid corresponding to that pattern has the property, but surely with minimum patterns of 18 clues or more.

I guess that you confirm coloin's assertion that no 17 clues pattern can have 2 clues in a band.
champagne
2017 Supporter
 
Posts: 5576
Joined: 02 August 2007
Location: France Brittany

Re: minimum number of clues per band/stack

Postby eleven » Thu Oct 16, 2014 2:03 pm

blue's post also shows an old result by Red Ed:
The other digit always must be in the same mini-line.
So in coloin's puzzle r6c3=4 and r9c3=8.
eleven
 
Posts: 1474
Joined: 10 February 2008

Re: minimum number of clues per band/stack

Postby blue » Thu Oct 16, 2014 4:44 pm

champagne wrote:I guess that you confirm coloin's assertion that no 17 clues pattern can have 2 clues in a band.

I can't, but I don't doubt it. This is Serg's area.

eleven wrote:blue's post also shows an old result by Red Ed:
The other digit always must be in the same mini-line.
So in coloin's puzzle r6c3=4 and r9c3=8.

It does ? [ Added: Yes it does ... re-visited below ]
Last edited by blue on Thu Oct 16, 2014 8:17 pm, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby coloin » Thu Oct 16, 2014 5:30 pm

Red Ed showed this little snippet - i cant recall the post however.

The assertion comes from the patterns which sergand blue confirmed didn't have puzzles,

C
Last edited by coloin on Thu Oct 16, 2014 5:35 pm, edited 1 time in total.
coloin
 
Posts: 1598
Joined: 05 May 2005

Re: minimum number of clues per band/stack

Postby Serg » Thu Oct 16, 2014 5:35 pm

Hi, people!
coloin published in the thread Ask for patterns that they dont have puzzles 2 two valuable results.

1. coloin proved, that any valid 17-clue puzzle must have more than 2 clues in a band (stack).
2. coloin published examples of 18-clue puzzles containing 2 clues in a band (stack).

I confirm correctness of his proof of the statement "any valid 17-clue puzzle must have more than 2 clues in a band (stack)". This proof was too brief to my mind, so I decided to repeat his proof more detailed to simplify the verification of this proof.

coloin's proof was based on 40-patterns list of maximal patterns, published (May 26, 2013) in the thread Investigation of one-crossing-free patterns.

Step 1
Code: Select all
        p123
+-----+-----+-----+
|. . .|. x x|x x x|
|. . .|. x x|x x x|
|. . .|. x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+
|. . .|x x x|x x x|
|. . .|x x x|x x x|
|x x x|x x x|x x x|
+-----+-----+-----+

This maximal pattern says, if a pattern has empty box B1, box B2 containing 2 clues and boxes B4 and B7 containing 1 clue each, i.e. pattern has map
Code: Select all
0 2 9
1 9 9
1 9 9

such pattern has no valid puzzles, because it can be morphed to subset of the pattern p123. So, if we consider configurations with empty B1 box and boxes B4 and B7 containing 1 clue each, box B2 of valid puzzle must contain at least 3 clues. Box B3 of valid puzzle must contain at least 3 clues too, because in case it would contain 2 clues, it could be transformed to map's
Code: Select all
0 2 9
1 9 9
1 9 9

subset.
So, if any valid puzzle has empty B1 box and boxes B4 and B7 containing 1 clue each, then B2 and B3 boxes of this puzzle must contain at least 3 clues each to provide validity of the puzzle (it is necessary, but not sufficient condition).

Step 2
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|
+-----+-----+-----+

This maximal pattern says, if a pattern has empty box B1 and boxes B4, B5 and B7 containing 1 clue each, i.e. pattern has map
Code: Select all
0 9 9
1 1 9
1 9 9

such pattern has no valid puzzles, because it can be morphed to subset of the pattern p110 (you should swap bands B123 --> B789 --> B456 --> B123 of this map to get subset of pattern P110). So, if we consider configurations with empty B1 box and boxes B4 and B7 containing 1 clue each, box B5 of valid puzzle must contain at least 2 clues. Boxes B6, B8 and B9 of valid puzzle must contain at least 2 clues too, because in case it would contain 1 clue, it could be transformed to map's
Code: Select all
0 9 9
1 1 9
1 9 9

subset.
So, if any valid puzzle has empty B1 box and boxes B4 and B7 containing 1 clue each, then B5, B6, B8 and B9 boxes of this puzzle must contain at least 2 clues each to provide validity of the puzzle.

Step 3
Code: Select all
        P114             
 +-----+-----+-----+     
 |. . .|. x x|. x x|     
 |. . .|. x x|. x x|     
 |. . x|. x x|. x x|     
 +-----+-----+-----+     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 |. x .|x x x|x x x|     
 +-----+-----+-----+     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 +-----+-----+-----+

This maximal pattern says, if a pattern has empty box B1 and boxes B4 and B7 containing 1 clue each, i.e. pattern has map
Code: Select all
0 9 9
1 2 2
1 9 9

such pattern has no valid puzzles, because it can be morphed to subset of the pattern p114 (you should swap bands B123 --> B456 --> B789 --> B123 of this map to get subset of pattern P114). So, if we consider configurations with empty B1 box and boxes B4 and B7 containing 1 clue each, box B5 or box B6 of valid puzzle must contain at least 3 clues. In the same way we can state that box B8 or box B9 of valid puzzle with empty B1 box and boxes B4 and B7 containing 1 clue each, must contain at least 3 clues.

So, if any valid puzzle has empty B1 box and boxes B4 and B7 containing 1 clue each, box B5 or box B6 and box B8 or box B9 of valid puzzle must contain at least 3 clues to provide validity of the puzzle.

Step 4 (summary)
If any valid puzzle has empty B1 box and boxes B4 and B7 containing 1 clue each, then its boxes B2 and B3 must contain at least 3 clues each, boxes B5, B6, B8 and B9 must contain at least 2 clues each, box B5 or box B6 and box B8 or box B9 of valid puzzle must contain at least 3 clues. So, minimal possible number of clues for the valid puzzles having empty B1 box and boxes B4 and B7 containing 1 clue each can be shown by 2 possible maps:
Code: Select all
  M1     M2
0 3 3     0 3 3
1 2 3     1 2 3
1 3 2     1 2 3

As you can see any valid puzzle having empty B1 box and boxes B4 and B7 containing 1 clue each must contain at least 18 clues.

Step 5
If any valid puzzle has empty B4 and B7 boxes, then its box B1 must contain at least 3 clues not to be subset of pattern
Code: Select all
        P138             
 +-----+-----+-----+     
 |. . x|x x x|x x x|     
 |. . x|x x x|x x x|     
 |x x x|x x x|x x x|     
 +-----+-----+-----+     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 +-----+-----+-----+     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 |. . .|x x x|x x x|     
 +-----+-----+-----+

So, in this case (2 empty boxes ia band/stack) band/stack must contain more than 2 clues.

Step 6 (trivial)
Any valid puzzle having 3 non-empty boxes in a band/stack contain at least 3 clues in that band/stack.

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

Re: minimum number of clues per band/stack

Postby blue » Thu Oct 16, 2014 5:36 pm

blue wrote:
eleven wrote:blue's post also shows an old result by Red Ed:
The other digit always must be in the same mini-line.
So in coloin's puzzle r6c3=4 and r9c3=8.

It does ?

Ah, I see it now.

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 2 3 1
7 8 9 | 2 3 1 | 5 6 4

1 2 3 | 4 5 6 | 7 8 9
4 5 6 | 7 8 9 | 2 3 1
7 8 9 | 2 3 1 | 5 6 4

... etc.
blue
 
Posts: 573
Joined: 11 March 2013

Re: minimum number of clues per band/stack

Postby blue » Thu Oct 16, 2014 6:05 pm

Serg wrote:coloin published in the thread Ask for patterns that they dont have puzzles 2 two valuable results.

1. coloin proved, that any valid 17-clue puzzle must have more than 2 clues in a band (stack).
2. coloin published examples of 18-clue puzzles containing 2 clues in a band (stack).

I confirm correctness of his proof of the statement "any valid 17-clue puzzle must have more than 2 clues in a band (stack)". This proof was too brief to my mind, so I decided to repeat his proof more detailed to simplify the verification of this proof.

Well done, both of you !
blue
 
Posts: 573
Joined: 11 March 2013

Next

Return to General