I started making a generalized Sudoku puzzle creator, capable of generating puzzles of arbitrary (given) difficulty levels. The project isn’t complete, but it’s far enough along that someone more motivated could do interesting things with it.
Background: 6.001 had a Sudoku game helper project. Their initial code represents cells as lists of possible values, where “setting” a cell corresponds to giving it only one possible value. There are two “immediate” logical constraining conditions on the possible values in a cell: cells may not have values uniquely specified by other cells in their row, column, or region; and every value must be possible in each row, column, and region. These two conditions, applied repeatedly, will solve most Sudoku puzzles. My conception of “difficulty level” is exactly how many choices must be made that are not so constrained (where a value must be guessed, and then applying these methods recursively can determine if the value solves the puzzle or leads to a contradictory situation.
My code implements these two logical methods, generates Sudoku squares (it takes about 10 seconds), and can almost solve arbitrary-complexity Sudoku puzzles, returning the average difficulty rating (there’s some debugging needed, but the constituent functions could be useful without fixing my bugs). Download the base code (from the project), my “game” extensions, and the generation code.