8
$\begingroup$

Consecutive Sudoku is a variant with the additional rule that orthogonally adjacent numbers are consecutive if and only if there is a dot/bar on the line between them. A Nonconsecutive Sudoku is one with no dots; no orthogonally adjacent numbers are consecutive. I've been trying to make one recently and my normal method of checking with a solver to see whether I've made the puzzle impossible isn't working, as the "solutions" it spits out all fail the consecutiveness test.

This makes me wonder what share of Sudoku solutions are also valid for Nonconsecutive Sudoku. I know that there are 6.67 × 1021 valid Sudoku boards, ignoring symmetries/transformations. How many of those are nonconsecutive, again ignoring symmetries? (Computer help is obviously allowed for computation.)

$\endgroup$
0

2 Answers 2

5
$\begingroup$

Ignoring all symmetries, the total number of nonconsecutive sudoku grids is...

5,287,048 as enumerated via code.

This agrees with the order of magnitude in Florian's estimate.

$\endgroup$
2
  • 4
    $\begingroup$ Could you explain how the code works in the answer or by commenting it? I'm losing track of what is what with all the single-letter variable names. $\endgroup$
    – bobble
    Dec 30, 2022 at 16:54
  • 1
    $\begingroup$ @bobble The code fills the grid one cell at a time, row by row, while checking that each new value is valid, and counts the number of times the grid is filled. $\endgroup$ Dec 30, 2022 at 16:57
4
$\begingroup$

You can estimate it as follows:

I computed the number of permutations of 1..9 that are non-consecutive. I got 47622 out of 362880 permutations. That is a probability of $p = 0.13$.
For every row and every column to be non-consecutive, the probability none of them is consecutive is
$p^{18} = 1.3\times 10^{-16}$

This ignores correlation between lines and rows, but it gives a rough estimate.

Another way is to check every pair. The probability of 2 different random digits in 1..9 to be non-consecutive is $q = 28/36 = 7/9$. There are $2\times 8\times 9 = 144$ pairs to check. Assuming independence for simplicity, the overall probability of no 2 numbers consecutive is:
$q^{144} = 1.9\times 10^{-16}$

This confirms the order of magnitude.

This means that the strategy to generate a standard sudoku solution and hope for it to be non-consecutive is not practical.

$\endgroup$
1
  • 2
    $\begingroup$ This is certainly a good estimate, as my exact count puts the probability at $7.9\times 10^{-16}$ $\endgroup$ Dec 30, 2022 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.