PseuDoKu
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 4x4 grid, and one number missing from each row or column, and haven't made the logic require one-of-each-per-2x2. The other day, she asked for "1-5" instead of "1-4": since I haven't introduced her to the boxes, the fact that 5x5 cannot have the sub-boxes is irrelevant.
But the 4x4 got me thinking: just how many valid solutions of 4x4 are there? I knew it was bounded by 16!=20.9×1012. But many of those are obviously invalid or repeat solutions. 16!(4!)4=63×106, 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).
| A | B | C | D |
| CD | DC | AB | BA |
| BCD | ACD | ABD | ABC |
| BCD | ACD | ABD | ABC |
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| A | B | C | D |
| C | D | {AB} | {BA} |
| B | {AC} | * | * |
| D | {CA} | * | * |
TABLE.II| A | B | C | D |
| C | D | {AB} | {BA} |
| D | {AC} | * | * |
| B | {CA} | * | * |
TABLE.III| A | B | C | D |
| D | C | {AB} | {BA} |
| B | {AD} | * | * |
| C | {DA} | * | * |
TABLE.IV| A | B | C | D |
| D | C | {AB} | {BA} |
| C | {AD} | * | * |
| B | {DA} | * | * |
Looking at TABLE.I, and permuting, then clean up the eliminated values:
TABLE.I permutations
| A | B | C | D |
| C | D | A | B |
| B | A | ABCD | ABCD |
| D | C | ABCD | ABCD |
| A | B | C | D |
| C | D | A | B |
| B | C | ABCD | ABCD |
| D | A | ABCD | ABCD |
| A | B | C | D |
| C | D | B | A |
| B | A | ABCD | ABCD |
| D | C | ABCD | ABCD |
| A | B | C | D |
| C | D | B | A |
| B | C | ABCD | ABCD |
| D | A | ABCD | ABCD |
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.
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.
(A,B,C,D) = (1, 4, 2, 3)
