The New Sudoku Players' Forum

[Mauricio]

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:

Pattern 3 JPF non valid ==> Pattern 3 Mauricio non valid.

[Mauricio]

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?

[RW]

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]

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

[JPF]

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,

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

[Mauricio]

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.

[ravel]

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

[JPF]

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

[RW]

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?

But of course we would like to see a pattern oriented poof here

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

[ravel]

Wasn't your old conjecture already proved?

I thought, Red Ed had verified (also) this with an exhaustive search ?

But of course we would like to see a pattern oriented poof here

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.

[JPF]

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]

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

[Eioru]

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.

[m_b_metcalf]

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

[RW]

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