Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Fast enough solution in Uncategorized category for Sudoku Solver by nickie
from itertools import product
from copy import deepcopy
# Three kinds of Sudoku conflicts: f in {X, Y, and S}
# If cell (i, j) has value x, then forall k, if (ti, tj) = f(i, j, k)
# it is not possible for cell (ti, tj) to have value x
def X(i, j, k):
return (k, j) # exclude same column
def Y(i, j, k):
return (i, k) # exclude same row
def S(i, j, k):
ki, kj = divmod(k, 3)
return (3*(i//3) + ki, 3*(j//3) + kj) # exclude same 3x3 square
class Sudoku:
def __init__(self, grid):
self.grid = grid
self.remaining = sum(row.count(0) for row in grid)
# possible values per cell
self.p = {(i, j): set(range(9)) for i, j in product(range(9), repeat=2)}
# update with values from the grid
for i, row in enumerate(grid):
for j, val in enumerate(row):
if val != 0: self.update(i, j, val-1)
# Update a cell's value, excluding it from all conflicting cells
def update(self, i, j, x):
for f in [X, Y, S]:
for k in range(9):
self.p[f(i, j, k)].discard(x)
self.p[i, j] = set([x])
# Find if there's just one option
def check(self, s):
n = len(s)
if n == 0: raise "deadend"
if n != 1: return 0
(i, j, x) = min(s)
if self.grid[i][j] != 0: return 0
self.update(i, j, x)
self.grid[i][j] = x+1
return 1
# Find all moves that are certain
def certain(self):
while self.remaining > 0:
changed = 0
for a, b in product(range(9), repeat=2):
# a cell where only one value goes
changed += self.check([(a, b, c) for c in self.p[a, b]])
# a row where a digit goes only to one place
changed += self.check([(a, c, b) for c in range(9)
if b in self.p[a, c]])
# a column where a digit goes only to one place
changed += self.check([(c, b, a) for c in range(9)
if a in self.p[c, b]])
# a 3x3 square where a digit goes only to one place
ai, aj = divmod(a, 3)
changed += self.check([(3*ai+ci, 3*aj+cj, b)
for ci, cj in product(range(3), repeat=2)
if b in self.p[3*ai+ci, 3*aj+cj]])
# stop if no progress
if changed == 0: break
self.remaining -= changed
# Solve a sudoku, possibly using backtracking
def checkio(grid):
stack = [Sudoku(grid)]
while stack:
s = stack.pop()
try:
s.certain()
except:
continue
if s.remaining == 0: return s.grid
best = 9
for q in product(range(9), repeat=2):
n = len(s.p[q])
if n < 2: continue
if n < best: best, cell = n, q
(i, j), options = cell, list(s.p[cell])
forked = [s] + [deepcopy(s) for i in range(1, len(options))]
n = s.remaining
for k, x in enumerate(options):
forked[k].update(i, j, x)
forked[k].grid[i][j] = x+1
forked[k].remaining = n-1
stack.append(forked[k])
Feb. 17, 2014
