The New Sudoku Players' Forum

[Mathimagics]

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


[Mathimagics]

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

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

[tarek]

.
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

[Mathimagics]

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

[tarek]

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

[Mathimagics]

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