Interesting idea, not least because Sudoku solving is a “solved problem”, and nothing sets me off like one of those. There are well-known constraint-satisfaction methods for constructing and solving Sudoku grids; there are branch-and-bound and integer programming approaches; you can even create, solve and typeset Sudoku grids by just typing a little LaTeX code. And of course Peter Norvig has shown us all how to do it in his excellent and clear pedagogic essay.
But of course all of those approaches make sense. Which is to say they’re elegant and no doubt ever so efficient and rational, but… well, they’re boring, for lack of a better term.
Zee and I paired a few months back on a preliminary experiment he’d designed, in which he was evolving solutions to fixed Sudoku puzzles. And something he said reminded me of an old unexplored notebook question regarding constraint-satisfaction puzzles generally, which I brought up. This week I’m in Cleveland working with him on his interpretation of that approach.
All the extant Sudoku solver algorithms I’m aware of rely on what you might call “serial attention” and a traditional dynamic programming architecture. That is, they scan over the initial grid in some way looking for any of a number of patterns: a block or row or column that has almost everything filled in, or a cell where two or three constraints overlap to make a number choice certain, and they fill those numbers in and start looking at the consequences. The fancy ones keep a little “stack” of what-if explorations in mind, looking not merely at the currently-obvious constraint-overlaps but also checking for conflicts and effects two or more steps into “the future”. This is in some sense the way many people actually work Sudoku: a cycle of scanning for patterns, making judicious assertions, and maybe backing out if those assertions are “tricky” (as they can be in difficult puzzle examples). And — at least in my case — probably there’s some guessing.
Very nice. We’re not doing that.
In this experiment we’re looking for distributed algorithms, a lot more like cellular automata rules, that simultaneously update the choices available to every cell in the Sudoku grid according to an (undiscovered) deterministic rule.
Here’s the way our hypothetical alien cellular fellows will “solve” a given puzzle:
- Every cell in the grid is assigned a
choice vector, which indicates which of the available digits (1 – 4 for small Sudoku, 1 – 9 for standard grids, and so on) that given cell might be at any given instant. The vectors aren’t probabilistic, just Boolean values indicating whether a cell could take a given value. If I represent these Booleans with
0for brevity, then for example in a 9x9 grid the initial
choice vectorfor any empty cell will be
111111111, and if the cell is a known hint (say a
000010000—that is, that given cell’s choices are limited to being
Answeris a script of any number of lines, each line containing exactly one
command. Commands have two parts: an
argumentis a string that refers to the relative position of some other cell within the Sudoku grid:
down, and also
ccw). A cell’s
leftneighbor is the cell in the same row, one step to the left, modulo the grid width; that is, the
leftneighbor of a cell in the left column is the cell in the same row on the right column. Similar toroidal conditions apply to
clockwiseneighbor of any cell in the grid is its preceding neighbor within its block, numbering in top-left-to-lower-right positional order, row-first. So for example, in a standard 3x3 block within a 9x9 Sudoku puzzle, the
cwneighbor of the cell in the upper right corner is the leftmost cell in the next row. The
cwneighbor of the cell in the lower right corner is the first block in the upper left, as well.
operatorrepresents a bitwise boolean operation to be carried out between the
choice vectorof the cell in question and that of the indicated
argumentcell. For example the command
"left and"applied to a given cell in the grid will replace that cell’s
choice vectorwith the result of applying bitwise
ANDto its current
choice vectorand that of its
- For each line in an
choice vectorof every cell in the grid is synchronously updated based on the current values, starting from the initial setup.
- After the last command in the
Answerhas been applied, the resulting grid is interrogated. That is, every cell is sent a
decide!message, and emits (with uniform probability) one of the choices encoded in its final
choice vector. Cells that have ended up with no remaining choices emit a
0answer, indicating they’re unable to respond.
Needless to say by this time, this is an exploratory project, not an “optimization” problem. It’s not a case of “find the most efficient algorithm to do that”, but rather “is it even feasible that this might get closer to a solution”? Our suspicion is that it might, but aside from a bit of hand-wavy discussion of “information propagating across the grid” we have no fracking idea how a general-purpose Sudoku solver might work, if it can.
In the meantime, you might already sense a few places where this scheme can be relaxed or expanded. Yes, we thought about probability vectors instead of choice vectors. Yes, we’ll start with a simple suite of
not, but we could get fancy with all 16 possible binary operators, or spread out into multiple arguments. Yes, we’re starting with a local neighborhood around each cell to begin with, but we could let the
argument of any command be a phrase of consecutive moves like
"left up left ccw". We could include access to the past state of a cell in the neighborhood definition as well. We could apply different rules to different cells at each time-step.
We have no clear idea what might happen until we give it a shot. Which will probably be the next thing we talk about.
How do we know what’s happening, and whether we think it’s good or bad?