## SudokuDP (Diagonal Pairs)

For fans of Killer Sudoku, Samurai Sudoku and other variants

### SudokuDP (Diagonal Pairs)

.
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 (26.49 KiB) Viewed 981 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.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### SudokuDP - Analysis

.
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.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### SudokuDP - Number of Grids

.
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.

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuDP (Diagonal Pairs)

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

tarek

Posts: 3761
Joined: 05 January 2006

### Re: SudokuDP (Diagonal Pairs)

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"?

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra

### Re: SudokuDP (Diagonal Pairs)

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

tarek

Posts: 3761
Joined: 05 January 2006

### Re: SudokuDP (Diagonal Pairs)

.
Ok, down with all monarchies!

I will use "anti-King" as an alias, but prefer to stick with my suffix convention, so it's SudokuDP (aka Anti-King Sudoku)

Mathimagics
2017 Supporter

Posts: 1926
Joined: 27 May 2015
Location: Canberra