The New Sudoku Players' Forum

[tarek]

I hope this makes sense to somebody.

There are pattens that can't provide a single-solution vanilla sudoku.

I am hoping that this may inspire some programmer (other than myself) to test if it would be feasible to try it out.

In a PM grid ....

Code: Select all

 . . . | a b c | . . . 
 . . d | . . . | e . . 
 . f . | . . . | . g . 
-------+-------+------
 h . . | . . . | . . i 
 j . . | . . . | . . k 
 l . . | . . . | . . m 
-------+-------+------
 . n . | . . . | . o . 
 . . p | . . . | q . . 
 . . . | r s t | . . .

cells containing given clues are labelled (in this example alphabetically) .... notice that labelling is sorted incrementally.

While candidate cells are labelled numerically

Code: Select all

 01 02 03 | .  .  .  | 07 08 09   
 10 11 .  | 13 14 15 | .  17 18 
 19 .  21 | 22 23 24 | 25 .  27   
----------+----------+---------
 .  29 30 | 31 32 33 | 34 35 . 
 .  38 39 | 40 41 42 | 43 44 . 
 .  47 48 | 49 50 51 | 52 53 . 
----------+----------+---------
 55 .  57 | 58 59 60 | 61 .  63 
 64 65 .  | 67 68 69 | .  71 72 
 73 74 75 | .  .  .  | 79 80 81 

also note that cells' labels are sorted incrementally

If you can get an automorphic puzzle (through symmetry operations) where candidate cells labels are not incrementally sorted then this provides a proof that this pattern will ALWAYS produce multiple solutions.


Now,

Correct me if I'm wrong. If all possible isomorphically different 16 clue patterns undergo this process we would then prove that a valid 16 puzzle cannot exist. If it can exist then we can tell through which pattern & limit our search for that elusive 16.

tarek

[RW]

First of all, congratulations on post number 1500!!

I hope this makes sense to somebody.

Sorry, need some more explanation...

If you can get an automorphic puzzle (through symmetry operations) where candidate cells labels are not incrementally sorted then this provides a proof that this pattern will ALWAYS produce multiple solutions.

Care to elaborate on this?

RW

[tarek]

Sorry, need some more explanation...

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

& label pattern cells using a system that has incremental values (alphabet in this case) like this

Code: Select all

 . . . | a b c | . . . 
 . . d | . . . | e . . 
 . f . | . . . | . g . 
-------+-------+------
 h . . | . . . | . . i 
 j . . | . . . | . . k 
 l . . | . . . | . . m 
-------+-------+------
 . n . | . . . | . o . 
 . . p | . . . | q . . 
 . . . | r s t | . . .

The empty cells are labelled using another system with incremental values (in this case cell numerical address) like this:

Code: Select all

Code:
 01 02 03 | .  .  .  | 07 08 09   
 10 11 .  | 13 14 15 | .  17 18 
 19 .  21 | 22 23 24 | 25 .  27   
----------+----------+---------
 .  29 30 | 31 32 33 | 34 35 . 
 .  38 39 | 40 41 42 | 43 44 . 
 .  47 48 | 49 50 51 | 52 53 . 
----------+----------+---------
 55 .  57 | 58 59 60 | 61 .  63 
 64 65 .  | 67 68 69 | .  71 72 
 73 74 75 | .  .  .  | 79 80 81 

super-impose, like this

Code: Select all

 01 02 03 | a  b  c  | 07 08 09   
 10 11 d  | 13 14 15 | e  17 18 
 19 f  21 | 22 23 24 | 25 g  27   
----------+----------+---------
 h  29 30 | 31 32 33 | 34 35 i 
 j  38 39 | 40 41 42 | 43 44 k 
 l  47 48 | 49 50 51 | 52 53 m 
----------+----------+---------
 55 n  57 | 58 59 60 | 61 o  63 
 64 65 p  | 67 68 69 | q  71 72 
 73 74 75 | r  s  t  | 79 80 81 

Run symmetry operations 2*(6^8) on the combined grid

After each operation:
1. if clue cells ARE NOT like this:

Code: Select all

 . . . | a b c | . . . 
 . . d | . . . | e . . 
 . f . | . . . | . g . 
-------+-------+------
 h . . | . . . | . . i 
 j . . | . . . | . . k 
 l . . | . . . | . . m 
-------+-------+------
 . n . | . . . | . o . 
 . . p | . . . | q . . 
 . . . | r s t | . . .

then continue with the following symmetry operation

if Check point 1 fails (which means that we have now the same pattern with same cell addresses) then

2. if empty cells ARE NOT like this:

Code: Select all

 01 02 03 | .  .  .  | 07 08 09   
 10 11 .  | 13 14 15 | .  17 18 
 19 .  21 | 22 23 24 | 25 .  27   
----------+----------+---------
 .  29 30 | 31 32 33 | 34 35 . 
 .  38 39 | 40 41 42 | 43 44 . 
 .  47 48 | 49 50 51 | 52 53 . 
----------+----------+---------
 55 .  57 | 58 59 60 | 61 .  63 
 64 65 .  | 67 68 69 | .  71 72 
 73 74 75 | .  .  .  | 79 80 81 

Then this proves that this pattern will ALWAYS have multiple solutions (You can stop here)

if Check point 2 fails (which means that we ended up with the same cell addresses for both pattern & empty cells) then Resume symmetry operations

if all symmetry operations were done without failing the 2nd Check point then this pattern May have unique puzzles

I hope that it's clearer now

First of all, congratulations on post number 1500!!

Thanx, I haven't noticed

tarek

[RW]

Yes, I understood that part. What I don't understand is why it proves anything. Forgive my stupidity if I'm missing something obvious, but isn't it always possible to scramble any automorphic pattern so that it fails both of your checkpoints?

[Edit: reread your post and noticed that I might have misunderstood check point one. So you are looking for an automorphic version where the cells with givens are in exactly the same location (each given stays in the same location) but the empty cells are not in the same location. Am I correct? Can you find such an automorph for the pattern you posted? Is it possible to find such an automorph through basic symmetry operations, unless the grid has two empty rows or columns in the same chute? ]

RW

[tarek]

Am I correct?

yes

Can you find such an automorph for the pattern you posted? Is it possible to find such an automorph through basic symmetry operations, unless the grid has two empty rows or columns in the same chute?

That is what i'm hoping to find. I might be completely wrong.

A counter-example is enough....

the 2 empty-columns in a chute is an easy example which is not what I'm after.

After re-thinking, a 3rd check point is needed:

if current cell Label IS NOT EQUAL to original label of that cell THEN Multiple solutions can be proved if ORIGIN and DESTINATION share a constraint....

So a hypothetical situation like this

Code: Select all

 07 02 03 | .  .  .  | 01 08 09   
 10 11 .  | 13 14 15 | .  17 18 
 19 .  21 | 22 23 24 | 25 .  27   
----------+----------+---------
 .  29 30 | 31 32 33 | 34 35 . 
 .  38 39 | 40 41 42 | 43 44 . 
 .  47 48 | 49 50 51 | 52 53 . 
----------+----------+---------
 55 .  57 | 58 59 60 | 61 .  63 
 64 65 .  | 67 68 69 | .  71 72 
 73 74 75 | .  .  .  | 79 80 81

where cells Labels (01 & 07) have changed position ....They also share the same row ...
That means that cell 1 can be cell 7 which can't be true in a unique solution sudoku.

so it should finally look like this:

Code: Select all

if a symmetry operation results in:
1. same pattern labels &&
2. different empty cell labels &&
3. ANY origin & destiantion labels share a constraint

Then this pattern has multiple solutions

Again, the 2 empty columns in a chute is an easy example but that is not what I'm after

It sounds to simple to be true IMO

tarek

[RW]

the 2 empty-columns in a chute is an easy example which is not what I'm after.

But I'm afraid it's the only option... If there isn't two empty rows/cols in a chute, then every legal legal permutational operation will move at least one given. To return it to it's original location, you will have to perform the same operation reversed, which also moves all empty cells to their original locations.

RW

[tarek]

To return it to it's original location, you will have to perform the same operation reversed, which also moves all empty cells to their original locations.

No

Code: Select all

 1 . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . 81

90 rotation

 . . . | . . . | . . 1
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
81 . . | . . . | . . .

Chute 1 - Chute 3

   . 1 | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . |81 . . 

coumn 1 - column 3 in chutes 1&3

 1 . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . . 
-------+-------+------
 . . . | . . . | . . . 
 . . . | . . . | . . . 
 . . . | . . . | . . 81 

tarek

[tarek]

A slightly better example:

Code: Select all

 a . . | . . . | . . . 
 . b . | . . . | . . . 
 . . c | . . . | . . . 
-------+-------+------
 . . . | d . . | . . . 
 . . . | . e . | . . . 
 . . . | . . f | . . . 
-------+-------+------
 . . . | . . . | g . . 
 . . . | . . . | . h . 
 . . . | . . . | . . i

1. 90 Rotation
2. Chute 1 - Chute 3
3. column 1 - column 3
4. Column 4 - Column 6
5. column 7- column 9

will return pattern cell labels exactly to their starting position

Now Focusing on Box 1:

Code: Select all

 a 02  03 |
10  b  12 |
19 20  c  |
----------+

90 rotation

19 10   a |
20  b  02 |
c  12  03 |
----------+

column 1  - column 3

 a 10  19 |
02  b  20 |
03 12   c |
----------+

This pattern will have multiple solutions because r1c2 can be r2c1 which are in the same box (amongst other similar examples). this can't be true in a unique solution sudoku

I've just proved that this pattern will ALWAYS have multiple solutions

We now need a proper 17+ clue example to convince myself & RW that this is feasible

tarek

[Edit: I'm actually struggling to find a 10 clue puzzle. I knew it, too simple to be true ]

[Red Ed]

Here's another way of putting it. The symmetry/relabelling operations (from the group of 9! x 3359232) fall into two camps: the "nice" ones have automorphic grids; the "nasty" ones (most of them) don't. Any automorphism of a unique-solution puzzle is an automorphism of its solution: so no unique-solution puzzle can have a "nasty" automorphism.

I used an argument very similar to tarek's to quickly find most of the "nasty" automorphism classes a while back.

[RW]

Ok, I gave you the short argument, because I was hoping that I wouldn't need to spell out the long argument... Yes, you can get one cell back to it's original location, or even 9 as in your second example. However, both of these used a 90 degree rotation. When you rotate the grid 90 degrees, rows become columns and columns become rows. So if you have more than one clue in a row, after the rotation they will not be in the same row, they are in the same column. They will stay in the same column until you rotate the grid again (reverse the operation).

The point is, every permutational operation you make will move a least one clue. This clue will have to be moved back to it's original location. In a pattern that doesn't have two empty rows within a chute, there is max one possible way to swap rows in each chute that affect only one clue. Say you have one clue in r1, one in r2 and none in r3. You may swap r2 and r3 only moving one clue. Now, to return the clue of r2 to r2, you must either reverse the operation or first swap r1 and r3 (originally r2), then r1 and r2. This will leave you with the clue originally located in r1 now in r3, so you have to swap r1 and r3 again to return it to it's original location - you're back at your starting point again.

Another thing you should know about permutations is that a unit is a unit and a chute is a chute. You cannot split these. If you have 9 symbols in one unit, then those nine symbols will move together as a unit through all permutations. The situation you described earlier (where r1c1 and r1c7 had changed places) is impossible, because you had removed those cells from their original box and column units.

I'm sorry, but there is no way around this. You simply cannot create a pattern that would fail both your first checkpoints, that doesn't have two empty rows or columns in a chute.

RW

[tarek]

You are correct RW regarding the VERY limited application to this method.

I agree that 2 cells can't just Swap places (it was just to make a point of how to interpret results).

The 2 clumns in a chute is not only the applicable example as I demonstrated with the 9 clue diagonal pattern.

It works because there is only 1 clue per row & per column.

I wouldn't be able to do it if there were more than 1 clue per row or column.(As RW mentioned)

Re-labelling is the way around all of this. Sadly, you can't relabel without knowing the solution, a luxury that we still don't have from the info supplied by pattern cell locations.

So at the end,

It is a method that currently has EXTREMELY limited application in finding invalid patterns (limited to only 2 or more empty lines per chute, or to puzzles with each clue falling in one column & one row)

Thanx for the input RW & Red Ed

tarek