SudokuPX (generalised SudokuP)

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuPX (generalised SudokuP)

Postby Mathimagics » Mon Mar 05, 2018 6:18 pm

.
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
SudokuPX-8C-Example.jpg (33.14 KiB) Viewed 263 times
.
Last edited by Mathimagics on Fri Jul 27, 2018 5:21 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuPX (generalised SudokuP)

Postby tarek » Sun Mar 11, 2018 2:35 pm

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
Image

This is a solvable diamond
Image

Tarek
User avatar
tarek
 
Posts: 2687
Joined: 05 January 2006

Re: SudokuPX (generalised SudokuP)

Postby tarek » Sun Mar 11, 2018 4:16 pm

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
User avatar
tarek
 
Posts: 2687
Joined: 05 January 2006

Re: SudokuPX (generalised SudokuP)

Postby Mathimagics » Sun Mar 11, 2018 6:08 pm

.
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!
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015

Re: SudokuPX (generalised SudokuP)

Postby tarek » Sun Mar 11, 2018 6:39 pm

Mathimagics wrote: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.

Mathimagics wrote:PS: nice job on the labelling!
Thanks :D

tarek
User avatar
tarek
 
Posts: 2687
Joined: 05 January 2006

Re: SudokuPX (generalised SudokuP)

Postby Mathimagics » Sun Mar 11, 2018 7:04 pm

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


Quite right, the significance had somehow esacped me!

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


Indeed! Fascinating! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 737
Joined: 27 May 2015


Return to Sudoku variants