Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Sudoku Solver by Moff
from itertools import product
def solve_sudoku(size, grid):
rows, cols = size
nx = rows * cols
xn1 = list(range(nx))
xn2 = list(range(1, nx + 1))
x = ([("rc", rc) for rc in product(xn1, xn1)] +
[("rn", rn) for rn in product(xn1, xn2)] +
[("cn", cn) for cn in product(xn1, xn2)] +
[("bn", bn) for bn in product(xn1, xn2)])
y = dict()
for r, c, n in product(xn1, xn1, xn2):
b = (r // rows) * rows + (c // cols)
y[(r, c, n)] = [
("rc", (r, c)),
("rn", (r, n)),
("cn", (c, n)),
("bn", (b, n))]
x, y = exact_cover(x, y)
for i, row in enumerate(grid):
for j, n in enumerate(row):
if n:
select(x, y, (i, j, n))
for solution in solve(x, y, []):
for (r, c, n) in solution:
grid[r][c] = n
yield grid
def exact_cover(x, y):
x = {j: set() for j in x}
for i, row in y.items():
for j in row:
x[j].add(i)
return x, y
def solve(x, y, solution):
if not x:
yield list(solution)
else:
c = min(x, key=lambda z: len(x[z]))
for r in list(x[c]):
solution.append(r)
cols = select(x, y, r)
for s in solve(x, y, solution):
yield s
deselect(x, y, r, cols)
solution.pop()
def select(x, y, r):
cols = []
for j in y[r]:
for i in x[j]:
for k in y[i]:
if k != j:
x[k].remove(i)
cols.append(x.pop(j))
return cols
def deselect(x, y, r, cols):
for j in reversed(y[r]):
x[j] = cols.pop()
for i in x[j]:
for k in y[i]:
if k != j:
x[k].add(i)
def checkio(grid):
return next(solve_sudoku((3, 3), grid))
Aug. 13, 2015
