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 gsf » Thu Jun 03, 2010 5:03 pm

dukuso wrote: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
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: Structures of the solution grid

Postby eleven » Fri Jun 04, 2010 3:48 pm

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: 3173
Joined: 10 February 2008

Re: Structures of the solution grid

Postby Red Ed » Sun Jun 06, 2010 9:42 pm

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

Postby Pat » Tue Jun 08, 2010 6:57 am

Red Ed wrote:perhaps someone should try to prove there's no(?) 13-clue 2×4 sudoku puzzle
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re: Structures of the solution grid

Postby Red Ed » Tue Jun 08, 2010 7:26 am

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

Postby dukuso » Tue Jun 08, 2010 7:50 am

but 2*4 sudoku doesn't look sooo interesting
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: Structures of the solution grid

Postby Red Ed » Tue Jun 08, 2010 4:03 pm

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

Postby coloin » Tue Jun 08, 2010 9:45 pm

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: 2502
Joined: 05 May 2005
Location: Devon

Re: Structures of the solution grid

Postby Red Ed » Fri Jun 11, 2010 6:55 am

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

Postby coloin » Fri Jun 11, 2010 11:03 am

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: 2502
Joined: 05 May 2005
Location: Devon

Re: Structures of the solution grid

Postby Red Ed » Fri Jun 11, 2010 3:47 pm

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

Postby Red Ed » Fri Jun 11, 2010 4:32 pm

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

Postby ronk » Fri Jun 11, 2010 4:37 pm

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

Postby Red Ed » Fri Jun 11, 2010 4:43 pm

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

Postby coloin » Sun Jun 13, 2010 11:01 pm

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: 2502
Joined: 05 May 2005
Location: Devon

PreviousNext

Return to General