Ask for some patterns that they don't have puzzles.

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

Ask for some patterns that they don't have puzzles.

Postby Eioru » Wed Apr 18, 2007 1:59 pm

Code: Select all
AAA...BBB
AAA...BBB
AAA*E*BBB
..*...*..
..E...E..
..*...*..
CCC*E*DDD
CCC...DDD
CCC...DDD


While ABCD have empty cells (>=3) that E can't use single (only remaining empty cell of the Column/Row) at first.
Also means Column 4 and 6 or Row 4 and 6 have empty cells.

like

Code: Select all
.*.....*.
*.*...*.*
.*.*.*.*.
..*...*..
.........
..*...*..
.*.*.*.*.
*.*...*.*
.*.....*.


Second adding.

which
Code: Select all
AAABBBCCC
AAABBBCCC
AAABBBCCC
DDDEEEFFF
DDDEEEFFF
DDDEEEFFF
GGGHHHIII
GGGHHHIII
GGGHHHIII

I know taht if the empty sets of
(ABC)(ACGI) are not exist, and
(AEH)(ABFI) are exist,
but (ABD)(ACEG)(ABDE) are unknown.
And if (BDEFH) are empty, how many clues at least shoud be added?
If the puzzle has been discussed , I would close it, or throw it to off-topic.
Last edited by Eioru on Wed Apr 18, 2007 11:43 am, edited 1 time in total.
Eioru
 
Posts: 182
Joined: 16 August 2006

Re: Ask for some patterns that they don't have puzzles.

Postby udosuk » Wed Apr 18, 2007 3:10 pm

Eioru wrote:If the puzzle has been discussed, I would close it, or throw it to off-topic.

It's been essentially discussed in here, but you don't need to close it or throw it to off-topic, since perhaps we can get some new discoveries with improved CPU power now...:idea:

Basically, we want to prove the following patterns/masks can't give valid puzzles:
Code: Select all
* * * | * * * | * * *
* * * | . . . | * * *
* * * | . . . | * * *
------+-------+------
* . . | . . . | . . *
* . . | . . . | . . *
* . . | . . . | . . *
------+-------+------
* * * | . . . | * * *
* * * | . . . | * * *
* * * | * * * | * * *

* * * | * * * | * * *
* * * | . . . | * * *
* * * | . . . | * * *
------+-------+------
* . . | . . . | . . *
* . . | . * . | . . *
* . . | . . . | . . *
------+-------+------
* * * | . . . | * * *
* * * | . . . | * * *
* * * | * * * | * * *

Well, tso sort of proved the impossibility of the first one in the above link, though not rigidly...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby JPF » Thu Apr 19, 2007 12:01 am

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


That's probably true.

But it can happen that a third cell (outside the central box) can be calculated.

In that situation : (a, b, c, are calculated cells) :
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 . . | . a . | c . x
x . . | . b . | . . x
x . . | . . . | . . x
------+-------+------
x x x | . . . | x x x
x x x | . . . | x x x
x x x | x x x | x x x

Would you be able to prove that c = b ?

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

Postby JPF » Thu Apr 19, 2007 10:23 am

More precisely :

Let n be the maximum number of cells which can be determined in a puzzle* with 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
* with at least one solution.

I propose the following propositions or conjectures :

a) n can only have the values 0,1,2,3

b) if n=1, the calculated cell is in the central box
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 . . | . a . | . . x
x . . | . . . | . . x
------+-------+------
x x x | . . . | x x x
x x x | . . . | x x x
x x x | x x x | x x x
Example : 123456789597000436648000215200000004300040001400000002932000148864000957715894623 # 650 solutions

c) if n=2, the calculated cells are in the central box,
but not in the same row and not in the same column.[Edit : wrong, see RW's example in a next post]
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 . . | . a . | . . x
x . . | b . . | . . x
x . . | . . . | . . x
------+-------+------
x x x | . . . | x x x
x x x | . . . | x x x
x x x | x x x | x x x
Example : 123456789947000615586000423700040006400600002600000004369000247854000361271364598 # 900 solutions

d) if n=3, the solutions are equivalent to 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 . . | . a . | b . x
x . . | . b . | . . x
x . . | . . . | . . x
------+-------+------
x x x | . . . | x x x
x x x | . . . | x x x
x x x | x x x | x x x
Example : 123456789594000362768000415300040607400060008600000004917000546246000873835674291 # 408 solutions [code]
[Edit : wrong, the 3 solved cells can be in the central box ; see RW's example in a next post]

Proofs or counter examples are welcome.

JPF
Last edited by JPF on Fri Apr 20, 2007 12:06 pm, edited 1 time in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby RW » Fri Apr 20, 2007 10:25 am

JPF wrote:c) if n=2, the calculated cells are in the central box, but not in the same row and not in the same column.

Counter example:
Code: Select all
684712539
917...428
352...176
4..2....1
2..1....5
1.......2
591...264
726...813
843621957

1200 solutions


JPF wrote:d) if n=3, the solutions are equivalent to this one :

Counter example:
Code: Select all
954123786
721...394
836...215
2...1...3
3....2..1
1..3....2
513...429
682...137
479231658

1872 solutions


JPF, I'm afraid that your proof only shows that there cannot be more than three singles in a grid like this. I can esaily prove that there isn't enough information to give naked or hidden singles in grids like those used in the 9+ thread, but still there is lots of valid puzzles.

To prove that the pattern cannot give an unique puzzle you have to prove that there will always be an unavoidable set within the unsolved cells. It can be hard for the second pattern (the one with r5c5 given), you posted two puzzles with that pattern and 2 solutions in the other thread, both have very different uncovered unavoidable sets.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby JPF » Fri Apr 20, 2007 12:54 pm

Thanks RW for this interesting feedback.
Obviously, my analysis was a bit on the low side.

RW wrote:JPF, I'm afraid that your proof only shows that there cannot be more than three singles in a grid like this.
I can esaily prove that there isn't enough information to give naked or hidden singles in grids like those used in the 9+ thread, but still there is lots of valid puzzles.

I'm not sure I fully understand.
Could you elaborate, please.

Thanks.

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

Postby RW » Fri Apr 20, 2007 2:11 pm

JPF wrote:Could you elaborate, please.

You only look at singles. There may very well be other techniques affecting the empty cells as well. Here's an example with several naked pairs to make extra eliminations in the middle box:
Code: Select all
 *-----------*
 |487|365|912|
 |695|...|738|
 |123|...|456|
 |---+---+---|
 |5..|...|..3|
 |8..|...|..9|
 |3..|...|..5|
 |---+---+---|
 |754|...|321|
 |916|...|587|
 |238|571|694|
 *-----------*

432 solutions

Unfortunately it still has no more than three solved cells. (If this was an unique puzzle, which we know it isn't, we would get one more single with an UR+1.)

In tso's "proof" I didn't really see a proof, just an educated guess. To prove something you have to show that no techniques may possibly eliminate enough candidates to reveal more singles. We know that there is a lot of puzzles that don't have any singles in the beginning, but through extremely complex nested forcing chains we find an unique solution anyway. Any proof for this should also take in account extremely complex nested forcing chains for all possible grids... That's why I thought it might be easier to aproach from the unavoidable set POV.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby JPF » Fri Apr 20, 2007 4:40 pm

RW wrote:You only look at singles. There may very well be other techniques affecting the empty cells as well.

Ok, I understand now.

Here is an example of what you are saying, but with an other pattern. (see ravel's answer)

I leave the (still) valid points of my conjectures:)
and will do some simulations...

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

Postby JPF » Sat Apr 21, 2007 10:25 am

RW,

One more of my conjectures (c) is down.

Here is a nice example that 2 cells not in the central box can be calculated.
The proof needs more than SST.
Code: Select all
 1 2 3 | 4 5 6 | 7 8 9
 4 7 8 | . . . | 6 5 2
 9 6 5 | . . . | 3 1 4
-------+-------+-------
 6 . . | . . . | . . 3
 5 . . | . . . | . . 7
 7 . . | . . . | . . 5
-------+-------+-------
 3 9 1 | . . . | 2 7 6
 2 4 7 | . . . | 5 3 8
 8 5 6 | 7 2 3 | 9 4 1

444 solutions ; but r3c4=2 and r7c5=4
Code: Select all
 1 2 3 | 4 5 6 | 7 8 9
 4 7 8 | . . . | 6 5 2
 9 6 5 | 2 . . | 3 1 4
-------+-------+-------
 6 . . | . . . | . . 3
 5 . . | . . . | . . 7
 7 . . | . . . | . . 5
-------+-------+-------
 3 9 1 | . 4 . | 2 7 6
 2 4 7 | . . . | 5 3 8
 8 5 6 | 7 2 3 | 9 4 1


Probably, more to come.

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

Postby RW » Sat Apr 21, 2007 12:40 pm

Very nice find JFP! Here's a minimal version of the puzzle (assuming we only want to solve the same two cells):
Code: Select all
 *-----------*
 |...|456|7..|
 |.78|...|..2|
 |...|...|...|
 |---+---+---|
 |6..|...|..3|
 |5..|...|...|
 |...|...|...|
 |---+---+---|
 |391|...|..6|
 |2..|...|5..|
 |...|72.|...|
 *-----------*

18 clues, 49664 solutions ; r3c4=2 and r7c5=4

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby JPF » Sat Apr 21, 2007 2:45 pm

This puzzle definitely kills the conjecture d:(

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

242 solutions.

3 solved cells : r5c5=r6c3=r8c4=6

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

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

Postby claudiarabia » Sun Apr 22, 2007 1:49 pm

How about 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 . .

. . . . . . . . .
. # . . . . . . .
. . # # # # # . .
. . # . . # # . .
. . # . . . # . .
. . # # . . # . .
. . # # # # # . .
. . . . . . . # .
. . . . . . . . .
claudiarabia
 
Posts: 288
Joined: 14 May 2006

Postby RW » Sun Apr 22, 2007 2:10 pm

claudiarabia wrote:How about these patterns:

The first is impossible, it's a subset of the 48 clue pattern we're already discussing. I wouldn't get my hopes up about the second pattern, but I'm sure that if there is such a puzzle, then JPF will find it in no time!:)

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Sun Apr 22, 2007 6:18 pm

Code: Select all
+---+---+---+
|...|...|...|
|.4.|...|.3.|
|..9|831|2..|
+---+---+---+
|..2|678|9..|
|..7|1.9|3..|
|..4|523|6..|
+---+---+---+
|..8|412|7..|
|.6.|...|.1.|
|...|...|...|
+---+---+---+


This puzzle was the only one from a miilion grids with a valid puzzle using the template. So I dont think even JPF will find claudias

BTW how does JPF find these puzzles ?

Can he find this sputnik ?
Code: Select all
+---+---+---+
|...|.5.|...|
|.4.|...|.3.|
|..9|...|2..|
+---+---+---+
|...|678|...|
|2..|1.9|..6|
|...|523|...|
+---+---+---+
|..8|...|7..|
|.6.|...|.1.|
|...|.1.|...|
+---+---+---+ many sols


C
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby m_b_metcalf » Sun Apr 22, 2007 9:59 pm

coloin wrote:
Code: Select all
+---+---+---+
|...|...|...|
|.4.|...|.3.|
|..9|831|2..|
+---+---+---+
|..2|678|9..|
|..7|1.9|3..|
|..4|523|6..|
+---+---+---+
|..8|412|7..|
|.6.|...|.1.|
|...|...|...|
+---+---+---+


This puzzle was the only one from a miilion grids with a valid puzzle using the template.

I don't quite understand that. I got five in 30 seconds (100,000 tries). Here's the first:
Code: Select all
  . . . . . . . . .
  . 7 . . . . . 6 .
  . . 8 9 4 1 3 . .
  . . 7 1 9 5 4 . .
  . . 5 6 . 7 1 . .
  . . 3 8 2 4 5 . .
  . . 4 7 8 9 6 . .
  . 1 . . . . . 3 .
  . . . . . . . . .

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Next

Return to General