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

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

Postby Mauricio » Wed Aug 01, 2007 8:20 am

JPF wrote:Pattern 3 JPF ...

Pattern 3 Mauricio ...

In that case it is an absolute yes, as your patterns contains mine, if my pattern is valid then your pattern is valid too, and using a contrapositive, then one gets the sentence:
JPF wrote: Pattern 3 JPF non valid ==> Pattern 3 Mauricio non valid.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Mauricio » Thu Aug 02, 2007 9:45 am

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

Perhaps a reverse bug argument can be used to prove that this pattern is invalid, but I am no expert on the reverse bug. Would an expert care to give his/her opinion?
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby RW » Fri Aug 10, 2007 7:36 am

Mauricio wrote:Perhaps a reverse bug argument can be used to prove that this pattern is invalid, but I am no expert on the reverse bug. Would an expert care to give his/her opinion?

As an "expert" I must say that I can't see any direct explanation to why the pattern is invalid using reverse Bug arguments. However, Your pattern gave me one new idea about unavoidable sets. This is my conjecture:

Any group of N digits restricted to N+1 columns of the same band will contain at least one unavoidable set.

So far I've quite easily proved this for N=2,3,5,6. N=2 is always an unavoidable set of size 6:
Code: Select all
1 | . | 2
2 | 1 | .
. | 2 | 1

N=3 always contains at least one unavoidable set of size 6:
Code: Select all
1 | 2 | XX
2 | 3 | XX
3 | 1 | XX

N=5 requires a longer explanation, but it can be shown that it will always contain at least one simple unavoidable set (with "a simple" set I mean a set that is either confined to two rows or a set that uses only two different digits = easy to recognize for the human eye).

N=6 can give these two patterns that don't contain any simple unavoidable sets:
Code: Select all
1 4 . | 6 5 . | . 2 3
2 5 . | 1 3 . | 6 4 .
3 6 . | 2 4 . | 1 . 5

1 4 . | 5 3 . | . 2 6
2 5 . | 1 6 . | 4 3 .
3 6 . | 2 4 . | 1 . 5

but both of them contain several more complex unavoidable sets.

N=4 and N=7 are physically impossible, so all that remains is to prove the case of N=8, which is exactly the case of your pattern above.

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

Postby RW » Fri Aug 10, 2007 2:45 pm

On second thought, I believe there's an easier way to prove that Mauricios pattern can't give any unique puzzles. Assume there actually is an unique puzzle with this pattern:

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

First of all, one of the digits '1' in the top band is a hidden single and can safely be removed. Now we are left with one empty row and two rows that only contain digit 1. If we decide to move one of those givens to another row in the same column, we will also get an unique puzzle (swapping rows). This implies that if we remove any of the remaining givens we will have a pseudo puzzle with two solutions like this:
Code: Select all
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . 1 |
+-------+-------+-------+
| 1 2 3 | x x x | x x x |
| 4 5 6 | 1 x x | x x x |
| 7 8 9 | x x x | 1 x x |
+-------+-------+-------+
| x 1 x | x x x | x x x |
| x x x | x 1 x | x x x |
| x x x | x x x | x 1 x |
+-------+-------+-------+

Now we can see that we could move the remaining given in the top band to any of the three rows and still always have only two solutions. This would give a total of six solutions for this puzzle:
Code: Select all
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 1 2 3 | x x x | x x x |
| 4 5 6 | 1 x x | x x x |
| 7 8 9 | x x x | 1 x x |
+-------+-------+-------+
| x 1 x | x x x | x x x |
| x x x | x 1 x | x x x |
| x x x | x x x | x 1 x |
+-------+-------+-------+

An empty band with only six solutions? If I recall correctly someone has already calculated the minimum amount of solutions for an empty band. I can't find those results now, but I'm sure the minimum is a lot more than six.

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

Postby JPF » Fri Aug 10, 2007 3:12 pm

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

An empty band with only six solutions? If I recall correctly someone has already calculated the minimum amount of solutions for an empty band. I can't find those results now, but I'm sure the minimum is a lot more than six.

right,
here, I wrote:Conjecture IV

This puzzle (B1B2B3=0)
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


Can only have 0 or 12k solutions.
(k is one of these 16 numbers : 8,10,12,13,14,15,16,18,19,22,23,24,43,48,72,144 )

As a consequence, when the puzzle has at least one solution, the minimum number of solutions is 96 and the maximum is 1728.


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

Postby Mauricio » Fri Aug 10, 2007 6:54 pm

RW wrote:On second thought, I believe there's an easier way to prove that Mauricios pattern can't give any unique puzzles.

I think you are correct. Thanks!
I never thought about considering pseudopuzzles, and certainly was not aware of JPF conjecture.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby ravel » Sat Aug 11, 2007 10:13 am

RW,

nice proof by contradiction (assume the puzzle is unique, then the pseudo puzzle has 6 solutions - contradiction).

But of course we would like to see a pattern oriented poof here:D
ravel
 
Posts: 998
Joined: 21 February 2006

Postby JPF » Sat Aug 11, 2007 10:46 pm

Proposed conjecture :

Mauricio's pattern has 0 or at least 16 solutions.

More precisely, the pattern can only have 0 or 2k solutions.
(k is one of these 16 numbers : 8,10,12,13,14,15,16,18,19,22,23,24,43,48,72,144 )

Here's an example with 16 solutions :

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


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

Postby RW » Sat Aug 11, 2007 11:35 pm

JPF wrote:Proposed conjecture :

Mauricio's pattern has 0 or at least 16 solutions.

More precisely, the pattern can only have 0 or 2k solutions.
(k is one of these 16 numbers : 8,10,12,13,14,15,16,18,19,22,23,24,43,48,72,144 )


If your previous conjecture about the three empty boxes is proved to be correct, then this is a direct consequence of that as the ones lock the rows in place and divide the amount of solutions by six. Wasn't your old conjecture already proved?

ravel wrote:But of course we would like to see a pattern oriented poof here:D

My best guess for finding a pattern based proof would be to develop the Hidden BUG technique to handle cells with more than two candidates. I believe this could be done, but I got so confused by the vanishing of that thread so I haven't had time to develop that theory yet. Alternatively it could of course be a massive layered BUG-lite...

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

Postby ravel » Sun Aug 12, 2007 12:16 pm

RW wrote:Wasn't your old conjecture already proved?
I thought, Red Ed had verified (also) this with an exhaustive search ?
ravel wrote:But of course we would like to see a pattern oriented poof here:D
My best guess for finding a pattern based proof would be ...
Sorry, this was just a joke concerning the endless t&e discussions. I prefer proofs by contradictions, when they are shorter and/or more elegant.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby JPF » Sun Aug 12, 2007 1:14 pm

RW, ravel

It's just a question of wording.

The "old conjecture" (IV) is not a conjecture any more, as it had been verified by Red Ed.
Let's call it proposal IV

My "new conjecture" concerning Mauricio's pattern is obviously a consequence of proposal IV.
So it's a proposal.

By using this new proposal, Mauricio's conjecture (i.e. the pattern doesn't have a valid puzzle) is directly proved.

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

Postby JPF » Wed Aug 29, 2007 6:46 pm

Is this pattern valid ? i.e. : is there a valid puzzle with this pattern ?

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


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

Postby Eioru » Wed Sep 26, 2007 11:52 am

This pattern sometimes has a Bug.

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


I try to add another one empty box.
Code: Select all
*********   *********
*********   *********
...***...   ...***...
...*.*...   ....*....
...*.*...   ....*....
...*.*...   ....*....
...***...   ...***...
*********   *********
*********   *********

But no valid puzzles come out.
Eioru
 
Posts: 182
Joined: 16 August 2006

Postby m_b_metcalf » Wed Sep 26, 2007 1:32 pm

Eioru wrote:I try to add another one empty box.
Code: Select all
*********   *********
*********   *********
...***...   ...***...
...*.*...   ....*....
...*.*...   ....*....
...*.*...   ....*....
...***...   ...***...
*********   *********
*********   *********

But no valid puzzles come out.

I had a similar problem with the 'I' in the Sudoku Alphabet. This is the best I can get as an approximation to your pattern (one clue fewer):
Code: Select all
 1 2 3 4 5 6 7 8 9
 8 6 9 1 2 7 5 4 3
 . . . 8 3 9 . . .
 . . . 2 . 5 . . .
 . . . . 1 . . . .
 . . . 6 . 4 . . .
 . . . 5 8 2 . . .
 2 7 8 9 4 3 1 5 6
 3 5 4 7 6 1 2 9 8

Regards,

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

Postby RW » Wed Sep 26, 2007 2:04 pm

Eioru wrote:I try to add another one empty box.
Code: Select all
*********   *********
*********   *********
...***...   ...***...
...*.*...   ....*....
...*.*...   ....*....
...*.*...   ....*....
...***...   ...***...
*********   *********
*********   *********

Your second pattern is impossible because of the same reasons as Mauricios pattern above (assume uniqueness, one clue in column 5 may be removed as hidden single, then row swapping tells you that the puzzle with an empty band would have 6 solutions=impossible).

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

PreviousNext

Return to General

cron