SudokuDP (Diagonal Pairs)

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuDP (Diagonal Pairs)

Postby Mathimagics » Wed Sep 05, 2018 11:34 pm

.
SudokuDP is standard Sudoku with the additional constraint that no Diagonal-Pair (two cells diagonally adjacent) can have the same value.

I've seen this referred to as "Anti-King" Sudoku, but generally it seems to have been largely ignored. That's a shame, because it is a simple variation, it uses the standard presentation (like SudokuP). It's a bit tricky from an analytical perspective (I'll discuss this in a later post), and should yield good puzzles for P & P solvers.

It also can be used in place of the "X" variant, so we can have SudokuP-DP and SudokuW-DP puzzles to complement the SudokuP/PX and SudokuW/WX (Windoku) variants.

In fact we now have 4 variants for each category (Sudoku, SudokuP, SudokuW) since the DP and X variants can be applied together.

Here is a 14-clue example of a standard SudokuDP puzzle.

Puzzle image:
Hidden Text: Show
SudokuDP-Sample.jpg
SudokuDP-Sample.jpg (26.49 KiB) Viewed 110 times

Solution:
Hidden Text: Show
Code: Select all
  +-------+-------+-------+
  | 2 1 7 | 3 9 5 | 4 6 8 |
  | 8 4 5 | 1 6 2 | 7 3 9 |
  | 3 9 6 | 7 4 8 | 5 2 1 |
  +-------+-------+-------+
  | 7 5 3 | 8 2 1 | 9 4 6 |
  | 9 8 2 | 4 7 6 | 3 1 5 |
  | 4 6 1 | 5 3 9 | 2 8 7 |
  +-------+-------+-------+
  | 1 3 4 | 9 8 7 | 6 5 2 |
  | 6 7 8 | 2 5 4 | 1 9 3 |
  | 5 2 9 | 6 1 3 | 8 7 4 |
  +-------+-------+-------+

Puzzle text:
Code: Select all
2.......8.......3..9.7.....7......4.......3.....5.............2..8..4.......13...
Last edited by Mathimagics on Fri Sep 07, 2018 2:58 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

SudokuDP - Analysis

Postby Mathimagics » Thu Sep 06, 2018 12:04 am

.
Naturally, we would like to count the number of SudokuDP grids, the number of essentially different (ED) grids, and of course the minimum number of clues (MNC).

We have a counting problem, namely that the DP requirement is unlike normal 9-cell constraints, but affects only pairs of cells. This means that, other than rotation and reflection, there are no ways to use standard Sudoku transformations on a SudokuDP grid and obtain another SudokuDP grid (at least, not that will work on all grids).

Of course, if there does exist some non-standard transformation, I am trusting that blue will find it!

Using "1"'s templates in the traditional manner, I get 1447 valid templates, which only reduce to 706 by rotation/reflection.

I have tested 2 templates (with fixed box 1) and counted the solutions, which were 1,787,464,483 and 924,096,068. These took 10-15 minutes to run, so we won't have a final tally any time soon.

For the MNC problem, I have quickly found some 12-clue puzzles, so we might expect that 11-clue puzzles will be found.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

SudokuDP - Number of Grids

Postby Mathimagics » Thu Sep 06, 2018 10:11 am

.
Random sampling of 5 million Sudoku grids suggests that about 1 in 8000 are SudokuDP.

That would suggest, on dividing this into 18,383,222,420,692,992 (the number of different Sudoku grids up to relabelling), a figure of 2,297,902,802,586 as an estimate of the number of SudokuDP grids.

Averaging my two template counts and multiplying by 1447 (number of templates) gives 1,961,814,057,925, so both guesstimates appear to be in the same ballpark.
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: SudokuDP (Diagonal Pairs)

Postby tarek » Fri Sep 07, 2018 11:37 am

Mathimagics wrote:.
SudokuDP is standard Sudoku with the addition constraint that no Diagonal-Pair (two cells diagonally adjacent) can have the same value.

I've seen this referred to as "Anti-King" Sudoku, but generally it seems to have been largely ignored. That's a shame, because it is a simple variation, it uses the standard presentation (like SudokuP). It's a bit tricky from an analytical perspective (I'll discuss this in a later post), and should yield good puzzles for P & P solvers.

Technically focusing on diagonal pairs makes it an anti-Ferz but as orthogonal cells are covered by Latin square rules anyway; it works out as anti-King too. The King chess piece is also more familiar as it is used in the modern popular chess game.

If you remove the Latin square constraints, then the appropriate chess piece needs to be referenced!

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

Re: SudokuDP (Diagonal Pairs)

Postby Mathimagics » Fri Sep 07, 2018 3:09 pm

tarek wrote:If you remove the Latin square constraints, then the appropriate chess piece needs to be referenced!


All normal Sudoku constraints apply. We just add the diagonal pair restrictions.

What is a "Ferz"? :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015

Re: SudokuDP (Diagonal Pairs)

Postby tarek » Fri Sep 07, 2018 4:22 pm

Mathimagics wrote:
tarek wrote:If you remove the Latin square constraints, then the appropriate chess piece needs to be referenced!


All normal Sudoku constraints apply. We just add the diagonal pair restrictions.

What is a "Ferz"? :?


Call me pedantic. As you continue to use all Sudoku constraints you can use the Anti-King term and don't worry about "Ferz".

The Ferz (Farsi: Short from for "Wise Counsellor) is the an old Chess piece & the predecessor of the current Queen chess piece. It moves exactly one square diagonally in each direction. According to wikipedia the term "Ferz" is still being used in Russia & Ukraine to describe the modern day Queen chess piece. Your algorithm detects the diagonal constraints & therefore if applied alone it would constitute a Ferz move. Your algorithm doesn't need to detect the 1 square orthogonal move as it is superfluous.

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

Re: SudokuDP (Diagonal Pairs)

Postby Mathimagics » Fri Sep 07, 2018 7:48 pm

.
Ok, down with all monarchies! 8-)

I will use "anti-King" as an alias, but prefer to stick with my suffix convention, so it's SudokuDP (aka Anti-King Sudoku)
User avatar
Mathimagics
2017 Supporter
 
Posts: 760
Joined: 27 May 2015


Return to Sudoku variants