The New Sudoku Players' Forum

[ThemePark]

My interest in sudokus is mainly within the programming and not the solving, and so I'm in the process of making a program, part of which will use random sudokus.

Thus I've been wondering, if it is possible to determine if a certain pattern is valid for any particular order of numbers, without actually filling in the numbers but just using the information of which fields should have a number. Are there other rules for determining valid sudoku patterns besides checking if the number of filled fields is bigger than or equal to 17, or can all patterns that obey that rule, be valid?

[JPF]

Hi ThemePark,

Welcome to the Forum.

There are 2^81 =2417851639229258349412352 patterns

There are two questions in yours :

1. Are there any rules to say if a given pattern contains at least one valid puzzle or not.
My answer is no, except for some few cases :
Patterns with :

• 2 empty rows in a band
• 2 empty columns in a stack
• p empty boxes (p>=5) .
  When p=3 or 4, see here

In addition :
It is conjectured that pattens with n clues (n<=16) don’t have valid puzzles.

Note that if a pattern is not valid, then any pattern included in it is not valid either.

It's very hard to prove that a pattern is not valid.
See this thread and more precisely Red Ed's proof that the following pattern doesn't have any valid puzzle

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


2. To start in your programming process, you should not have any problem finding valid puzzles with patterns with 26 clues and more (for patterns following the previous rules).


JPF

[RW]

JPF, there was actually one more question: "is it possible to determine if a certain pattern is valid for any particular order of numbers". I think this should be easier to answer for those patterns that actually always are valid. This leads to the follow-up question that I don't think we have answered yet (correct me if I'm wrong):

What is the smallest possible pattern that will always give a valid puzzle? Alternatively: What is the largest possible pattern that cannot contain an unavoidable set?

Here's a modest start:

Code: Select all

*-----------*
|.XX|.XX|.XX|
|.XX|XXX|XXX|
|X.X|.XX|X.X|
|---+---+---|
|XXX|.XX|.X.|
|XX.|X.X|XXX|
|X.X|XX.|XXX|
|---+---+---|
|X.X|XXX|X.X|
|XX.|X.X|XXX|
|XXX|X.X|XX.|
*-----------*
61 cells

I believe this pattern should always give a unique puzzle...

[Edit] On second thought, this is a lot better:

Code: Select all

*-----------*
|...|...|...|
|...|XXX|XXX|
|...|XXX|XXX|
|---+---+---|
|.XX|.XX|XXX|
|.XX|XXX|.XX|
|.XX|XXX|XXX|
|---+---+---|
|.XX|XXX|X.X|
|.XX|X.X|XXX|
|.XX|XXX|XXX|
*-----------*
56 cells

RW

[JPF]

RW, good question.

I gave this 56 clues-pattern here :

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
 x x . | x x x | x . x


I'm not sure 56 clues is the minimum.

Edit :

This one has 48 clues and has 0 or 1 solution :

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 think we already discussed that before...

JPF

[RW]

Edit :

This one has 48 clues and has 0 or 1 solution :

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 think we already discussed that before...

JPF

Of course... Must have had a complete blackout, how could I miss that!

RW

[ThemePark]

...

Note that if a pattern is not valid, then any pattern included in it is not valid either.

...

That little goldnugget just made my programming a hundred times easier. I've never realized before that this would hold true.

My patterns are generated from a small set of boxes. As it turns out, all of my boxes are dependant on at least one other box, i.e. adding only or subtracting only will make one box look like another box, and this holds true for all my boxes. Hence I have been able to build a hierarchy out of them, and thus whenever I find a valid pattern, I can calculate a lot of other patterns by following my hierarchy.

So thanks JPF, you helped me a lot more than I had imagined.