Analyzing the Sudoku puzzle-solving Python program

10 years ago, Google engineer Peter Norvig wrote the Python program that solves every Sudoku puzzle, and it continues to inspire junior developers to this day. I thought it would be a good exercise of demonstrating how software engineering problems are defined and solved incrementally in programming.

In software engineering, your task is to identify the problem from business requirements, and then program a solution to the problem. The problem you formulate has very specific conditions that need to be met for it to be considered "solved". Multiple problems can exist for a set of business requirements, each of which needs their own solution programmed. Then output is passed along from the solution of one problem to the next to construct a reference program that satisfies the business requirements.

The Sudoku puzzle program, while I don't believe Google requested such a program be made, is nevertheless a great example of finding multiple problems and coding their solutions.

Identifying the problem is an important task for software engineers, more so than coding the actual solution itself. And someone who's just coding is simply a programmer, not a software engineer. Software engineers are in larger demand at job listings because of their ability to interpret program managers' requests of functionality into a blueprint that an be concretely be followed to create the actual software.

I would like to take apart the program and define each problem found.

The code is written for Python 2 but can easily be modernized using the 2to3 program.

1. Notation of a puzzle solution

From the original article:

A puzzle is solved if the squares in each unit are filled with a permutation of the digits 1 to 9.

So one requirement is that we have a way to represent a solved puzzle (and puzzles in general).

And here is the solution to that problem. A representation involving concepts that the software engineer needs to define, such as units, grid and peers. See the original article for definitions of those.

def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

digits   = '123456789'
rows     = 'ABCDEFGHI'
cols     = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
units = dict((s, [u for u in unitlist if s in u]) 
             for s in squares)
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in squares)

And part of this problem's solution, is defining how the Sudoku grid is stored:

def parse_grid(grid):
    """Convert grid to a dict of possible values, {square: digits}, or
    return False if a contradiction is detected."""
    ## To start, every square can be any digit; then assign values from the grid.
    values = dict((s, digits) for s in squares)
    for s,d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False ## (Fail if we can't assign d to square s.)
    return values

def grid_values(grid):
    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    return dict(zip(squares, chars))

2. Board constraints

On each Sudoku board with numbers on them, there exist certain combinations of rows-columns-groups that are invalid. The problem is to filter these invalid solutions.

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
    return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
    dplaces = [s for s in u if d in values[s]]
    if len(dplaces) == 0:
        return False ## Contradiction: no place for this value
    elif len(dplaces) == 1:
        # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

3. Displaying the puzzle

This should be the easiest problem to solve as you can just output characters on the terminal. A more advanced program would use a GUI library and paint lines for the board and draw numbers in between them.

def display(values):
    "Display these values as a 2-D grid."
    width = 1+max(len(values[s]) for s in squares)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print ''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols)
        if r in 'CF': print line
    print

4. Searching for a solution via intermediates

The problem here is essentially to find a sequence of intermediate boards that ultimately lead to a solved Sudoku board.

def solve(grid): return search(parse_grid(grid))

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares): 
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d)) 
        for d in values[s])

def some(seq):
    "Return some element of seq that is true."
    for e in seq:
        if e: return e
    return False

Conclusion

So we have now seen that for the simple question of "how can I solve a sudoku puzzle?" can be broken down into four different problems. Each one of them can then be tackled and implemented independently. This is an extremely useful skill to have because now you can divide the work among 4 programmers. So if you have a complicated question that can be broken down into dozens of different problems, you can leverage as many programmers as you need to implement each one.

But never forget Brooks's law: "adding manpower to a late software project makes it later". In other words, assigning more than a dozen or so programmers to solve a bunch of closely interconnected problems will make the project take longer to finish. If you have a large pool of programmers, assign them to groups of problems that do not directly depend on each other.

If you see any errors in this post, please let me know so I can correct them.