My apologies, the terminology is imprecise; basically, in as optimal a way as you can brute force a solution, if one exists, relying on the simplest heuristic f

My apologies, the terminology is imprecise; basically, in as optimal a way as you can brute force a solution, if one exists, relying on the simplest heuristic for branching. The same way, really, as you'd do it by hand, if you wanted to guarantee a solution (if one exists). So, yes, a backtracking solver, a la (this is basically what Norvig did in the link someone else mentions; I implemented mine around the same time as his article was written, it looks like, as a fun college time killer, probably when Sudoku was first in vogue) - Figure out the possibility sets of all empty squares (that is, a set of all possible values given the current state of the table, i.e., for each square, initialize them with 1-9, then remove every value that is already contained in the same row, column, and 3x3, thus figuring out for each "this square could be 1 or 5, and nothing else"). Grab the square with the fewest possibilities; does it have only one? If so, go with it, update all related squares (by removing that value from their possibility set), recurse. Is it of possibilities > 1? Take one of the values out of the possibility set. Push a copy of the table as it stands (without that removed value) onto a stack; put in the taken value for the value of that square, update all related squares, and recurse. If you ever find a possibility space of zero (that is, a square has neither a value, nor any possible values), throw out your current table and pop off the stack, recursing upon that. If you find a possibility space of zero, and the stack is empty, the sudoku is unsolvable. Otherwise, once every square has a value, you're finished. I feel like I had done a little pondering on ways, while coding it up, to find better heuristics for picking what number to start with, in the event the square with the minimal number of possibilities had more than one (i.e., "this square could be 1 or 5", rather than just picking one arbitrarily, would choose one based on some criteria), but I never really got around to playing with it, as nothing took more than a few tenths of a second, and that was enough to say "there, I need never care about Sudoku"