Meta-sudoku, round 2

Previously on this blog: the notion of a “meta-sudoku” puzzle as a configuration of 81 squares, each labeled “filled” or “unfilled.” The goal of the puzzle is to find an assignment of numbers to the “filled” squares so that the resulting (partially filled) grid is a solvable Sudoku puzzle.

I wrote a little program to run through all the possible assignments to the following configuration:

First, I asked my program how many viable assignments existed. By “viable,” I just mean that
the assignment is unique up to permutation, and it doesn’t contain any *obvious* contradictions
out of the gate. For example: The grid below left is not viable because you can swap all the 1s
for 2s (and vice versa) to create a “lower-numbered” grid. The grid below right is not viable
because it contains an obvious contradiction: two 1s in the top row.

According to my program, there are 2,659,328,730 viable assignments. To compute just this
*number* of possible assignments, without inspecting the resulting grids for solvability, took
my program 67 seconds.

Note in passing that if we completely brute-forced it, by testing all 9^{17} possible
assignments for viability, we’d have to test 9^{17} = 16,677,181,699,666,569 assignments!
Even if we could test assignments for viability at the astonishing rate of four per nanosecond,
it would still take us *48 days* of continuous computation in order to test all 9^{17} of them.
So short-circuiting large swaths of the search space turns out to be super important here.

Now how about validating that an assignment is a valid Sudoku — which boils down to Sudoku-solving?

On my dual-core, hyperthreaded MacBook, my program can test grids for solvability at the rate
of about 50,000 grids per second. At this rate, it takes something like 15 hours of continuous
computation to inspect all 2.6 billion possible viable assignments for just this *one* meta-sudoku
configuration. So I did that — at least, long enough for it to find some solutions.

It turns out that this configuration can be filled in to create a valid Sudoku grid in at least these four fundamentally different ways:

So, in terms of my original puzzle, we would say that this particular meta-sudoku configuration
is *not* a valid meta-sudoku puzzle: there is more than one possible meta-solution. (Namely,
there are at least the four solutions above.)

How about the moose-shaped meta-sudoku?
With 24 filled squares, brute force would look at 9^{24} grids —
that’s 80 thousand billion billion.
From partial runs of my program in “counting” mode, I know it actually has somewhere between
480 billion and 87698 billion viable grids.

But my program quickly turned up many distinct *solvable* Sudoku grids for the moose configuration,
which means that the moose, too, is not a valid meta-sudoku. Here are some of the distinctly
solvable Sudokus you can form from the moose configuration:

I still don’t know if there exist any “meta-sudoku” configurations which are really “valid”
in the sense of having only *one* distinct solution. If you find one, let me know!