The New Sudoku Players' Forum

[PaulIQ164]

I found a new technique that I believe is almost entirely useless today. I'll explain it later. Promise.

[PaulIQ164]

I just put it in its own new thread in "Solving Techniques", since that is what it is.

[Condor]

That is very interesting condor. If you have anything else you have discovered along this line, I would be interested in hearing about it.

Thanks!

Ok I will post some more discoveries if you like. They might set others thinking and lead to still more discoveries.

One thing I have discovered is that if you take any template and permute the columns in the stacks and rows in the bands then all the other templates can be produced. There are 6 ways of permuting the rows/columns in a band/stack and 6 bands and stacks on a sudoku grid.

This discovery gave me an idea for naming templates.

To name templates we need 3 things.

1. A number to represent the permutations in a band or stack.

Code: Select all

Permutation
number       Order
1            1,2,3
2            1,3,2
3            2,1,3
4            2,3,1
5            3,1,2
6            3,2,1

2. 6 digits, one for each band and stack. I put them in the order of bands 1 2 3, then stacks 1 2 3.

3. An identity template.

Code: Select all

* . .   . . .   . . .
. . .   * . .   . . .
. . .   . . .   * . .

. * .   . . .   . . .
. . .   . * .   . . .
. . .   . . .   . * .

. . *   . . .   . . .
. . .   . . *   . . .
. . .   . . .   . . *

I use this template because it was the first one found by my program.

An example of how it works.

Lets produce template 315264. This will be done in 2 stages to make it easier to see.

First take the identity template and permute each band

Code: Select all

     2  . . .   * . .   . . .
3    1  * . .   . . .   . . .
     3  . . .   . . .   * . .

     1  . * .   . . .   . . .
1    2  . . .   . * .   . . .
     3  . . .   . . .   . * .

     3  . . .   . . .   . . *
5    1  . . *   . . .   . . .
     2  . . .   . . *   . . .

Now permute the stacks in the same way.

Code: Select all

          2       6       4
        1 3 2   3 2 1   2 3 1

        . . .   . . *   . . .
        * . .   . . .   . . .
        . . .   . . .   . . *

        . . *   . . .   . . .
        . . .   . * .   . . .
        . . .   . . .   * . .

        . . .   . . .   . * .
        . * .   . . .   . . .
        . . .   * . .   . . .

That is template 315264.

I am not a math guy, but I assume that the fact that there are 6 ways of permuting the "stacks" and 6 "stacks" is the reason why there are 6^6 templates. Is that right?

This would appear to be the case.

[BlueSpark]

I like that naming system. I am going to poke around with it and see what I can find out.

Thanks!

[Condor]

I too have found it very helpful to think of the sudoku as 9 interlocking templates (although I used the term "pattern" but will use "template" in the future as it is to my ear much better ).

I saw someone else use the term "template" in this forum some months ago and thought it appropiate

[Condor]

I like that naming system. I am going to poke around with it and see what I can find out.

I have made a discovery that makes use of the naming system. If you want I can post. However it is more appropiate in the 3D thread as it applies to Dion Cubes.

[Condor]

I am not a math guy, but I assume that the fact that there are 6 ways of permuting the "stacks" and 6 "stacks" is the reason why there are 6^6 templates. Is that right?

This would appear to be the case.

After giving this some more thought have decide it must be the case.

If you put a digit in the first row, it must be in 1 of the 3 boxes. For the second row 2 boxes, and of course 1 box for the third row. A basic combination. 3!

The same applies for the other bands and stacks. So the number of templates must be 6^6=46656.

[Condor]

I like that naming system.

I should have added how to work out the template name. It is actually quite simple.

I will show the basic proceedure with an example band. The boxes are numbered 1 to 3 from left to right. (For columns, the boxes are numbered from top to bottom.) Just note which box the digit is in as represented by the asterisk.

Code: Select all

. . .   . * .   . . .
* . .   . . .   . . .
. . .   . . .   * . .

Reading the rows from top to bottom we get 213, which is permutation number 3.

Code: Select all

Permutation
number       Order
1            1,2,3
2            1,3,2
3            2,1,3
4            2,3,1
5            3,1,2
6            3,2,1

The process is repeated for each band and stack.

For example this template is 453633.

Code: Select all

. . .   . * .   . . .
. . .   . . .   . * .
. . *   . . .   . . .

. . .   . . .   * . .
. * .   . . .   . . .
. . .   * . .   . . .

. . .   . . *   . . .
* . .   . . .   . . .
. . .   . . .   . . *

[coloin]

I too have found it very helpful to think of the sudoku as 9 interlocking templates
It seems that the template concept would be one model by which to approach the question of the minimum number of clues required for a valid sudoku puzzle.

I think you might be right - it may well be useful for the minimum clues question.

The first template is 46656 ways [definite] These are all essentially similar !

EDIT
This is best worked out with options for each clue
9|4|1
1|9|6
6|1|4

=3^6* 2^6 = 6^6

Now to try to estimate the number of templates for each clue number. [Some combinations dont give a completable grid.]
the 2nd template might be ? [8^2] * [6*5*4*3] = 23040 [guestimate].
the 3rd ? variable
the 4th ? variable
the 5th ? -----120 --?ways
the 6th ---- 24 --? ways
the 7th ---- 6 --? ways
the 8th ---- 2 ways usually - but will be 4 if there is an unavoidable pair with the two clues !
the 9th --- only one way [definite]

The average number of ways sum up to N [Bertram] ! I am sure we could estimate an average for the missing numbers......
EDIT + EDIT...
heres a guess at an average figure. Note this is the number of ways you can add a template given previous fillings.
46656 [def]
8696 [def]
2065 [calculated average]
?1500
?1000
?100
?15
?3 [about right]
1 [def]

totaling 5.6*10^21 !

I think it is a tough one to work it out exactly. I'm not sure how far anyone got with it when we were trying to work out N [Bertram].
The reason this might be useful is if we can combine the opening clues to generate more clues / cover the sets efficiently.

There are many ways to to represent the patterns below !

For example

Two initial grids

1

Code: Select all

To complete 3 1s to 9 1s
+---+---+---+
|1..|...|...|
|...|..2|7..|
|...|...|...|
+---+---+---+
|...|...|...|
|...|.1.|...|
|.8.|...|2..|
+---+---+---+
|.2.|...|...|
|.34|...|...|
|...|...|..1|
+---+---+---+ 10 clues .....all the 1s can be completed ........16 total.


there are 3 ways to arrange the 3 1s this way, 6 boxes to have 3 clues [234],4 different ways to complete the remaining 1s. [3*6*4] There are also other combinations of three clues of one number which solve to 16.
2

Code: Select all

To complete 3 2s to 9 2s
+---+---+---+
|1..|...|...|
|...|..2|...|
|8.7|...|..5|
+---+---+---+
|...|...|...|
|...|.1.|...|
|...|...|2..|
+---+---+---+
|.2.|...|...|
|...|...|...|
|...|.7.|..1|
+---+---+---+  10 clues.....all the 2s can be completed ........16 total.


put them together

Code: Select all

+---+---+---+
|1..|...|...|
|...|..2|7..|
|8.7|...|..5|
+---+---+---+
|...|...|...|
|...|.1.|...|
|.5.|...|2..|
+---+---+---+
|.2.|...|...|
|.35|...|...|
|...|.7.|..1|
+---+---+---+     14 clues total
                         The non-1, non-2 clues can be varied - to give 26-30 clues - some give no solutions !!



Code: Select all

an example with extra clues shown
+---+---+---+
|1.2|...|...|
|5.3|1.2|7..|
|8.7|...|125|
+---+---+---+
|.1.|.2.|...|
|27.|.1.|...|
|.5.|...|21.|
+---+---+---+
|.21|...|...|
|.35|..1|..2|
|.8.|27.|..1|
+---+---+---+    30 clues


We have 4 templates here
The 1,2 complete to 9 clues
The 5,7 goes from 3 to 4 clues only

If we know the possible templates for the first 3 or 4 templates we might be able to improve on the clues generated....I think thats what low clue solutions do...and they go on to solve the grid.

Or it may be totally fruitless ...as there never will be found a 16.
C

[AARIMA21]

I have only recently learned of sudoku, and it looks like I will soon be addicted if I am not already. Like everyone else I have poked around to see if I could find quicker or novel ways to solve them. Many of the things I have found out are, alas, completely useless in that regard. Here are some of them:

(1) It is obvious that if you were to assign values to the positions of each row and column--1 to 9 from top to bottom and left to right, or whatever--then the sum of the position values of any given number in a completed sudoku adds up to 45, since 1+2+3+4+5+6+7+8+9=45 and each number appears in every row and column only once. This is also true, however, when you assign position values 1 to 9 within the 3x3 boxes of the sudoku--even though a given number might appear at the same position in 2 or 3 different boxes (3 is the limit I think). For instance, number X might appear in the 9th cell of the upper-left hand box and also appear in the 9th cell of the center box, but this high total (18 for only two boxes) will be elsewhere balanced off and 45 will be the total of the position values of X. Cool!

(2) If you assign values to the positions of the entire sudoku (1 to 81), then the total of the position values of any given number is 369, which is a fine, fine number. Cool!

(3) Take a sudoku puzzle. Select any 3x3 box (or column or row) that has some numbers in it. In a blank sudoku write the numbers 1 to 9 in order (they don't have to be in order but it makes it easier as they are meant to be position values) in the 3x3 box that corresponds to the one you have chosen in the puzzle. As you figure out numbers in the puzzle, in the corresponding cells of the blank sudoku write the number of the position that that number you have figured out occupies in the chosen 3x3 box of the puzzle. (For instance, suppose you have chosen the top left box. You then figure out that r7c6 is a 9. In the top left box there is a 9 at position 4. Write 4 at r7c6.) This process creates in the blank sudoku another valid sudoku. Upon reflection it is clear that this must be so--and it is so obvious as not to be helpful. I thought at first that the two "sister sudokus" might help each other to maturity in a sort of logical feedback and transfer snowball maelstrom, but they don't as, of course, each one contains the exact same information. Of course, sometimes you don't see something in one of the sudokus that strikes you immediately in the other, and this can be helpful, but it is too rare an occurrence (for me) to bother with it. It is certainly not any faster than the standard approaches.

(4) I am very unsure about this one, but my probably very unorthodox (and probably very misguided) statistical approach revealed that there are 46,000+ ways of validly placing a given number onto the sudoku grid. Is that right? Seems like a lot.

Anyone else got any of these sort of dead-end ideas?

[coloin]

Deleted

[Ruud]

Hi,

I have been playing with these templates for quite a while now. I use them in the following way in my solver:

- Keep a list of all 46656 templates. They are stored as bit-arrays, so I can easily use them in bitwise operations.

- Maintain the remaining templates for each digit, with a double linked list.

- When a candidate for a digit is eliminated, cover all templates that contain a digit at that location.

- When a candidate for a digit is forced or pinned, cover all templates that do not contain a digit at that location.

- Overlay all remaining templates for each digit. This shows all possible placements for that digit. Candidates outside this pattern can be eliminated. This technique subsumes every kind of coloring that deals with a single digit.
It is a nice fallback if you want to test the effectiveness of coloring techniques, and to discover new patterns.

- Take 2 different digits, and compare their templates. throw out any template that has conflicts with every template for the second digit.

- Merge the 2 templates, compare to a third, then a fourth, etc, and you have a backtracking mechanism that can find all solutions. (but not as fast as DLX, so it is pretty useless...)

The only problem with templates is: What to write in the log for an elimination by templates?

Ruud.

[dukuso]

46656 1-rookeries (templates) , 1 equivalence class
419250816 2-rookeries , 170 classes
866092839552 3-rookeries , 92053(?) classes
...
46656 8-rookeries , 170 classes
1 9-rookery , 1 class


just as subsets of the 9*9.

[Red Ed]

Not quite sure about your terminology here: are there 6.67e21 9-rookeries, or just one? (That is, are the 9k cells in a k-rookery labelled with their contents or not?)

By the former definition, I worked out a while back that there are

T(0) = 1 way of laying down no digits at all
T(1) = 46656 ways of laying down all the 1s
T(2) = 838501632 ways of laying down all the 1s,2s
T(3) = 5196557037312 ways of laying down all the 1s,2s,3s
T(4) = 9631742544322560 ways of laying down all the 1s,2s,3s,4s

and then I ran out of patience, though it's obvious that the sequence ends

T(8) = 6670903752021072936960 ways of laying down all the 1s-8s
T(9) = 6670903752021072936960 ways of laying down all the 1s-9s

I was hoping at the time to see a nice rate of decay in the ratio of T(k)/T(k-1) -- because there is a decreasing amount of freedom for the choice of 9-cell template as you move through the digits -- but it wasn't looking very tidy so I gave up. My numbers could be wrong, though. [EDIT: in fact, they were (thanks Condor for spotting this). I've corrected T(3) and probably T(4) now.]

[dukuso]

one 9-rookery, contents don't matter.
I corrected my number of 3-rookeries above.
Your numbers should be at least k! times higher for k-rookeries