The New Sudoku Players' Forum

[Mathimagics]

.
The SudokuP puzzles which have been occupying much of our recent discussion are just one particular instance of a more general class of puzzles in which a 4th dimension (psets) is added to the 3 dimensions (rows, columns, boxes) of standard Sudoku.

This 4th dimension generally can be any partiton of the 81 cells into 9 psets. SudokuP partitions the grid into 9 psets, where each pset contains 9 cells that are in the same box-position. The pset mapping in this case looks like this (where cells in the same pset are assigned the same letter):

Code: Select all

   a b c | a b c | a b c
   d e f | d e f | d e f
   g h i | g h i | g h i
   ---------------------
   a b c | a b c | a b c
   d e f | d e f | d e f
   g h i | g h i | g h i
   ---------------------
   a b c | a b c | a b c
   d e f | d e f | d e f
   g h i | g h i | g h i


In SudokuPX, we extend this to arbitrary partitions of the grid into 9 disjoint sets.

One measure of interest is the number of cells whose domain is affected by a digit being assigned to any cell. Brian Taylor's BB solver calls these the associated cells. For standard Sudoku the associated cell count (ACC) is 20 (8 cells in the row, 8 in the column, and 4 in the box).

In SudokuP we have ACC = 24, since each cell has, in addition to the standard 20, affects 4 cells in the corresponding box-position, for those 4 boxes not in the same band/stack as the cell whose value is being set.

The maximum possible ACC value would seem to be 28, when each cell affects the domain of 8 cells in addition to the standard 20. This is only possible where the psets constitute a Sudoku square, ie each pset has one cell from each row, column and box.

These psets therefore form a Sudoku grid that is orthogonal to the original grid.

We might expect that puzzles with higher ACC values require less clues, and indeed this is the case. While we search for the existence (or non-existence) of 10-clue SudokuP puzzles, a search expected to weeks, if not months, to complete, it takes only a few minutes to identify 8-clue SudokuPX puzzles, and to find that there a whole swag of them. Here is just one example:

Code: Select all

         Puzzle                    Psets                    Solution
 =========================================================================

 . . . | 9 . . | . . .     a b c | e i f | g h d     3 6 8 | 9 7 5 | 4 1 2
 . . . | . . . | 7 . .     d e f | g a h | b c i     1 5 4 | 3 8 2 | 7 9 6
 . . . | . 4 . | . . .     g h i | b d c | e f a     7 9 2 | 1 4 6 | 8 3 5
 ---------------------     ---------------------     ---------------------
 . 1 . | . . . | . . .     b f a | h e i | c d g     8 1 6 | 4 2 3 | 5 7 9
 . . . | . . . | . . .     e g d | c f a | h i b     4 2 5 | 7 9 1 | 6 8 3
 . . . | 6 . . | . . .     i c h | d b g | f a e     9 3 7 | 6 5 8 | 2 4 1
 ---------------------     ---------------------     ---------------------
 . . . | . . . | . . .     h a e | f g d | i b c     5 7 3 | 8 6 9 | 1 2 4
 2 . . | . . . | . . .     c d g | i h b | a e f     2 8 1 | 5 3 4 | 9 6 7
 . . . | . . . | . 5 8     f i b | a c e | d g h     6 4 9 | 2 1 7 | 3 5 8


A suggested graphical form for these puzzles (suggestions for improvement would be welcome):

SudokuPX-8C-Example.jpg (33.14 KiB) Viewed 1312 times

.

[tarek]

The sudoku Hands variant will definitely have a high ACC even though created using 9 9-cell regions. It appears to have forced extra regions and therefore a high (indirect) ACC.

This is a variant where the clue count has gone down to the minimum 8

The regions are not as symmetric as your SudokuP and therefore (as Windoku) more tricky to program for equivalence.

This one is solvable


This is a solvable diamond


Tarek

[tarek]

For your 28 ACC for each cell variants. It is possible to search for all these templates (backtracking) and possibly check for the templates’ equivalence/isomorphism. It will be eye-pleasing to find variants which have some form of regularity/symmetry

here are my 2 attempts at a more aesthetic labelling of the regions (one is box-normal one is box and row-normal):

Code: Select all

+-------+-------+-------+
| a b c | i g h | e f d |
| d e f | c a b | h i g |
| g h i | f d e | b c a |
+-------+-------+-------+
| i g h | e f d | a b c |
| c a b | h i g | d e f |
| f d e | b c a | g h i |
+-------+-------+-------+
| e f d | a b c | i g h |
| h i g | d e f | c a b |
| b c a | g h i | f d e |
+-------+-------+-------+
+-------+-------+-------+
| a b c | d e f | g h i |
| d e f | g h i | a b c |
| g h i | a b c | d e f |
+-------+-------+-------+
| b c a | e f d | h i g |
| e f d | h i g | b c a |
| h i g | b c a | e f d |
+-------+-------+-------+
| c a b | f d e | i g h |
| f d e | i g h | c a b |
| i g h | c a b | f d e |
+-------+-------+-------+

Tarek

[Mathimagics]

.
Actually the ACC for your mostly-contiguous Psets example is surprisingly low. Here are the ACC counts (ie the excess over 20) for individual cells:

Code: Select all

 4 3 3 | 3 1 2 | 5 6 4
 6 3 3 | 3 1 2 | 5 3 3
 5 5 3 | 4 2 3 | 3 3 3
 -----------------------
 2 2 3 | 5 5 5 | 4 3 3
 1 1 2 | 5 8 5 | 2 1 1
 3 3 4 | 5 5 5 | 3 2 2
 -----------------------
 3 3 3 | 3 2 4 | 3 5 5
 3 3 5 | 2 1 3 | 3 3 6
 4 6 5 | 2 1 3 | 3 3 4


That gives an average of 3.36 per cell, so ACC is 23.36, which makes it lower than SudokuP (24).

PS: nice job on the labelling!

[tarek]

Actually the ACC for your mostly-contiguous Psets example is surprisingly low.
That gives an average of 3.36 per cell, so ACC is 23.36, which makes it lower than SudokuP (24).

hmmmm ... Thanks for the calculation. So this low ACC variant still achieved constrained 8-clue puzzles. This suggests that there are forces beyond the direct ACC that are responsible for that. This could be a separate discussion beyond the scope intended for this thread.

PS: nice job on the labelling!

Thanks

tarek

[Mathimagics]

So this low ACC variant still achieved constrained 8-clue puzzles.

Quite right, the significance had somehow esacped me!

This suggests that there are forces beyond the direct ACC that are responsible for that.

Indeed! Fascinating!