Peter Norvig: Solving Every Sudoku Puzzle

Peter Norvig wrote up a nice Sodoku solver in Python. Here's an excerpt:

Setting Up the Problem

First we have to agree on some notation. After looking at a few Sudoku sites I notice that there is not universal agreement, but the majority favor labeling the rows A-I, the columns 1-9, and calling a collection of nine squares (either a row, a column, or a box) a unit, and calling the other squares in a unit that square's peers. We can implement this in the programming language Python as follows:

rows = 'ABCDEFGHI' cols = '123456789' digits = '123456789' squares = [r+c for r in rows for c in cols] unitlist = ([[r+c for r in rows] for c in cols] + [[r+c for c in cols] for r in rows] + [[rows[r+dr]+cols[c+dc] for dr in (0,1,2) for dc in (0,1,2)] for r in (0,3,6) for c in (0,3,6)]) units = dict((s, [u for u in unitlist if s in u]) for s in squares) peers = dict((s, set(s2 for u in units[s] for s2 in u if s2 != s)) for s in squares)

What I like about his post is that shows a clean analysis and solution to the problem, and manages to teach a bit of CS and engineering at the same time.

Read more on Peter's site: Solving Every Sudoku Puzzle