A pattern that gives no valid sudoku puzzles

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

A pattern that gives no valid sudoku puzzles

Postby udosuk » Wed Jun 07, 2006 2:19 am

This might come as a shock to some, but any sudoku puzzle (non-X, vanilla) covered by the following 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 x | . . . | x x x
 x x x | x x x | x x x

... DOES NOT have a unique solution. If you don't believe it, take any random completed grid, empty part of the cells as the above mask, and feed it to a solver program (such as Simple Sudoku)... You'll find it might report 2 or 3, maybe more solutions, but NEVER will it be a valid (i.e. with 1 unique solution) puzzle...

So, anyone trying to generate valid puzzles with these patterns:
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 | . . .

... FORGET IT! Mission impossible...

And kudos to anybody who could write a complete proof to this...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby keith » Wed Jun 07, 2006 2:54 am

udosuk,

A very provocative post! I presume you also exclude all subsets, such as this one:
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

which I saw posted a couple of days ago.

Keith
Last edited by keith on Wed Jun 07, 2006 6:30 am, edited 1 time in total.
keith
2017 Supporter
 
Posts: 221
Joined: 03 April 2006

Postby daj95376 » Wed Jun 07, 2006 3:50 am

udosuk,

Toss my first reply. There was something that I misunderstood!

Obviously, JPF has a more thorough understanding than both of us combined!
Last edited by daj95376 on Wed Jun 07, 2006 3:31 am, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby udosuk » Wed Jun 07, 2006 4:48 am

daj95376 wrote:Of course! All of these examples have rows/columns that can be exchanged within a chute without changing the template. So, any attempt at solving them will result in multiple solutions.

Excuse me... It isn't that obvious to me... I'm sure it's my own thickness but could you elaborate more please...

For example, how to exchange rows/columns on this one:
Code: Select all
918|765|432
764|...|519
532|...|876
---+---+---
156|...|784
493|.8.|265
827|...|391
---+---+---
641|...|923
385|...|147
279|341|658


As opposed to the following, which has a unique solution:
Code: Select all
.71|345|68.
4..|...|..7
6..|...|..3
---+---+---
9..|...|..6
.2.|...|.7.
7..|...|..4
---+---+---
1..|...|..5
3..|.6.|..8
.46|7.8|31.


Thanks!:!:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Wed Jun 07, 2006 7:16 am

udosuk wrote:And kudos to anybody who could write a complete proof to this...

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


has one and only one solution
Code: Select all
 1 9 8 | 2 7 5 | 3 4 6
 4 2 6 | 3 1 8 | 5 9 7
 3 5 7 | 9 4 6 | 8 1 2
-------+-------+-------
 6 4 3 | 5 9 2 | 7 8 1
 2 8 9 | 1 6 7 | 4 3 5
 7 1 5 | 4 8 3 | 6 2 9
-------+-------+-------
 5 3 1 | 6 2 4 | 9 7 8
 8 6 2 | 7 3 9 | 1 5 4
 9 7 4 | 8 5 1 | 2 6 3



*edit*, or even better :
Code: Select all

 . . . | 2 8 5 | . . .
 . . 4 | . . . | 2 . .
 . 6 . | . . . | . 3 .
-------+-------+-------
 5 . 1 | . . . | . . 4
 3 . . | . 7 . | . . 8
 2 . . | . . . | . . 9
-------+-------+-------
 . 1 . | . . . | . 7 .
 . . 9 | . . . | 5 . .
 . . . | 3 1 2 | . . .



Where is the joke ?

JPF
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Wed Jun 07, 2006 12:15 pm

JPF wrote:Where is the joke ?

The joke's on me, entirely... For some reason I've mistaken today as the April Fool's day... Must be the effect of the Omen film...

Great... At the moment let's deal with:
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

&
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 x | x x x
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Wed Jun 07, 2006 3:06 pm

udosuk wrote:At the moment let's deal with...

There are 2^81=2.4x10^24 possible patterns* !

I don't know for the first one...

For the second pattern, here is one solution :

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


or its minimal little brother :

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



JPF

*(before symmetry, etc..)
JPF
2017 Supporter
 
Posts: 6122
Joined: 06 December 2005
Location: Paris, France

Postby udosuk » Wed Jun 07, 2006 7:36 pm

JPF, it seems you're truly a master in this! Great work! And best of luck in cracking through this pattern...:)
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
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby fermat » Fri Jun 09, 2006 11:22 pm

I am guessing no one has, I cannot. I tried it by hand, a few grids.
I let Micheal Kennett's program run for 10 hours, to no effect.

So, I am thinking that there may be no solution or
that Micheal's test stutters on some patterns.

Has anyone tried a different template solver/builder to test this pattern?
fermat
 
Posts: 105
Joined: 29 March 2006


Return to General