PseuDoKu Details

What I’m calling variants of sudoku, whether simplificiation of or extrapolation from the original.

My daughter enjoys playing the “number game” on my phone with me; I tell her where to put the next solved number (“put a 2 between the 5 and the 6 in that grey box”, etc.). I’ve thus started doing simpler grids on the chalkboard — with just a 4×4 grid, and one number missing from each row or column, and haven’t made the logic require one-of-each-per-2×2. The other day, she asked for “1-5” instead of “1-4”: since I haven’t introduced her to the boxes, the fact that 5×5 cannot have the sub-boxes is irrelevant.

But the 4×4 got me thinking: just how many valid solutions of 4×4 are there? I knew it was bounded by `16! = 20.9xx10^12`. But many of those are obviously invalid or repeat solutions. `(16!) / (4!)^4 = 63xx10^6`, to remove the identicals for each of the 4 numbers, is closer, but still has invalids. As a next approximation, each row (or column) will have `4!` permutations, so it’s bounded by `(4!)^4 = 331776`. Each row really has fewer combos than the row above, due to invalid rows.

I realized there will also be quite a few logically-equivalent solutions, that have different numbers, but the same relative order; this actually makes the analysis much easier. Let’s call the first four numbers chosen for the first row `(A,B,C,D)`. There are `4! = 24` permutations of the `(1,2,3,4)` into `(A,B,C,D)`. Thus, the total number of possible solutions will be 24× the number of solutions where the first row is `(A,B,C,D)`.

For the first column, there are three numbers remaining, so `3! = 6` implies there should be six permutations of the left column… but only four of those are valid columns, because “B” cannot be located in the UL box a second time. Thus, here are the four proto-tables, with fixed top-row, fixed left-column, and fixed UL-box:

TABLE.I
TABLE.II
TABLE.III
TABLE.IV


Looking at TABLE.I, and permuting, then clean up the eliminated values:

TABLE.I permutations


TABLE.I permutations, cleaned


In TABLE.I.4, there are no more valid letters for two of the cells, and two of its other cells have multiple values – in other words, that’s an invalid solution-set! It turns out, TABLE.II-.IV similarly have only three valid solutions each, four a total of `3*4=12` permutations.

TABLE.I permutations


TABLE.II Permutations


TABLE.III Permutations


TABLE.IV Permutations


Those 12 `(A,B,C,D)` tables each have the 24 permutations of `(1,2,3,4)`, for a total of 288 pseudoku4 solutions. Of course, the total number of games is much larger, because there are quite a few combinations of starting cells that will resolve to those 288 solutions.