Sudoku Solver

sudoku.py

#!/usr/bin/python
# 
# Takes first command line argument as path to an input file.
# Input file is expected to contain 81 numbers, with 0 
# representing empty spaces, and 1-9 representing given numbers.

from sys import argv, stdout, exit

# tries different possibilities, backtracks if necessary
def backtracking(domains, assignments, constraints):
	if len(assignments) == 81:
		return True
	next_value, minimum = 0, 100
	for value in [node for node in domains if node not in assignments]:
		if len(domains[value]) < minimum:
			minimum = len(domains[value])
			next_value = value
	for possible_value in domains[next_value]:
		for neighbor in constraints[next_value]:
			if neighbor not in assignments:
				continue
			if possible_value == assignments[neighbor]:
				break
		else:
			assignments[next_value] = possible_value
			new_domains = {}
			for domain_key in domains.keys():
				new_domains[domain_key] = domains[domain_key][:]
			for neighbor in constraints[next_value]:
				if possible_value in new_domains[neighbor]:
					new_domains[neighbor].remove(possible_value)
			if backtracking(new_domains, assignments, constraints):
				return True
			else:
				del assignments[next_value]
	return False

# prints out all of the assignments in a nice format
def printout(assignments):
	stdout.write('\n+===+===+===+===+===+===+===+===+===+\n')
	for node in xrange(81):
		if node != 0 and node % 9 == 0:
			if node % 27 == 0:
				stdout.write('|\n+===+===+===+===+===+===+===+===+===+\n')
			else:
				stdout.write('|\n+---+---+---+---+---+---+---+---+---+\n')
		stdout.write('| ')
		if node in assignments:
			stdout.write(str(assignments[node]))
		else:
			stdout.write(' ')
		stdout.write(' ')
	stdout.write('|\n+===+===+===+===+===+===+===+===+===+\n')

# arranges contraints between board squares
domains, constraints, assignments = {}, {}, {}
for node in xrange(81):
	domains[node], constraints[node] = range(1, 10), []
	row, column = node / 9, node % 9
	corner = (row - (row % 3)) * 9 + (column - (column % 3))
	for column_index in xrange(9):
		if (row * 9 + column_index) not in constraints[node]:
			constraints[node].append(row * 9 + column_index)
	for row_index in range(0, 81, 9):
		if (column + row_index) not in constraints[node]:
			constraints[node].append(column + row_index)
	for box_index in [0, 1, 2, 9, 10, 11, 18, 19, 20]:
		if (corner + box_index) not in constraints[node]:
			constraints[node].append(corner + box_index)
	constraints[node].remove(node)

# reads in puzzle, assumes 0 is unassigned space
text = map(int, list(open(argv[1]).read().replace('\n', '')))
if len(text) != 81:
	stdout.write("Invalid puzzle.\n")
	exit(0)
for node in xrange(81):
	tmp = text[node]
	if tmp == 0:
		continue
	assignments[node] = tmp
	for neighbor in constraints[node]:
		if tmp in domains[neighbor]:
			domains[neighbor].remove(tmp)
		if neighbor in assignments:
			if assignments[neighbor] == assignments[node] and neighbor != node:
				stdout.write("Invalid puzzle.\n")
				exit(0)
printout(assignments)

# calls backtracking algorithm and prints out final
backtracking(domains, assignments, constraints)
printout(assignments)

sudoku.txt

800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400