Sudoku

Tamara and I have been somewhat addicted to sudoku (that number game in a bunch of papers these days) lately. I decided to write my own sudoku puzzle generator.

It's harder than you might expect.

The basic logistics behind puzzle generation are easy enough -- start putting given numbers (givens) down randomly, enforce row/column/block constraints, backtrack when a constraint is violated. Writing this in a functional language makes this almost trivial (I used Python, which isn't what purists would consider a functional language, but it's functional enough).

What's hard is creating puzzles of a certain difficulty.

One of the rules of a sudoku puzzle is that it must have a unique solution (and not require any guessing; I believe this is a corollary to uniqueness). Standard sudoku puzzles have 81 (9x9) squares; apparently, it's not possible to have fewer than 17 givens (and generating a puzzle with this few requires days of computation). The puzzles being generated by my code have between 25-32 on average and are graded as being "easy" according to the sudoku program from that link above.

This will require more thought, but I think I'm becoming disinterested in the problem at this point.