Canonical Form

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

Postby Mike Barker » Fri Jan 19, 2007 4:49 am

Thanks Glenn - I don't know where you get the time to help us all out:) . Figuring this out with all of you was as much fun as solving a Sudoku.

To summarize, the following is not a canonical form since not all puzzles can be transformed into it:
Code: Select all
|123|456|789|
|456|...|...|
|789|...|...|

There are many options for canonical forms. If the puzzle is transformed to have the smallest row order lexicographic value, then the row-normal form develops:
Code: Select all
|123|456|789|
|45.|...|...|
|...|...|...|

If, in addition, box 1 is required to be 1-9 in row order then the box-normal form develops:
Code: Select all
|123|45.|...|
|456|...|...|
|789|...|...|

where the extra "45" always occurs although not explicitly required by the definitions (braid analysis helped me to picture why).

Transformation of a puzzle into canonical form is accomplished by the following operations:
1. Permuting the three stacks (6 permuations)
2. Permuting the three bands (6 permuations)
3. Permuting the three columns within a stack (6^3 permuations)
4. Permuting the three rows within a band (6^3 permuations)
5. Transposing or 90deg rotation (2 permuations)
6. Remapping the 9 digits (9! permutations)

This allows up to 6^8*2*9!=1,218,998,108,160 arrangements (including automorphisms - identical puzzles after transformation). Actual canonicalization can be accomplished with 9*6^2*2=648 operations since the remaining cell order and digit mapping can be immediately determined:
1. Permuting the 9 boxes to box 1 (9 permutations)
2. Permuting the three columns in box 1 (6 permutations)
3. Permuting the three rows in box 1 (6 permutations)
4. Transposing or 90deg rotation (2 permutations)
Last edited by Mike Barker on Tue Jan 23, 2007 10:15 pm, edited 4 times in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby gsf » Fri Jan 19, 2007 5:14 am

Mike Barker wrote:Thanks Glenn - I don't know where you get the time to help us all out:) . Figuring this out with all of you was as much fun as solving a Sudoku.

it keeps my math chops in shape
its fun and requires an open mind
for me its easy to get stuck in details when a bigger picture view is required
and son of a gun I still need more practice to avoid off by one errors the first time around
also, some of the solver concepts go back to university work -- basically dusting off old algorithms
its amazing how exercizing one part of math/algorithms sneaks into unexpected areas
finally, about time -- the computer does most of the work
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Fri Jan 19, 2007 5:39 am

Mike Barker wrote:To summarize, the following is not a canonical form since not all puzzles can be transformed into it:
Code: Select all
|123|456|789|
|456|...|...|
|789|...|...|

...
braid analysis helped me to picture why.

Mike, excellent plausible summary. If that were a valid normalization form, every grid would need to have "traveling triples" in at least one band or stack. Although I've never seen a proof, I'm certain grids with "traveling pairs" in every band and every stack exist.

Mike Barker wrote:If the puzzle is transformed to have the smallest row order lexicographic value, then the row-normal form develops:
Code: Select all
|123|456|789|
|45.|...|...|
|...|...|...|

If, in addition, box 1 is required to be 1-9 in row order then the box-normal form develops:
Code: Select all
|123|45.|...|
|456|...|...|
|789|...|...|

where the extra "45" always occurs although not explicitly required by the definitions

I think "overall lexicographical ordering" is explicitly part of the definitions.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Smythe Dakota » Mon Jan 22, 2007 7:49 am

Mike Barker wrote:
Code: Select all
|123|456|789|
|45.|...|...|
|...|...|...|

Some readers may be wondering how you can include both 4 and 5 (in row 2) without loss of generality, but not 6 (or whatever) in the next cell.

The 4 is easy. Whatever goes in r2c1 must appear in either r1s2 or r1s3 (s stands for stack). So, just interchange stacks 2 and 3 (if necessary), and/or interchange columns within the stack.

The 5 is slightly harder to see. r2s1 must have one of the following:

(a) 3 digits in common with r1s2, and 0 in common with r1s3;
(b) 2 digits in common with r1s2, and 1 in common with r1s3;
(c) 1 digit in common with r1s2, and 2 in common with r1s3;
(d) 0 digits in common with r1s2, and 3 in common with r1s3.

Without loss of generality, (a) and (d) can be combined, since we can just interchange stacks 2 and 3 if necessary. Likewise, (b) and (c) can be combined. So we really have one of the following for r2s1:

(a) 3 digits in common with one of the other stacks, and 0 with the other;
(b) 2 digits in common with one of the other stacks, and 1 with the other.

If we now throw in the 5 in r2c2, this is still compatible with either (a) or (b), with stacks and columns interchanged if necessary to make r2s1 have either 2 or 3 digits in common with r1s2.

But now we can't throw in a 6 at r2c3, because now we would have to separate cases (a) and (b), and there we lose generality.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby coloin » Mon Jan 22, 2007 11:23 am

Code: Select all
|123|456|789|
|45.|...|...|
|...|...|...|

could we not also add another clue ?
Code: Select all
|123|456|789|
|45.|...|...|
|.8.|...|...|

All grids can be transformed into it I believe !
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Mike Barker » Mon Jan 22, 2007 3:31 pm

Bill, thanks for the proof.

As far as what more can be said about the canonical form, I don't think anything is known about r3c2. By construction r2c3 equals 6 or 7. If it equals 6 then the grid will be:
Code: Select all
|123|456|789|
|456|789|...|
|...|...|...|

If it is 7 then I'm not sure what more can be said. It appears that at least most of the time the grid will be:
Code: Select all
|123|456|789|
|457|189|...|
|...|...|...|

It's not obvious if this is always the case.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby ronk » Mon Jan 22, 2007 4:09 pm

Smythe Dakota wrote:Without loss of generality, (a) and (d) can be combined, since we can just interchange stacks 2 and 3 if necessary. Likewise, (b) and (c) can be combined. So we really have one of the following for r2s1:

(a) 3 digits in common with one of the other stacks, and 0 with the other;
(b) 2 digits in common with one of the other stacks, and 1 with the other.

If we now throw in the 5 in r2c2, this is still compatible with either (a) or (b), with stacks and columns interchanged if necessary to make r2s1 have either 2 or 3 digits in common with r1s2.

But now we can't throw in a 6 at r2c3, because now we would have to separate cases (a) and (b), and there we lose generality.

Right, (a) and (b) are the traveling triples and traveling pairs, respectively, that I referred to earlier. But I don't see how your argument is proof that some puzzles have traveling pairs in every chute.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Papy » Mon Jan 22, 2007 5:42 pm

Coloin

You have many canonical form:
Why a cannon form and how iit is make

A canon form is away to organise the clues and the digits always in the same UNIQUE way.
In fact you have to order the boxes and in each box sort the row and columns

After doing that you have the secons part sort the digits
Lokk with a bloc (band)
123 456 789
789 132 645
657 879 321


Yoy have 3 boxes that you cxan check like you want
123 321 231 312 213
Yout goal is to have always (or find) the same ordre.
In THIS sample we can identifie the box wity:
the first cell, the last, the sum of the first row....
You can choose the way you want
So when yours boxes are in the good order you have to sort them

Take a box
x x 1 you have many evrsion 1 x x 1 x x
x 3 9 9 3 x 9 x 3
x x x x x x x x x ....


So just like you explain all in the tread we have to sort row and colums
For example you choose to sort the box in the ASCENDING way by number of clue to get for example

x x x 0 clues
x x 1 1 clues
x 3 9 2 clues You can do he same for the column

x x x
x x 1
x 3 9

0 1 2 clues
You can scramble the box like you want you always get thesame final order

so the canon form for the clue of the box 1 is FOR YOU
x x x
x x 1
x 3 9
That is the first part.t he second is to detect now the swap of the digits
for example you have
1 x x
2 x 7
x x x
and
x x 1
x 3 9
x x x

So you sort the bow and after you renim the digit in he same order for example
987 so the canon box 1 will be x x x
654 x x 4
321 x 2 1
Yuu can make the sort you want renumber the digit you want you always retrouve YOUR form and compare grids
Buta box never comes alone but by 3 you have to

sort the blocs
Sort the box
Sort the roxs
Sort the column
And at end renumbe digits.

You can do this works WITHOUT solve the grid juste with the clues.
Every one use his method , his form: no matter
But it will be good that a norm appears that every one can use without to know how it's

For example when I canonize my collection I finf 118 000 , the Gordon 32636 but when Rudd or GSF canon my ciollectiion they only find 2 grids!
With a internationnal norm I will find immediatly where is the problem
A thinks that is B and B taht is A !!!
Papy
 
Posts: 131
Joined: 15 August 2006

Postby coloin » Tue Jan 23, 2007 10:11 pm

Papy I think gsf's canonisation is correct

Code: Select all
could we not also add another clue ?
|123|456|789|
|45.|...|...|
|.8.|...|...|
but this is not the smallest row order lexicographic value, what I meant was the equivalent of an 8 [ie 7 or 9] has to be in r2c3

Interestingly I have looked at a lexographic list of grids - [from gsf's 17-puzzle collection - total 36637 grids]

Code: Select all
+---+---+---+
|123|456|789|
|456|...|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+   occurred 20074 times out of 36637

+---+---+---+
|123|456|789|
|456|...|...|
|789|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+  occurred  12805  times out of 20074

+---+---+---+
|123|456|789|
|457|...|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+ occurred 16563 times out of 36637


The repeating mini-row occurs over half the time in this series
and
This 2 at r4c1 was present in all the grids !

......................................................

Aside from that all grids can be represented as Mike Barker suggests these representations are all equivalent
Code: Select all
+---+---+---+
|123|4..|...|
|456|...|...|
|789|...|4..|
+---+---+---+
|.4.|...|...|
|...|.4.|...|
|...|...|.4.|
+---+---+---+
|..4|...|...|
|...|..4|...|
|...|...|..4|
+---+---+---+

b1|b2|b3
b4|b5|b6
b7|b8|b9

b1*b5*b9*b6*b8*b2*b4*b3*b7 = 9!*9*9*4*4*2*2*1*1 = 1881169920 equivalent ways to use these clues


perhaps MB or SD could please recap where the 9! x 6^8 x 2 number comes in in this format ?
Last edited by coloin on Tue Jan 23, 2007 7:11 pm, edited 1 time in total.
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Red Ed » Tue Jan 23, 2007 11:03 pm

Let's say you have a (non-automorphic) solution grid in the format you gave. How many equivalent grids are there? Obviously it's 9! x 6^8 x 2, just by applying the whole group of transformations in turn. In deriving the 1881169920 number, you are only using a subgroup. In particular, you've not allowed yourself to switch bands (3!) or stacks (3!) around, to transpose the grid (2), or to permute rows 1-3 and cols 1-3 in a manner that selects something other than the digit 4 as the "anchor" (9). Multiply the numbers in brackets together and you get 3!x3!x2x9 = 648, which is the factor you were missing.

Put another way, there are always 648 ways to transform a solution grid into that form. It's an easy job to try all of them and then pick the lexicographically least (say) as your canonical form. That's why canonicalisation of solution grids is such an easy task.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Papy » Wed Jan 24, 2007 11:04 am

Red Ed

I think that your mail is an answer for me.
If not sorry and forget this reponse

here is my method to 14n ( Thanks Ruud the last bug is out)

Frst you searh the box (chuit?)
You swap the bloc to have it at the top of grid
After yopu swap Verticals blocs to have the the box in top left

after you sort the blocs
H: descending the number of clue by row
V: descending the numbe of clues by column
Solmve the grid
And now remap the set you want in the order you want.

I prefer row or column because of contraints
a row or Column 9
Box 6 except Box 5
This method is very speed and need the same time on every grid

Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby Mike Barker » Thu Jan 25, 2007 2:16 am

Coloin, nice observation about r4c1=2. It will always be that way because r1c2=2 therefore there must be a 2 in r4-9c1. The only constraints on the orders of these rows will be to maintain the smallest lexicographic value so the row containing the 2 in column 1 will become row 4.

Here's a complete distribution of digits based on 10000 runs so even though these results suggest that if r2c3=7 then r2c4=1 it is not a proof.

Code: Select all
Probablity of occurance for a digit within a canonical puzzle
+-----------------------------+-----------------------------+-----------------------------+
| 1-100.0 | 2-100.0 | 3-100.0 | 4-100.0 | 5-100.0 | 6-100.0 | 7-100.0 | 8-100.0 | 9-100.0 |
+-----------------------------+-----------------------------+-----------------------------+
| 4-100.0 | 5-100.0 | 6-24.00 | 1-76.00 | 8-100.0 | 9-100.0 | 1-22.51 | 2-12.47 | 1- 1.49 |
|         |         | 7-76.00 | 7-24.00 |         |         | 2-76.23 | 3-77.80 | 2-11.30 |
|         |         |         |         |         |         | 3- 0.55 | 6- 9.73 | 3-21.65 |
|         |         |         |         |         |         | 6- 0.71 |         | 6-65.56 |
+-----------------------------+-----------------------------+-----------------------------+
| 6-58.17 | 6-10.39 | 6- 7.44 | 1-11.34 | 1- 5.88 | 1- 6.78 | 1-33.89 | 1-27.74 | 1-14.37 |
| 7-22.66 | 7- 0.95 | 7- 0.39 | 2-41.36 | 2-27.04 | 2-31.60 | 4-20.27 | 4-35.36 | 4-44.37 |
| 8-15.33 | 8-55.83 | 8-28.84 | 3-27.15 | 3-41.40 | 3-31.45 | 5-40.69 | 5-25.70 | 5-33.61 |
| 9- 3.84 | 9-32.83 | 9-63.33 | 7-20.15 | 7-25.68 | 7-30.17 | 6- 5.15 | 6-11.20 | 6- 7.65 |
+-----------------------------+-----------------------------+-----------------------------+
| 2-100.0 | 1-16.13 | 1-19.48 | 1- 1.70 | 1-15.84 | 1-14.92 | 1- 5.96 | 1-11.73 | 1-14.24 |
|         | 3-22.92 | 4-19.53 | 3-13.77 | 3-11.64 | 3-13.26 | 3-18.41 | 3- 3.94 | 3-16.06 |
|         | 4-15.36 | 5-21.47 | 5-19.40 | 4-16.09 | 4-16.86 | 4-11.78 | 4-11.39 | 4- 8.99 |
|         | 6-13.80 | 6-13.25 | 6-16.79 | 6-19.78 | 5-20.41 | 5-10.59 | 5-14.84 | 5-13.29 |
|         | 7-15.24 | 7- 4.41 | 7-10.30 | 7-14.03 | 7-14.01 | 6-16.14 | 6-14.85 | 6- 5.39 |
|         | 8- 6.27 | 8-14.37 | 8-19.29 | 9-22.62 | 8-20.54 | 8-18.41 | 7-21.10 | 7-20.91 |
|         | 9-10.28 | 9- 7.49 | 9-18.75 |         |         | 9-18.71 | 9-22.15 | 8-21.12 |
+-----------------------------+-----------------------------+-----------------------------+
| 3-40.54 | 1-14.52 | 1-17.38 | 1- 2.45 | 1-14.90 | 1-16.74 | 1- 7.91 | 1-11.81 | 1-14.29 |
| 5-23.96 | 3-18.30 | 4-17.47 | 2-14.94 | 2-18.01 | 2-17.37 | 2- 5.86 | 2-21.11 | 2-22.71 |
| 6-10.01 | 4-14.62 | 5-22.68 | 3- 7.55 | 3- 5.20 | 3- 7.50 | 3-10.21 | 3- 2.42 | 3- 8.28 |
| 7-16.22 | 6-15.29 | 6-13.13 | 5-13.27 | 4-16.29 | 4-17.83 | 4-14.05 | 4-10.21 | 4- 9.53 |
| 8- 9.27 | 7-17.31 | 7- 5.60 | 6-15.45 | 6-15.36 | 5-13.19 | 5- 8.64 | 5- 9.35 | 5- 8.91 |
|         | 8- 7.76 | 8-15.06 | 7- 9.21 | 7-11.15 | 7-10.99 | 6-15.15 | 6-11.83 | 6- 3.78 |
|         | 9-12.20 | 9- 8.68 | 8-16.79 | 9-19.09 | 8-16.38 | 8-17.35 | 7-14.41 | 7-15.11 |
|         |         |         | 9-20.34 |         |         | 9-20.83 | 9-18.86 | 8-17.39 |
+-----------------------------+-----------------------------+-----------------------------+
| 5- 9.69 | 1-14.16 | 1-18.33 | 1- 2.36 | 1-16.18 | 1-14.91 | 1- 7.74 | 1-12.31 | 1-14.01 |
| 6- 7.35 | 3-18.24 | 4-18.07 | 2-14.80 | 2-18.69 | 2-16.19 | 2- 6.45 | 2-22.41 | 2-21.46 |
| 7-19.04 | 4-14.95 | 5-22.20 | 3-15.97 | 3-12.05 | 3-13.06 | 3-21.29 | 3- 4.62 | 3-14.77 |
| 8-23.73 | 6-14.76 | 6-12.41 | 5-17.76 | 4-16.58 | 4-16.35 | 4-14.29 | 4-10.48 | 4- 9.28 |
| 9-40.19 | 7-17.49 | 7- 4.69 | 6-16.70 | 6-15.92 | 5-15.97 | 5-10.81 | 5-13.34 | 5-10.23 |
|         | 8- 7.69 | 8-15.85 | 7- 8.33 | 7-11.42 | 7-10.56 | 6-16.10 | 6-12.68 | 6- 4.08 |
|         | 9-12.71 | 9- 8.45 | 8-14.04 | 9- 9.16 | 8-12.96 | 8-13.49 | 7-14.54 | 7-13.93 |
|         |         |         | 9-10.04 |         |         | 9- 9.83 | 9- 9.62 | 8-12.24 |
+-----------------------------+-----------------------------+-----------------------------+
| 3-59.46 | 1-17.54 | 1-13.76 | 1- 2.25 | 1-15.64 | 1-16.25 | 1- 7.55 | 1-12.23 | 1-14.78 |
| 5-30.85 | 3-13.80 | 2-32.60 | 2- 9.29 | 2-12.37 | 2-11.91 | 2- 3.87 | 2-14.33 | 2-15.63 |
| 6- 3.82 | 4-18.11 | 4-15.35 | 3- 4.32 | 3- 3.91 | 3- 4.96 | 3- 6.85 | 3- 1.62 | 3- 5.08 |
| 7- 5.87 | 6-15.40 | 5-12.07 | 5-13.95 | 4-16.42 | 4-16.41 | 4-13.66 | 4-10.53 | 4- 9.52 |
|         | 7-16.61 | 6-10.11 | 6-18.02 | 6-16.87 | 5-14.81 | 5- 8.78 | 5- 9.69 | 5- 9.85 |
|         | 8- 7.79 | 7- 3.38 | 7-10.26 | 7-13.04 | 7-13.36 | 6-17.15 | 6-13.56 | 6- 5.07 |
|         | 9-10.75 | 8- 8.95 | 8-20.14 | 9-21.75 | 8-22.30 | 8-20.24 | 7-17.99 | 7-19.49 |
|         |         | 9- 3.78 | 9-21.77 |         |         | 9-21.90 | 9-20.05 | 8-20.58 |
+-----------------------------+-----------------------------+-----------------------------+
| 5-35.50 | 1-19.04 | 1-15.84 | 1- 1.94 | 1-15.03 | 1-15.77 | 1- 6.88 | 1-11.60 | 1-13.90 |
| 6-15.40 | 3-13.49 | 2-33.19 | 2- 9.93 | 2-11.22 | 2-12.13 | 2- 3.78 | 2-14.85 | 2-14.90 |
| 7-24.18 | 4-17.95 | 4-14.98 | 3-15.48 | 3-11.96 | 3-15.69 | 3-20.33 | 3- 4.93 | 3-18.12 |
| 8-24.92 | 6-15.24 | 5-10.78 | 5-12.76 | 4-16.54 | 4-17.26 | 4-12.69 | 4-10.96 | 4- 9.62 |
|         | 7-16.03 | 6- 9.84 | 6-15.74 | 6-14.46 | 5-14.53 | 5- 7.18 | 5- 9.71 | 5- 9.54 |
|         | 8- 7.61 | 7- 2.88 | 7- 7.65 | 7-10.47 | 7-10.03 | 6-13.11 | 6-11.89 | 6- 4.32 |
|         | 9-10.64 | 8- 8.45 | 8-14.81 | 9-20.32 | 8-14.59 | 8-14.66 | 7-14.12 | 7-14.64 |
|         |         | 9- 4.04 | 9-21.69 |         |         | 9-21.37 | 9-21.94 | 8-14.96 |
+-----------------------------+-----------------------------+-----------------------------+
| 6- 5.25 | 1-18.61 | 1-15.21 | 1- 1.96 | 1-16.53 | 1-14.63 | 1- 7.56 | 1-12.58 | 1-12.92 |
| 7-12.03 | 3-13.25 | 2-34.21 | 2- 9.68 | 2-12.67 | 2-10.80 | 2- 3.81 | 2-14.83 | 2-14.00 |
| 8-26.75 | 4-19.01 | 4-14.60 | 3-15.76 | 3-13.84 | 3-14.08 | 3-22.36 | 3- 4.67 | 3-16.04 |
| 9-55.97 | 6-15.12 | 5-10.80 | 5-22.86 | 4-18.08 | 4-15.29 | 4-13.26 | 4-11.07 | 4- 8.69 |
|         | 7-16.37 | 6- 9.82 | 6-17.30 | 6-17.61 | 5-21.09 | 5-13.31 | 5-17.37 | 5-14.57 |
|         | 8- 7.05 | 7- 2.65 | 7-10.10 | 7-14.21 | 7-10.88 | 6-16.49 | 6-14.26 | 6- 4.15 |
|         | 9-10.59 | 8- 8.48 | 8-14.93 | 9- 7.06 | 8-13.23 | 8-15.85 | 7-17.84 | 7-15.92 |
|         |         | 9- 4.23 | 9- 7.41 |         |         | 9- 7.36 | 9- 7.38 | 8-13.71 |
+-----------------------------+-----------------------------+-----------------------------+


To summarize Ed's comments about the source of 6^8*9!*2:
Code: Select all
Transformation of a puzzle into canonical form is accomplished by the following operations:
1. Permuting the three stacks (6 permuations)
2. Permuting the three bands (6 permuations)
3. Permuting the three columns within a stack (6^3 permuations)
4. Permuting the three rows within a band (6^3 permuations)
5. Transposing or 90deg rotation (2 permuations)
6. Remapping the 9 digits (9! permutations)


Papy, my appologies, but I'm not sure I understand your posts. Are you talking about transforming a puzzle into canonical form (permutating the solution to the puzzle into a standard format - which is the focus of this thread), normalizing a puzzle (permutating the clues into some standard format), or some technique to help solve puzzles (like on your other thread?) For canonicalization you must have the solution before you start moving things around.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby JPF » Thu Jan 25, 2007 9:07 am

Interesting stats.
But you should have given all the possible digits even with low probability ; eg :
Mike Barker wrote:Here's a complete distribution of digits based on 10000 runs so even though these results suggest that if r2c3=7 then r2c4=1 it is not a proof.

here are 2 counter-examples with r2c3=7 & r2c4=2 :
Code: Select all
123456789457289613869713245235847196694132578781695324316978452578324961942561837
123456789457289163869731524291645837538927416746318295315864972674192358982573641

First one :
Code: Select all
 *-----------*
 |123|456|789|
 |457|289|613|
 |869|713|245|
 |---+---+---|
 |235|847|196|
 |694|132|578|
 |781|695|324|
 |---+---+---|
 |316|978|452|
 |578|324|961|
 |942|561|837|
 *-----------*

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Thu Jan 25, 2007 10:53 am

I think a "small" typo has mislead JPF

Great probability stats

so the 100 % clues are !
Code: Select all
+---+---+---+
|123|456|789|
|45.|.89|...|
|...|...|...|
+---+---+---+
|2..|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
Can we get 6^8*9!*2 from this
If we can it will be a proof
CC
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby JPF » Thu Jan 25, 2007 2:21 pm

Probablity of occurence for a digit within a canonical grid
Here is the first band for 10^6 runs :
Code: Select all
:
+-----------------------------+-----------------------------+-----------------------------+
| 1-100.0 | 2-100.0 | 3-100.0 | 4-100.0 | 5-100.0 | 6-100.0 | 7-100.0 | 8-100.0 | 9-100.0 |
+-----------------------------+-----------------------------+-----------------------------+
| 4-100.0 | 5-100.0 | 6-28.9  | 1-71.1  | 8-100.0 | 3-*     | 1-27.0  | 1-*     | 1- 1.9  |
|         |         | 7-71.1  | 2-*     | 9-*     | 9-100.0 | 2-72.1  | 2-14.0  | 2-13.9  |
|         |         |         | 7-28.9  |         |         | 3- 0.5  | 3-77.5  | 3-22.0  |
|         |         |         | 8-*     |         |         | 6- 0.4  | 6- 8.5  | 6-62.2  |
+-----------------------------+-----------------------------+-----------------------------+
| 6-55.0  | 6- 9.9  | 6- 6.3  | 1-14.1  | 1- 6.8  | 1- 8.0  | 1-31.2  | 1-26.3  | 1-13.7  |
|         |         |         |         |         |         | 2-*     | 2-*     | 2-*     |
| 7-27.3  | 7- 1.1  | 7- 0.5  | 2-42.1  | 2-25.1  | 2-32.7  | 4-20.0  | 4-36.3  | 4-43.9  |
| 8-14.5  | 8-57.7  | 8-27.8  | 3-25.1  | 3-43.2  | 3-31.7  | 5-42.6  | 5-24.7  | 5-32.7  |
| 9- 3.2  | 9-31.3  | 9-65.5  | 7-18.7  | 7-24.9  | 7-27.5  | 6- 6.2  | 6-13.0  | 6- 9.7  |
+-----------------------------+-----------------------------+-----------------------------+
* possible candidate but with probability <0.1%

[Edit 1, [1] was missing in r2c8 and [2] was missing in r2c4,r3c7,r3c8,r3c9]
[Edit 2, after daj's comment on r3c9=2]
[Edit 3, after Red Ed's findings on r2c456 ; see later ]


To be noted P(r7c1=3)~60%

Of course, we still have the question of unbiased grids generation...
see here

JPF
Last edited by JPF on Wed May 23, 2007 12:50 pm, edited 3 times in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to General