Findings Invalid Patterns

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

Findings Invalid Patterns

Postby tarek » Thu Apr 17, 2008 1:53 pm

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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Re: Findings Invalid Patterns

Postby RW » Thu Apr 17, 2008 3:57 pm

First of all, congratulations on post number 1500!!:D

tarek wrote:I hope this makes sense to somebody.

Sorry, need some more explanation...:(

tarek wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Re: Findings Invalid Patterns

Postby tarek » Thu Apr 17, 2008 4:30 pm

RW wrote: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:(

RW wrote:First of all, congratulations on post number 1500!!:D
Thanx, I haven't noticed:D

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby RW » Thu Apr 17, 2008 4:59 pm

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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby tarek » Thu Apr 17, 2008 5:22 pm

RW wrote:Am I correct?
yes

RW wrote: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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby RW » Thu Apr 17, 2008 5:50 pm

tarek wrote: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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby tarek » Thu Apr 17, 2008 5:56 pm

RW wrote: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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby tarek » Thu Apr 17, 2008 6:52 pm

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:( ]
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby Red Ed » Thu Apr 17, 2008 10:06 pm

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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Thu Apr 17, 2008 10:57 pm

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
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby tarek » Fri Apr 18, 2008 7:23 am

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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006


Return to General