I will denote this number as NR2(R, C), where the box sizes are R x C, and the corresponding grid size is N x N, where N = R x C. I will also assume, without loss of generalisation, that R ≤ C.
The value of NR2 boils down to the question: if we fix row 1 = {1, 2, ... N}, how many permutations are possible that do NOT have values (1 to C) appearing in any positions (1 to C), or values (C+1 to 2C) appearing in positions (C+1 to 2C), and so on.
This is a classic combinatorial problem (permutations with forbidden positions), which has an explicit solution:
- NR2 formula
- NR2_Formula1.png (6.05 KiB) Viewed 792 times
The values X[k] in this summation are the coefficients of (x ^ k) in P(R,C), the Rook polynomial for the given box size, after raising to the R-th power. That is, X = P(R,C) ^ R.
The rook polynomial P(R,C) for a single box (R x C) where R ≤ C is given by:
- NR2_Formula2.png (17.34 KiB) Viewed 792 times
For example: with R = C = 3 (standard Sudoku), the rook polynomial coefficients for (3 x 3) are {1, 9, 18, 6} (i.e. P(3,3) = 1 + 9x + 18x^2 + 6x^3).
After raising P(3,3) to the 3rd power, we get X[k] = { 1 , 27 , 297 , 1719 , 5670 , 10854 , 11772 , 6804 , 1944 , 216}. Plugging these into the first summation formula above gives NR2(3,3) = 12096.
Counts obtained for cases 3x3 to 6x6 are. Each NR2 value is divisible by (C! ^ R), so this is given along with the full NR2 count:
- Code: Select all
RxC NR2
---------------------------------------------------------------------------------
3x3 56 x (3! ^ 3) = 12096
3x4 1092 x (4! ^ 3) = 15095808
4x4 748521 x (4! ^ 4) = 248341303296
4x5 134631576 x (5! ^ 4) = 27917203599360000
4x6 25899377112 x (6! ^ 4) = 6960161309975838720000
5x5 2671644472544 x (5! ^ 5) = 66479063739206860800000
5x6 5752866855116280 x (6! ^ 5) = 1113132351251287958224896000000
6x6 4165949769769961828425 x (6! ^ 6) = 580375415775905260256627372851200000000
