Solve easy Sudoku (without Backtracking)

sudoku-easy.py

# Easy Sudoku Solver - No backtracking

"""
Functions for pretty printing the board
"""

# Pretty print board
def pp(a):
    r = len(a)
    for x in range(r):
        print(''.join((str(e) for e in a[x])))

# Pretty print the neighborhood of a cell
def pn(i,j):
    b = [['-' for x in range(9)] for y in range(9)]
    b[i][j] = 'O'
    for x,y in N[(i,j)]:
        b[x][y] = 'X'
    pp(b)

def box(i,j):
    # Calculate the "box number" from row and column
    return 3*(i//3) + (j//3)

def box_pairs(b):
    i = 3*(b // 3)
    j = 3*(b % 3)
    return [(i,j),(i,j+1),(i,j+2),(i+1,j),(i+1,j+1),(i+1,j+2),(i+2,j),(i+2,j+1),(i+2,j+2)]

def neighbors():
    # Generate all neighbor pairs for the 81 cells
    boxes = [box_pairs(x) for x in range(9)] # Generate all possible pairs for each "box number"
    ng = {}
    for i,j in PAIRS:
        s = set(boxes[box(i,j)]+[(i,x) for x in range(9)]+[(x,j) for x in range(9)])
        s.remove((i,j))
        ng[(i,j)] = s
    return ng

def dup(a):
    # Utility method to create duplicate of board
    return [list(a[i]) for i in range(len(a))]

def check(a):
    # Checks if Sudoku is solved
    for x in range(9):
        if REF != set(a[x]) or REF != {a[i][x] for i in range(9)} or REF != {a[i][j] for i,j in box_pairs(x)}:
            return False
    return True

def allowed(a, i, j):
    # Returns allowed values for a particular cell
    if a[i][j] != 0: # If already filled, ignore
        return set()
    s = {a[x][y] for x,y in N[(i,j)] if a[x][y] != 0} #values of neighbors
    return REF - s

def instance(a):
    # Solves easy Sudoku
    if check(a):
        return a
    s = {}
    b = dup(a)
    for i,j in PAIRS:
        e = allowed(a,i,j)
        if len(e) == 1:
            v = e.pop()
            b[i][j] = v
        s[(i,j)] = e
    if a == b:
        # If no progress has been made, return
        return b
    return instance(b)

REF = set(range(1,10)) # The Set we use to check if a row/col/box is filled correctly
PAIRS = [(i,j) for i in range(9) for j in range(9)] # Generate all pairs from 0 to 9
N = neighbors() # One time call, generate and store all possible neighbors for a cell

# A test instance
puzzle = [[5,3,0,0,7,0,0,0,0],
          [6,0,0,1,9,5,0,0,0],
          [0,9,8,0,0,0,0,6,0],
          [8,0,0,0,6,0,0,0,3],
          [4,0,0,8,0,3,0,0,1],
          [7,0,0,0,2,0,0,0,6],
          [0,6,0,0,0,0,2,8,0],
          [0,0,0,4,1,9,0,0,5],
          [0,0,0,0,8,0,0,7,9]]

# Pretty print completed Sudoku
pp(instance(puzzle))