## Structures of the solution grid

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

### Re: Structures of the solution grid

that's a quoting issue between you and your os
I posted unix compatible quoting
maybe " instead of ' ?
or you can use %, for space (added for cases like this)
Code: Select all
`-f%v%,#%,%03#Bn%,%3#An%,%#Bc`
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

### Re: Structures of the solution grid

Concerning the low clues again, i really dont mind, if there are 100 or 500 17's not found yet. So if it would really be feasible to compute all the possible 6/3 rookery combinations for them, i would be much more interested in a proof, that there is no 16 clue - with much less effort.

Searching for rookeries, i found, that his is not a very new idea, see this post
eleven

Posts: 2077
Joined: 10 February 2008

### Re: Structures of the solution grid

Still on the subject of rookeries/templates/etc. ... perhaps someone should try to prove there's no(?) 13-clue 2Ã—4 sudoku puzzle. It would be a relatively convenient means of testing and refining "rookery" methods.

Let me make up some terminology. This is a (1,2,2)-scaffold:
Code: Select all
`. . 2 #|. . . #. # . .|. # . #-------+-------. . . 1|# . 2 .# . . #|. # . .-------+-------. # . .|# . # .# . # .|. . 3 .-------+-------# # # .|. . . .. . . .|# 3 . #`
In general a (c(1),c(2),..,c(k))-scaffold consists of 8k cells, c(1) of which contain the digit 1 and so on up to c(k) containing the digit k, while the remaining 8k-c(1)-c(2)-...-c(k) cells are blank ('#'); and the given digits are sufficient to 'solve' the whole 8k cell structure (i.e. there's only one way to place the other 8-c(1) 1's up to 8-c(k) k's). This is somewhat similar to what Wolfgang was proposing with his 'subpuzzles'.

Now suppose there was 13-clue puzzle. Then up to isomorphism it is a scaffold of one of these types:
• (0,1,1,1,1,1,1,7)
• (0,1,1,1,1,1,2,6)
• (0,1,1,1,1,1,3,5)
• (0,1,1,1,1,1,4,4)
• (0,1,1,1,1,2,2,5)
• (0,1,1,1,1,2,3,4)
• (0,1,1,1,1,3,3,3)
• (0,1,1,1,2,2,2,4)
• (0,1,1,1,2,2,3,3)
• (0,1,1,2,2,2,2,3)
• (0,1,2,2,2,2,2,2)
• (1,1,1,2,2,2,2,2)
So you 'just' have to prove that none of those scaffold-types can exist. Here's one way to do that for, say, the (0,1,1,1,1,1,1,7)-scaffold:
• Write down all (0)-scaffolds up to isomorphism. There's only one.
• Extend that to all (0,1)-scaffolds up to isomorphism as follows. In as many ways as possible { add 8 '#' characters, one per row/col/box, and replace one of those '#' chars with the digit 2; if it's a new shape up to isomorphism and is 'solved' by its given digits, add it to the list of (0,1)-scaffolds }.
• Extend that to a list of all (0,1,1)-scaffolds up to isomorphism in a similar manner.
• Continue extending until we are forced to give up, e.g. by failing to extend from (0,1,1,1).
I've not tried it so have no idea if it's workable. I expect that it's not hard to cross off the first few scaffold-types from the list above; but the last few might require some cunning if they're to complete in reasonable time.
Red Ed

Posts: 633
Joined: 06 June 2005

Red Ed wrote:perhaps someone should try to prove there's no(?) 13-clue 2Ã—4 sudoku puzzle

Pat

Posts: 3796
Joined: 18 July 2005

### Re: Structures of the solution grid

Yes, I'd noticed. I would like to know how rookery methods compare with others (like Afmob's).
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Structures of the solution grid

but 2*4 sudoku doesn't look sooo interesting
dukuso

Posts: 479
Joined: 25 June 2005

### Re: Structures of the solution grid

Of course. But it's probably tractable, whereas it's not at all clear that ordinary sudoku should be.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Structures of the solution grid

Well we know for a fact that 7 clues of one number will never be minimal - so this can be removed at a stroke. [in 2*4 and 3*3]

In the 3*3 - I never was able to find a 19-puzzle with clues [********6] -and hence no 18 or 17 with this freq pattern.

It might be the case that there cant be found a 15-puzzle with [********6] in the 2*4

Having said all that - how much simpler is the 2-rookeries and 3-rookeries in the 2*4 ?

C
coloin

Posts: 1790
Joined: 05 May 2005

### Re: Structures of the solution grid

coloin wrote:Well we know for a fact that 7 clues of one number will never be minimal - so this can be removed at a stroke. [in 2*4 and 3*3]
How do we know that 7 clues of one number will never be minimal?
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Structures of the solution grid

With 7 clues you will always have a single which can be removed - leaving 6 clues.

In the 2*4 there is only one way to have 6 clues which is minimal

Showing clues in their block......

Code: Select all
`******--`

In the 3*3 - here are some ways
Code: Select all
`-***-***-`

Code: Select all
`---******`

Code: Select all
`**--**-**`

Other readers will see too that if you add another clue - it leaves another clue which will be superfluos

C
coloin

Posts: 1790
Joined: 05 May 2005

### Re: Structures of the solution grid

I don't see how any of that proves the assertion that there can't be seven 1s (to pick an arbitrary digit) in any minimal 2Ã—4 or 3Ã—3 sudoku puzzle.

I mean, patterns of clues in a block, what's that all about?
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Structures of the solution grid

Okay, I can prove by contradiction that no minimal 2Ã—4 sudoku puzzle can contain seven 1s.

Suppose to the contrary that it was possible. Then, without loss of generality, the seven 1s are in this position, with '#' indicating the position of the missing 1:
Code: Select all
`1 . . .|. . . .. . . .|1 . . .-------+-------. 1 . .|. . . .. . . .|. 1 . .-------+-------. . 1 .|. . . .. . . .|. . 1 .-------+-------. . . 1|. . . .. . . .|. . . #`
This is part of a minimal puzzle, so every clued 1 must be part of a minimal unavoidable that is not touched by the other clues. Further, since no minimal unavoidable can contain any singleton digits, each clued 1 must be in a minimal unavoidable shared with '#'.

In particular, there must be a minimal unavoidable in the puzzle incident with just these two 1s:
Code: Select all
`. . . .|. . . .. . . .|. . . .-------+-------. . . .|. . . .. . . .|. . . .-------+-------. . 1 .|. . . .. . . .|. . . .-------+-------. . . .|. . . .. . . .|. . . #`
But, hang on, no minimal unavoidable can have 1s in (only) that position!

Contradiction. Therefore there can't be seven 1s in any minimal 2Ã—4 sudoku puzzle.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Structures of the solution grid

Red Ed wrote:I mean, patterns of clues in a block, what's that all about?

Those are patterns of blocks with clues.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

### Re: Structures of the solution grid

ronk, okay, that would make more sense. But coloin's sequence of pictures is still not a proof.
Red Ed

Posts: 633
Joined: 06 June 2005

### Re: Structures of the solution grid

Red Ed wrote:ronk, okay, that would make more sense. But coloin's sequence of pictures is still not a proof.

There is essentially only one way to have 7 [out of 8] clues in a 2*4 - and it is non-minimal.

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

My sequence of diagrams showed 6 clues in a pattern which could be minimal. Other patterns of 6 clues are likely to be non-minimal - therefore need not be considered.
coloin

Posts: 1790
Joined: 05 May 2005

PreviousNext