25 May 2006

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

No comments: