Hi,

Mathimagics!

Last days I pondered

mathematical ways to enumerate essentially different P-Sudoku solution grids. But I didn't invent anything. So, I am forced to consider

computational approach. No Group Theory, conjugacy classes, etc.

Approx. number of essentially different P-Sudoku solution grids must be equal to "Number of different P-Sudokus sol. grids"/"Number of permitted isomorphic transformations". For this estimation we can consider isomorphic transformations, which transform

any valid P-Sudoku solution grid to another

valid P-Sudoku solution grid. So, we should consider following (group of) P-Sudoku isomorphic transformations.

1. Transposing - 2 ways.

2. Permutations of 3 bands - 6 ways.

3. Permutations of 3 stacks - 6 ways.

4. The same permutations of rows in every band - 6 ways.

5. The same permutations of columns in every stack - 6 ways.

Totally we have 2 x 6^4 = 2592 isomorphic transformations.

Therefore, there must exist around (201,105,135,151,764,480/9!)/2,592 = 213,808,581 essentially different P-Sudoku solution grids (approx.). Then we must take into account automorphisms and connecting orbits to get exact number.

First, I am going to define "P-Sudoku metric". This is ordered set of numbers, defining any P-Sudoku solution grid in

unique way, i.e. different P-Sudoku solution grids must have different metrics. Such metric should be compatible with mentioned above "P-Sudoku solution grid equivalence classes" (11 classes) to use results of the "all-different" P-Sudoku solution grids enumeration. Here is my P-Sudoku metric definition.

1. We must reduce P-Sudoku solution grid to canonical view, i.e. we must relabel B1 box to provide "right" numeration (r1: "1","2","3"; r2: "4","5","6"; r3: "7","8","9").

2. Then we should swap or not stacks B258 and B369 to provide location of digits "1" in row r2 of B2 box and in row r3 of B3 box (similarly to P-Sudoku solution grid equivalence classes). Swapping or not bands B456 and B789 must provide location of digits "1" in column c2 of B4 box and in column c3 of B7 box.

3. Now we are ready to calculate metric. First part of the metric - list of column numbers of digits "1" in a grid (row may have numbers 0,1,...,8). For example, grid's fragment

- Code: Select all
` 1 2 3 . . . . . .`

4 5 6 1 . . . . .

7 8 9 . . . 1 . .

. 1 . . . . . . .

. . . . 1 . . . .

. . . . . . . 1 .

. . 1 . . . . . .

. . . . . 1 . . .

. . . . . . . . 1

has "one's list" - (0,3,1,4,7,2,5,8).

4. In similar manner we should calculate lists for "2","3",... "9" digits. At the end we'll get 9 lists of numbers (each list contains 9 numbers).

When we compare 2 metrics (for 2 P-Sudoku solution grids) we must compare first one's lists, number by number. If a metric has higher number in the same position of the list, this metric is higher. If one's lists contain the same numbers in the same positions, we must process list for "2" digit, and so on.

Now we are ready to define "minimal form" of P-Sudoku solution grid. It is P-Sudoku with minimal metric among 2592 isomorhic images of the given P-Sudoku solution grid. We should count all P-Sudoku solution grid, having minimal form.

It turns out, that we need only to count P-Sudoku solution grid with minimal form among P-Sudoku solution grid, produced for 11 equivalence classes as it was done during all different P-Sudoku solution grid counting. Practically it means that each P-Sudoku solution grid, produced for an equivalence class, must be checked for form's minimality. If processed P-Sudoku solution grid has minimal form, we should increase "essentially different P-Sudoku solution grid's" counter and store grid for further needs. At the end we should get number slightly higher than 213,808,581. At this moment all grid's automorphisms will be taken into account.

Now we should take into account connections between orbits. We should check transformation, not belonging to P-Sudoku isomorphic transformations group. For example, we may check swapping rows in the alone band

only. If such transformation gives us valid P-Sudoku grid, then we find orbit connection. We must count connected orbits as one orbit, so "essentially different P-Sudoku solution grid's" counter, calculated at previous stage, must be decreased to account for connections. Exact set of transformation for checking connections contains 3359232/2592 = 1296 transformations. (I'll write about these transformations later.)

Finally we should get exact number of essentially different P-Sudoku solution grids.

BTW. I've just found in the thread "Su-Doku's maths" description of essentially different sudoku counting method without Group Theory, conjugacy classes, etc. (see post of

PatmaxDaddy here, dated by October 24, 2005, some his previous posts and following his discussion with

dukuso). But description is not transparent and I doubt that anyone can repeat

PatmaxDaddy's calculations.

Serg