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