Structures of the solution grid

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

Re: Structures of the solution grid

Postby ronk » Sun Jun 13, 2010 11:40 pm

coloin wrote:There is only 2 ways to have 7 [out of 9] clues in a 3*3 - and both of these are non minimal.

At least one clue could be removed so as to cause a hidden single, but is a hidden single sufficient to avoid a possible unavoidable set?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Structures of the solution grid

Postby Red Ed » Mon Jun 14, 2010 6:38 am

coloin, this is just another assertion with proof:
coloin wrote:There is only 2 ways to have 7 [out of 9] clues in a 3*3 - and both of these are non minimal.

But, okay, the penny's dropped. Let me spell out how to prove the statement for one of the two ways of putting down seven 1s in the 3x3 case:
Code: Select all
1 . .|. . .|. . .
. . .|1 . .|. . .
. . .|. . .|1 . .
-----+-----+-----
. 1 .|. . .|. . .
. . .|. 1 .|. . .
. . .|. . .|. 1 .
-----+-----+-----
. . 1|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .
The 1 at r4c2 is redundant because it's a hidden single in that box owing to eliminations by the 1s in boxes 1, 5, 6 and 7.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Structures of the solution grid

Postby coloin » Mon Jun 14, 2010 11:05 am

ronk wrote:
coloin wrote:There is only 2 ways to have 7 [out of 9] clues in a 3*3 - and both of these are non minimal.

At least one clue could be removed so as to cause a hidden single, but is a hidden single sufficient to avoid a possible unavoidable set?

Yes...i couldnt believe it either - so I checked - but of course it is true !
Code: Select all
1 . .|. . .|. . .
. . .|1 . .|. . .
. . .|. . .|. . 1
-----+-----+-----
. 1 .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . 1|. . .|. . .
The clues in blocks 234&7 include all the ununavoidable sets that r1c1 is in - which is why it can be removed when the puzzle is made and inserted when it is partially solved.
I cant find the post however - unique solution
In that list of unavoidable sets [with r1c1 [11]] there will always be r2c4,r3c9,r4c2,r9c3 [24,39,42,93]

Thanks Red Ed, the other 7/9 is
Code: Select all
. . .|. . .|. . .
. . .|1 . .|. . .
. . .|. . .|1 . .
-----+-----+-----
. 1 .|. . .|. . .
. . .|. 1 .|. . .
. . .|. . .|. 1 .
-----+-----+-----
. . 1|. . .|. . .
. . .|. . 1|. . .
. . .|. . .|. . .
the clue at r5c5 is dedundant

There are no minimal puzzles with more than 6 clues of one value.
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: Structures of the solution grid

Postby RW » Mon Jun 14, 2010 12:54 pm

coloin wrote:
ronk wrote:
coloin wrote:There is only 2 ways to have 7 [out of 9] clues in a 3*3 - and both of these are non minimal.

At least one clue could be removed so as to cause a hidden single, but is a hidden single sufficient to avoid a possible unavoidable set?

Yes...i couldnt believe it either - so I checked - but of course it is true !

...

There's an easier explanation as well. If you remove all clues from an unavoidable set, you get a deadly pattern. In a deadly pattern each candidate always appears at least twice in each row, column and box, no hidden singles.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Structures of the solution grid

Postby Red Ed » Mon Jun 14, 2010 5:09 pm

RW wrote:There's an easier explanation as well. If you remove all clues from an unavoidable set, you get a deadly pattern. In a deadly pattern each candidate always appears at least twice in each row, column and box, no hidden singles.

Noooo... too complicated. OK, my fault for introducing unavoidables into the discussion, having failed to notice the easy route. :wink: Surely the cleanest argument is just to observe that in the two 7-digit patterns you can always find a digit which, if removed, would be a hidden single in a box. Nice, direct and based entirely on first principles. I suppose that's what coloin's first pictures were hinting at.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Structures of the solution grid

Postby RW » Mon Jun 14, 2010 6:56 pm

Yes, I think that was what coloin meant with the pictures and that is the cleanest explanation to why we can't have 7 same digits in a minimal puzzle. I was just trying to answer ronk's question "is a hidden single sufficient to avoid a possible unavoidable set?"

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Structures of the solution grid

Postby Red Ed » Mon Jun 14, 2010 7:05 pm

I didn't quite understand ronk's question. Was it that the hidden single, with its clued counterparts of the same value, might not be sufficient to cover all unavoidables involving that digit? Or ... oh, doesn't matter.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Structures of the solution grid

Postby ronk » Mon Jun 14, 2010 7:32 pm

Red Ed wrote:I didn't quite understand ronk's question. Was it that the hidden single, with its clued counterparts of the same value, might not be sufficient to cover all unavoidables involving that digit? Or ... oh, doesn't matter.

As you said earlier, "the penny was dropped" about unavoidables. To pick up the penny, I asked a facetious question ... to which I was expecting a "UR1.1 style answer", which goes something like this: If a "uniqueness pattern" can be influenced by candidates outside the pattern, it's not a uniqueness pattern at all.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Structures of the solution grid

Postby Red Ed » Mon Jun 14, 2010 7:41 pm

ronk> To pick up the penny ...

<facetious>I thought I felt fingers scrabbling around my brain ... get out of there!</facetious> :shock:
Red Ed
 
Posts: 633
Joined: 06 June 2005

Re: Structures of the solution grid

Postby JPF » Tue Jun 15, 2010 4:16 am

Incidentally, that means that a minimal puzzle cannot have more than 54 clues.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Re: Structures of the solution grid

Postby eleven » Tue Jun 15, 2010 10:31 am

Trivially the minimum number of clues you need to solve a 3-rookery is 2 and the maximum without redundant clues 18.

You also can have both with the same 3-rookery, as this sample shows for 123.
Code: Select all
 +-------+-------+-------+
 | 1 5 8 | 4 2 6 | 7 3 9 |
 | 4 2 7 | 1 3 9 | 5 8 6 |
 | 6 9 3 | 8 7 5 | 4 1 2 |
 +-------+-------+-------+
 | 5 3 6 | 9 1 4 | 8 2 7 |
 | 7 1 2 | 3 5 8 | 6 9 4 |
 | 9 8 4 | 7 6 2 | 1 5 3 |
 +-------+-------+-------+
 | 8 7 1 | 6 9 3 | 2 4 5 |
 | 2 6 9 | 5 4 1 | 3 7 8 |
 | 3 4 5 | 2 8 7 | 9 6 1 |
 +-------+-------+-------+
 +-------+-------+-------+
 | . 5 . | . . 6 | 7 . . |
 | 4 . 7 | . . . | 5 . . |
 | . . . | 8 . . | . . . |
 +-------+-------+-------+
 | . . . | . . . | . . . |
 | . . . | 3 . 8 | 6 . . |
 | 9 . 4 | . . . | . . . |
 +-------+-------+-------+
 | 8 . . | . 9 . | . 4 . |
 | . 6 . | . . 1 | . . 8 |
 | . . 5 | . . 7 | . . . |
 +-------+-------+-------+
 +-------+-------+-------+
 | 1 5 8 | . 2 6 | 7 3 . |
 | . 2 7 | . 3 . | 5 . 6 |
 | 6 . 3 | . 7 . | . 1 2 |
 +-------+-------+-------+
 | 5 . . | . . 4 | . 2 . |
 | . 1 2 | . . . | 6 . . |
 | . . . | . 6 2 | 1 5 . |
 +-------+-------+-------+
 | . 7 1 | . 9 3 | . . 5 |
 | . . . | . . . | 3 7 . |
 | 3 . 5 | . . 7 | . . 1 |
 +-------+-------+-------+


In my sets of high clues i could not find a 6-rookery with 36 clues, just about 1000 with 35.
eleven
 
Posts: 1535
Joined: 10 February 2008

Re: Structures of the solution grid

Postby dukuso » Sat Jul 10, 2010 2:09 pm

I recalculated the number of 3-rookeries (isomorphism-classes) as : 92048
4-rookeriy-classes: less than 158.4M (if I have no bug, which is quite possible)
dukuso
 
Posts: 479
Joined: 25 June 2005

Previous

Return to General