Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Use algorithm X to solve sudoku. Credits: http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
from collections import defaultdict
digits = "123456789"
constraints = defaultdict(set)
positions = {}
grids = {}
currentgrid = 0
squares = [a+b for a in digits for b in digits]
for rowgroup in ("123","456","789"):
for colgroup in ("123","456","789"):
currentgrid += 1
for row in rowgroup:
for col in colgroup:
grids[row+col] = "g{}".format(currentgrid)
def makeconstraintsandpositions():
for row in digits:
for col in digits:
for num in digits:
poshash = "{}{}{}".format(row, col, num)
rowhash = "r{}{}".format(row, num)
colhash = "c{}{}".format(col, num)
cellhash = "rc{}{}".format(row, col)
gridhash = grids[row+col] + num
positions[poshash] = [rowhash, colhash, gridhash, cellhash]
constraints[rowhash].add(poshash)
constraints[colhash].add(poshash)
constraints[cellhash].add(poshash)
constraints[gridhash].add(poshash)
return constraints, positions
def solve(constraints, positions, solution=[]):
if not constraints:
yield list(solution)
else:
c = min(constraints, key=lambda x: len(constraints[x]))
for position in constraints[c]:
solution.append(position)
cons = select(constraints, positions, position)
for s in solve(constraints, positions, solution):
yield s
deselect(constraints, positions, position, cons)
solution.pop()
def select(constraints, positions, position):
cons = []
for j in positions[position]:
for i in constraints[j]:
for k in positions[i]:
if k != j:
constraints[k].remove(i)
cons.append(constraints.pop(j))
return cons
def deselect(constraints, positions, position, cons):
for j in reversed(positions[position]):
constraints[j] = cons.pop()
for i in constraints[j]:
for k in positions[i]:
if k != j:
constraints[k].add(i)
def parse(string):
solutions = []
chars = [c for c in string if c in digits or c in "0.*"]
constraints, positions = makeconstraintsandpositions()
assert len(chars) == 81
for square, value in zip(squares, chars):
if value in digits:
select(constraints, positions, square+value)
solutions.append(square+value)
return constraints, positions, solutions
def show(positions):
sudoku = {}
for position in positions:
row, col, num = position
sudoku[row+col] = num
for row in digits:
for col in digits:
print sudoku[row+col],
print
sdk="""
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0"""
for solution in solve(*parse(sdk)):
show(solution)
print "========="
print "done"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment