The New Sudoku Players' Forum

by **JPF** » Wed May 31, 2006 11:44 pm

This one is ok with the rule, but is only 16 :

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

JPF

by **udosuk** » Fri Jun 02, 2006 7:06 pm

Could anyone show me why the following configuration cannot yield a valid non-X sudoku puzzle: :?:

Code: Select all: 0 0 0 0 0 0 0 0 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 0 0 0 0 0 0 0 0

by **tso** » Sat Jun 03, 2006 12:13 am

udosuk wrote:Could anyone show me why the following configuration cannot yield a valid non-X sudoku puzzle:

Code: Select all
0 0 0 0 0 0 0 0 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 . . . . . . . 0 0 0 0 0 0 0 0 0 0

I can't give a proof, but see if this makes sense:

Only the 12 edge cells marked with 'a' (of the 34 on the perimeter) can have a direct effect on placement of cells marked 'b' in the center box:

Code: Select all: . . . | a a a | . . . . . . | . . . | . . . . . . | . . . | . . . ------+-------+------ a . . | b b b | . . a a . . | b b b | . . a a . . | b b b | . . a ------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | a a a | . . .

At least four 1's in these 12 edge cells are required to place a '1' in the center, for example:

Code: Select all: . . . | 1 . . | . . . . . . | . . . | . . . . . . | . . . | . . . ------+-------+------ 1 . . | . . . | . . . . . . | . . . | . . 1 . . . | . .(1)| . . . ------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | . 1 . | . . .

At least three 2's in the remaining 8 edge cells are needed to place a '2' in the center, for example:

Code: Select all: . . . | 1 2 . | . . . . . . | . . . | . . . . . . | . . . | . . . ------+-------+------ 1 . . | . . . | . . 2 . . . | . .(2)| . . 1 . . . | . . 1 | . . . ------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | 2 1 . | . . .

Those remaining 5 edge cell won't give you enough information to force another placement in the center box:

Code: Select all: . . . | 1 2 . | . . . . . . | . . . | . . . . . . | . . . | . . . ------+-------+------ 1 . . |(3 3). | . . 2 3 . . | . . 2 | . . 1 . . . | . . 1 | . . 3 ------+-------+------ . . . | . . . | . . . . . . | . . . | . . . . . . | 2 1 3 | . . .

The other twenty perimeter cells cannot help even if we use them all at once:

Code: Select all: 3 3 3 | 1 2 . | 3 3 3 3 . . | . . . | . . 3 3 . . | . . . | . . 3 ------+-------+------ 1 . . |(3 3). | . . 2 3 . . | . . 2 | . . 1 . . . | . . 1 | . . 3 ------+-------+------ 3 . . | . . . | . . 3 3 . . | . . . | . . 3 3 3 3 | 2 1 3 | 3 3 3

by **udosuk** » Sun Jun 04, 2006 7:54 am

tso, call me thick but I can't see how your description works... Consider your own example:

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

If your method works then we could determine at least 1 cell in the middle block by the following 12 cells:

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

I couldn't see how... :?:

by **tso** » Sun Jun 04, 2006 3:25 pm

udosuk wrote:
If your method works then we could determine at least 1 cell in the middle block by the following 12 cells:

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

I couldn't see how...

That would depend on what digits are in those cells:

Code: Select all: +-------+-------+-------+ | . . . | 1 2 . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | +-------+-------+-------+ | . 1 . | . . . | . . 2 | | 3 . . | . . . | . . 1 | | . . . | . . . | . 3 . | +-------+-------+-------+ | . . . | . . . | . . . | | . . . | 2 . . | . . . | | . . . | . 1 3 | . . . | +-------+-------+-------+

Hidden singles at r56c6.

But I don't know what you are getting at.

by **udosuk** » Sun Jun 04, 2006 3:45 pm

I mean, if your proposition doesn't work on a certain valid sudoku puzzle (the one you posted yourself), how could you rule out a certain pattern that doesn't satisfy those conditions to have any chance of reaching a unique solution?

The example you made doen't match the particular sudoku puzzle I posted last time... Which shows that even the middle/central block doesn't have a cell determined by those 12 clues there exists some mechanism to eventually "force" out a unique solution, as brought out by the clues in the corner blocks...

by **tso** » Sun Jun 04, 2006 4:18 pm

udosuk wrote:I mean, if your proposition doesn't work on a certain valid sudoku puzzle (the one you posted yourself), how could you rule out a certain pattern that doesn't satisfy those conditions to have any chance of reaching a unique solution?

I don't know what proposition you are refering to. My claim is that there cannot be enough information contained in the perimeter clues to fill more than two cells in the center box. The valid Sudoku you posted has cells not on the perimeter. I don't understand the second have of your question.

udosuk wrote:The example you made doen't match the particular sudoku puzzle I posted last time... Which shows that even the middle/central block doesn't have a cell determined by those 12 clues there exists some mechanism to eventually "force" out a unique solution, as brought out by the clues in the corner blocks...

Red herring. The example has cells that are not on the perimeter.

Code: Select all: x x x | 1 2 . | x x x x x x | a a . | x x x x x x | a a . | x x x ------+-------+------ 1 . . |(3 3). | . . 2 3 . . | . . 2 | . . 1 . . . | . . 1 | . . 3 ------+-------+------ x x x | . . . | x x x x x x | . . . | x x x x x x | 2 1 3 | x x x

Consider the remaining cells marked 'a'. We know one of them is a three -- but the rest of the puzzle cannot give enough information to tell you if it goes in column 4 or column 5 -- even with all the cells marked 'x' filled.

I do not believe you can create a valid puzzle or even determine more than 2 of the central cells with this mask:

Code: Select all: 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

by **JPF** » Sun Jun 04, 2006 5:17 pm

I would basically agree with tso...
... at least on the conclusions.

I think that the only statement we can make is that,
for a pattern like this (12 clues) :

Code: Select all: . . . | a a a | . . . . . . | . . . | . . . . . . | . . . | . . . -------+-------+------- a . . | . . . | . . a a . . | . . . | . . a a . . | . . . | . . a -------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | a a a | . . .

The maximum number of computable (brute force or not) cells is 2.

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

In the same vein, the maximum number of computable cells for a full rectangle would be 5 :?:

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

udosuk wrote:The example you made doen't match the particular sudoku puzzle I posted last time... Which shows that even the middle/central block doesn't have a cell determined by those 12 clues there exists some mechanism to eventually "force" out a unique solution, as brought out by the clues in the corner blocks...

Which one are you referring to ?

JPF

by **udosuk** » Sun Jun 04, 2006 5:23 pm

tso wrote:
Code: Select all
x x x | 1 2 . | x x x x x x | a a . | x x x x x x | a a . | x x x ------+-------+------ 1 . . |(3 3). | . . 2 3 . . | . . 2 | . . 1 . . . | . . 1 | . . 3 ------+-------+------ x x x | . . . | x x x x x x | . . . | x x x x x x | 2 1 3 | x x x

Consider the remaining cells marked 'a'. We know one of them is a three -- but the rest of the puzzle cannot give enough information to tell you if it goes in column 4 or column 5 -- even with all the cells marked 'x' filled.

This is much better explanation... So we also need to focus on cells on the surrounding blocks, not only those within the central block. If you've elaborated it like that in the first place then there would be no confusion...

tso wrote:I do not believe you can create a valid puzzle or even determine more than 2 of the central cells with this mask:

Code: Select all
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

I recall there are puzzle designing blokes gunning for patterns like these:

Code: Select all: . . 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 . .

Code: Select all: . . . | x x x | . . . . . x | . . . | x . . . x . | . . . | . x . ------+-------+------ x . . | . . . | . . x x . . | . x . | . . x x . . | . . . | . . x ------+-------+------ . x . | . . . | . x . . . x | . . . | x . . . . . | x x x | . . .

Perhaps you could go one better and prove that the following mask also can't produce valid puzzles, and prevent them from trying the impossible...

Code: Select all: 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

Thanks tso for clarifying the matter eventually...

by **udosuk** » Sun Jun 04, 2006 5:32 pm

JPF wrote:
udosuk wrote:The example you made doen't match the particular sudoku puzzle I posted last time... Which shows that even the middle/central block doesn't have a cell determined by those 12 clues there exists some mechanism to eventually "force" out a unique solution, as brought out by the clues in the corner blocks...

Which one are you referring to ?

JPF, I was referring to this one:

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

When solving that puzzle most of the outside blocks are solved until the 1st cell in the central block is determined, which is generally true for all puzzles with similar patterns... That's why tso's approach of tackling the central block from the get-go looked "unnatural" to me... I did admit I was (and am) thick...

by **JPF** » Sun Jun 04, 2006 6:04 pm

udosuk wrote:I recall there are puzzle designing blokes gunning for patterns like these:
Code: Select all
. . 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 . .

Code: Select all
. . . | x x x | . . . . . x | . . . | x . . . x . | . . . | . x . ------+-------+------ x . . | . . . | . . x x . . | . x . | . . x x . . | . . . | . . x ------+-------+------ . x . | . . . | . x . . . x | . . . | x . . . . . | x x x | . . .

Perhaps you could go one better and prove that the following mask also can't produce valid puzzles, and prevent them from trying the impossible...

I'm one of them

here

I wrote:but stuck with those 2 patterns, unable to get a valid puzzle (each of those 2 examples has 2 solutions).
Code: Select all
. . . | 2 8 5 | . . . . . 4 | . . . | 2 . . . 6 . | . . . | . 3 . -------+-------+------- 5 . . | . . . | . . 4 3 . . | . 7 . | . . 8 2 . . | . . . | . . 9 -------+-------+------- . 1 . | . . . | . 7 . . . 9 | . . . | 5 . . . . . | 3 1 2 | . . .

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

Thanks in advance tso

JPF

by **tso** » Sun Jun 04, 2006 7:36 pm

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

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

Gee, unless we have reason to believe otherwise, I'd assume that if you can find a dual solution puzzle, that a unique solution puzzle with the same mask probably exists.

Of course, we can fix these two puzzles by combining them:

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

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

Cell 'a' is the same in both puzzles, as is cell 'b'.

[EDIT]

Better yet, replace the first puzzle with one with the digits transmuted:

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

Now all that's required for a unique solution is for 'x' to be the same in each puzzle.

by **JPF** » Sun Jun 04, 2006 8:32 pm

tso wrote:Gee, unless we have reason to believe otherwise, I'd assume that if you can find a dual solution puzzle, that a unique solution puzzle with the same mask probably exists.

unfortunately, this 16-clues pattern from gfroyle

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

has one 2-solutions puzzle, but no valid puzzle.

JPF

by **tso** » Sun Jun 04, 2006 9:37 pm

Well yes -- but I think we have to assume in the general case, with a mask greater than or equal to 17 cells, and at least 8 of the 9 digits are present, no two rows or columns intersecting with the same box empty, etc -- that given no other information, that if a dual solution can be found, it is more likely than not that a valid puzzle can be found.

by **JPF** » Fri Jun 30, 2006 10:06 pm

Here are 2 convex and symmetrical loops :

35 holes :

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

37 holes :

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

JPF

The New Sudoku Players' Forum

Largest 'hole' in a Sudoku; Largest 'emtpy space'