constraints vs. loss of generality

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

constraints vs. loss of generality

Postby Havard » Thu May 10, 2007 11:28 am

In this post, Red Ed used something he called "symmetry constraints" in order to very quickly calculate wheter a certain pattern had any valid puzzles or not.

This inspired me to do some more research on these constraints, and find out how they work and interact, with the ultimate goal of having a computer program apply them automatically to a template, reducing template-generation speeds!

I invite anyone who is interested to submit templates and suggested constraints to this thread, that then can be checked to see if the constraints cause a loss of generality or not. I also hope that some will be able to confirm the results on this thread, since I don't have complete trust in that my program is reliable.

The pattern I wanted to start with is the same that was discussed in the previous thread, and looks like this:
Code: Select all
. . .|. . .|. . .
. . .|A B C|. . .
. . .|D E F|. . .
-----+-----+-----
. . .|1 2 3|. . .
. . .|4 5 6|. . .
. . .|7 8 9|. . .
-----+-----+-----
. . .|G H I|. . .
. . .|J K L|. . .
. . .|. . .|. . .


There are 6 different valid ways you can fix A.
For A and B there are: 33
A-C: 162
A-D: 648
A-E: 2160
A-F: 6048

A-I: 262656

and finally, fixing all the clues in this template (A-L) gives 2502144 valid ways to fill in this grid. (according to my program)

Now canonizing all of these sub-grids gives (again according to my program, great if someone verified) 8888 unique sub-grids of this template.

This means that with any constraint that is applied, unless it can produce all those 8888 it is a bad constraint, and cause a loss of generality.

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Havard » Thu May 10, 2007 2:28 pm

To start with the simplest possible, I thought that this slightly modified template could be good:
Code: Select all
. . .|. . .|. . .
. . .|A B C|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|1 4 7|. . .
. . .|2 5 8|. . .
. . .|3 6 9|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .


Without any constraints, there are 162 possible ways to fill this grid, but only 6 unique ones! They (can) look like this:
Code: Select all
............412...............147......258......369..............................
............421...............147......258......369..............................
............423...............147......258......369..............................
............471...............147......258......369..............................
............472...............147......258......369..............................
............483...............147......258......369..............................


Now from these it is already clear that we can fix A to a digit.
Now running again with the constraint:
A = 4, we get 27/6 (27 in total, 6 unique)
In other words fixing A to 4 does not loose generality. However, it still produces 27, so that constraint is obviously not enough if we want to only produce unique grids. (our goal!)

Trying to fix A as 5->9, B as 1->3,6->9 and C as 1->6 produces the same result: 27/6.
This is also well reflected in the fact that 162(our total amount) / 27 (total after fixing one digit) = 6 which is the number of of possibilities for each place:
A can be {4,5,6,7,8,9}
B can be {1,2,3,7,8,9}
C can be {1,2,3,4,5,6}

Now let's look at the other type of constraint:
As most people now know, two columns can be shifted inside a stack. If we take one configuration like this:
Code: Select all
. . .|. . .|. . .
. . .|4 1 2|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|1 4 7|. . .
. . .|2 5 8|. . .
. . .|3 6 9|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

and swap column 4 and 6 we get:
Code: Select all
. . .|. . .|. . .
. . .|2 1 4|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|7 4 1|. . .
. . .|8 5 2|. . .
. . .|9 6 3|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

now relabeling by saying that 7=1, 8=2 and 9=3, we get:
Code: Select all
. . .|. . .|. . .
. . .|8 7 4|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|1 4 7|. . .
. . .|2 5 8|. . .
. . .|3 6 9|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

so we can then say that:
(A=8, B=7, C=4) is equivalent to (A=4, B=2, C=1)

In order to limit the number of the equivalent grids that arises from this swapping, Red Ed introduced a term "symmetry constraints", that says that one digit from one "swappable" sector must be smaller than the digit it can replace in the other "swappable" sector. (i like that word, "swappable":) )

This can be shown with the relationship between A and B in this example:
Code: Select all
. . .|. . .|. . .
4 5 6|A B .| 7 8 9
. . .|x x .|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|x x .|. . .
. . .|. . .|. . .
-----+-----+-----
. . .|x x .|. . .
. . .|x x .|. . .
. . .|. . .|. . .

the possible {A,B} configurations are:
{1,2}
{1,3}
{2,1}
{2,3}
{3,1}
{3,2}

since columns 4 and 5 can be swapped and relabled for yet another isomorph of this template, we have these equivalent combinations for A and B: (1-2 / 2-1), (1-3 / 3-1), (2-3 / 3-2)

What Red Ed did to prevent these from happening, was saying that A must be smaller than B -> (A < B)
Of the 6 possible combinations, this will limit us to:
{1,2}
{1,3}
{2,3}
and no isomorphs would arise from swapping of column 5 and 6, this constraint effectivly preventing it!:)

The simplest way of showing this in context would be with this example:
Code: Select all
. . .|A . .|. . .
. . .|. . B|. . .
. . .|. . C|. . .
-----+-----+-----
. . .|1 4 7|. . .
. . .|2 5 8|. . .
. . .|3 6 9|. . .
-----+-----+-----
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .

This gives 150 combinations / 15 unique.
Now by adding (B<C) as a constraint, preventing row 2 and row 3 freely swapping place, the results are: 75 / 15. In other words, we have exactly cut the number of combinations in two, without losing any generality!:)
This is what the output then looks like:
Code: Select all
...4..........1........2......147......258......369..............................
...6..........1........2......147......258......369..............................
...7..........1........2......147......258......369..............................
...9..........1........2......147......258......369..............................
...5..........1........4......147......258......369..............................
...7..........1........4......147......258......369..............................
...8..........1........4......147......258......369..............................
...4..........1........5......147......258......369..............................
...6..........1........5......147......258......369..............................
...7..........1........5......147......258......369..............................
...8..........1........5......147......258......369..............................
...9..........1........5......147......258......369..............................
...6..........4........5......147......258......369..............................
...7..........4........5......147......258......369..............................
...9..........4........5......147......258......369..............................

We see that B is kept smaller than C, but notice how now A is moving around!
Does this mean that we can't fix A and have the symmetry constraint?
Fixing A=4 gives 10/6, so we are only getting 6 of the 15!
Interestingly: A=4,5,6 -> 10/6 but A= 7,8,9 -> 15/9.
In other words, by fixing A as 4,5,6, we are only giving B and C 5 numbers to play with! This is best illustrated by looking at the output:
Code: Select all
...A..........B........C......147......258......369..............................
...4..........1........2......147......258......369..............................
...4..........1........5......147......258......369..............................
...4..........2........3......147......258......369..............................
...4..........2........5......147......258......369..............................
...4..........2........6......147......258......369..............................
...4..........5........6......147......258......369..............................

Code: Select all
...A..........B........C......147......258......369..............................
...7..........1........2......147......258......369..............................
...7..........1........4......147......258......369..............................
...7..........1........5......147......258......369..............................
...7..........2........3......147......258......369..............................
...7..........2........4......147......258......369..............................
...7..........2........5......147......258......369..............................
...7..........2........6......147......258......369..............................
...7..........4........5......147......258......369..............................
...7..........5........6......147......258......369..............................

We see that combinations like B=1-C=4 and B=4-C=5 is effectively eliminated in the first one, since A is set to 4. Note that if A were 5, 1-5 and 5-6 would go, and if it were 6 2-6 and 5-6 would go!

So why does A=7,8,9 produce 15/9 when the full grid is 150/15? Why are we still 6 short!

Adding JUST A=(7,8,9) as a constraint gives the result: 30/9!
Aha! There is nothing wrong with the interaction of A=(7,8,9) and B<C, it is something wrong with fixing A!

Why? What has changed since our last example, where it was OK to fix the A! (pun intended!)
Let's look at the 15 unique:
Code: Select all
...4..........1........2......147......258......369..............................
...4..........1........5......147......258......369..............................
...4..........2........3......147......258......369..............................
...4..........2........5......147......258......369..............................
...4..........2........6......147......258......369..............................
...4..........5........6......147......258......369..............................
...7..........1........2......147......258......369..............................
...7..........1........4......147......258......369..............................
...7..........1........5......147......258......369..............................
...7..........2........3......147......258......369..............................
...7..........2........4......147......258......369..............................
...7..........2........5......147......258......369..............................
...7..........2........6......147......258......369..............................
...7..........4........5......147......258......369..............................
...7..........5........6......147......258......369..............................

This clearly shows that there is no fixable clue with this template...
Why?!?
Well, the first observation is that:
A has the possibilities {4,5,6,7,8,9}
B AND C has the possibilities {1,2,3,4,5,6}
Second observation is that B and C share a sector, while A does not share anything.

Ok, I think I will wrap up this post now, and continue later. One more note for the last template. Since we got 75/15 for the last template with (B<C), cutting the possibilities down by two, it "should" mean that there are some sort of constraint out there that will reduce the grid with a factor 5... (75/15 = 5):D

so, are you guys interested?:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005


Return to General

cron