The New Sudoku Players' Forum

[gsf]

sudoku: %O3#Bn: cannot read
sudoku: %3#An: cannot read
sudoku: %#bc': cannot read

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

[eleven]

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

[Red Ed]

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.

[Pat]

perhaps someone should try to prove there's no(?) 13-clue 2×4 sudoku puzzle

i suppose you've noticed that Afmob has been trying to find a 13 (no luck so far)

[Red Ed]

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

[dukuso]

but 2*4 sudoku doesn't look sooo interesting

[Red Ed]

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

[coloin]

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

[Red Ed]

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?

[coloin]

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

[Red Ed]

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]

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.

[ronk]

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

Those are patterns of blocks with clues.

[Red Ed]

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

[coloin]

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.