2009 Sudoku Solver

sudoku.py

# Preetam D'Souza
# 4.24.09
# Period 7

###[ Constraint Solvers: Sudoku ]###

SIZE = 9 # 9x9

# Check method cycles through each key in the dictionary, and makes
# sure that each value (neighbor) does not have the same value as the key
def check(neighbors, colors):
    for k in neighbors.keys():
        for v in neighbors[k]:
            if colors[k] == colors[v]: # check if neighbors have same color
                return False

    return True # no neighbors have same color

# This Brute Force recursion method searches all possible territory
# coloring states by using a depth-first search through the
# state tree.
def brute(neighbors, colorlist, colors, depth):

    if depth==len(neighbors): # list fully generated
        if check(neighbors,colorlist): # good solution
            print "OKAY: %s" % colorlist
        #else: # solution fails
        #       print "NOT OKAY: %s" % colorlist

    if depth>=len(neighbors): return # base case

    for color in colors: # for each available color
        n = neighbors.keys()[depth] # the last neighbor
        colorlist[n] = color # try this color
        brute(neighbors,colorlist,colors,depth+1) #depth-first recursion

# This search method uses forward checking with a degree and minimum color choice
# heuristic. There is also backtracking implemented into the recursive algorithm.
def search(neighbors, colorlist, colors, choices, sorted, depth):

    if depth==len(neighbors): # list fully generated
        print "OKAY: %s\n" % colorlist
        for x in colorlist:
            m[x[0]][x[1]] = colorlist[x]
        return

    sorted = sort(choices,sorted)
    #print "Sorted list: %s\nChoices: %s\n" % (sorted,choices)
    n = sorted[0] # neighbor with least color choices & most connections
    for color in choices[n][0]: # for each available color for n
        colorlist[n] = color # try this color
        tmp = []
        for x in neighbors[n]: # alter neighbors
            if x not in choices: continue
            choices[x][1] -= 1 # neighbors have one less uncolored neighbor
            if x in sorted and color in choices[x][0]: # remove color from neighbors
                tmp.append(x)
                choices[x][0].remove(color)

        sorted.remove(n) # this territory has been used
        search(neighbors,colorlist,colors,choices,sorted,depth+1) #depth-first recursion
        sorted.append(n) #backtrack
        for k in tmp:
            choices[k][0].append(color)
        for x in neighbors[n]: # backtrace
            if x not in choices: continue
            choices[x][1] += 1


# Selection sort algorithm
def sort(choices,neighbors):
    max = -1
    for i in xrange(0,len(neighbors)):
        m = i
        for j in xrange(i+1,len(neighbors)):
            jcolors = len(choices[neighbors[j]][0]) # remaining choices for neighbors[j]
            mcolors = len(choices[neighbors[m]][0]) # remaining choices for neighbors[max]
            if jcolors < mcolors:
                m = j
            elif jcolors == mcolors and choices[neighbors[j]][1] > choices[neighbors[m]][1]:
                m = j
        neighbors[i], neighbors[m] = neighbors[m], neighbors[i]

    return neighbors

# display sudoku matrix
def display(matrix):
    for i in xrange(SIZE):
        print '\n'
        for j in xrange(SIZE):
            if matrix[i][j] == '-1':
                print '_'.rjust(5),
            else:
                print matrix[i][j].rjust(5),

    print '\n\n'

# File I/O
infile = open('evil.txt')
filelist = infile.read()
print "filelist=%s" % filelist
lines = filelist.split('\n')
lines = lines[:-2]
print "file by lines %s\n\n" % lines

m = [[-1]*SIZE for i in xrange(SIZE)]
for i in xrange(len(lines)):
    line = lines[i].split(',')
    for j in xrange(len(line)):
        if '\r' in line[j]: line[j] = line[j][:-1]
        m[i][j] = line[j]

print "Matrix: %s" % m

display(m)

# dictionary creation
dict = {}
for i in xrange(SIZE):
    for j in xrange(SIZE):
        if m[i][j] != '-1': continue # blank space
        k = (i,j)
        if k not in dict: dict[k] = []
        for dx in xrange(SIZE):
            vr = (i,dx) # each item in row i
            vc = (dx,j) # each item in col j
            if vr not in dict: dict[vr] = []
            if vc not in dict: dict[vc] = []
            if vr != k and vr not in dict[k]: dict[k].append(vr)
            if vc != k and vc not in dict[k]: dict[k].append(vc)
            if vr != k and k not in dict[vr]: dict[vr].append(k)
            if vc != k and k not in dict[vc]: dict[vc].append(k)

# add neighbors in each 3x3 square region
t = (1,1)
for i in xrange(3):
    r = (t[0]+3*i,t[1])
    for j in xrange(3):
        r = (r[0],t[1]+3*j)
        square = [(r[0]-1,r[1]-1),(r[0]-1,r[1]),(r[0]-1,r[1]+1),
                  (r[0]  ,r[1]-1),(r[0]  ,r[1]),(r[0]  ,r[1]+1),
                  (r[0]+1,r[1]-1),(r[0]+1,r[1]),(r[0]+1,r[1]+1)]
        for k in square:
            for v in square:
                if v == k : continue
                if v not in dict[k]: dict[k].append(v)
                if k not in dict[v]: dict[v].append(k)

# get rid of fixed places
for key in dict.keys():
    if m[key[0]][key[1]] != '-1':
        del dict[key]

print "Dictionary: %s\n\n" % dict

colors = "1 2 3 4 5 6 7 8 9".split(' ')

# create the choices dictionary
colorlist = {}
choices = {}
for x in dict.keys():
    if m[x[0]][x[1]] != '-1':
        continue
    tmp = colors*1
    for n in dict[x]:
        if m[n[0]][n[1]] in tmp:
            tmp.remove(m[n[0]][n[1]])
    choices[x] = [tmp*1,len(dict[x])] # [remaining choices, # of neighbors]
print "Color Choices and Uncolored Neighbors Dictionary: %s\n\n" % choices

sorted = sort(choices,dict.keys())
print "Sorted Neighbor List: %s\n" % sorted

# SEARCH
search(dict,colorlist,colors,choices,sorted,0)
# output solution
display(m)