127 lines
4.1 KiB
Python
127 lines
4.1 KiB
Python
"""
|
|
Module to solve any Sudoku Board
|
|
Credits for Solver : http://norvig.com/sudoku.html
|
|
"""
|
|
|
|
|
|
def cross(array1, array2):
|
|
"""Cross product of elements in A and elements in B."""
|
|
return [a+b for a in array1 for b in array2]
|
|
|
|
|
|
digits = '123456789'
|
|
rows = 'ABCDEFGHI'
|
|
cols = digits
|
|
squares = cross(rows, cols)
|
|
unitlist = ([cross(rows, c) for c in cols] +
|
|
[cross(r, cols) for r in rows] +
|
|
[cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123','456','789')])
|
|
units = dict((s, [u for u in unitlist if s in u])
|
|
for s in squares)
|
|
peers = dict((s, set(sum(units[s], []))-set([s]))
|
|
for s in squares)
|
|
|
|
|
|
def parse_grid(grid):
|
|
"""Convert grid to a dict of possible values, {square: digits}, or
|
|
return False if a contradiction is detected."""
|
|
# To start, every square can be any digit; then assign values from the grid.
|
|
values = dict((s, digits) for s in squares)
|
|
for s, d in grid_values(grid).items():
|
|
if d in digits and not assign(values, s, d):
|
|
return False # (Fail if we can't assign d to square s.)
|
|
return values
|
|
|
|
|
|
def grid_values(grid):
|
|
"""Convert grid into a dict of {square: char} with '0' or '.' for empties."""
|
|
chars = [c for c in grid if c in digits or c in '0.']
|
|
assert len(chars) == 81
|
|
return dict(zip(squares, chars))
|
|
|
|
|
|
def display(values):
|
|
"""Display these values as a 2-D grid."""
|
|
width = 1+max(len(values[s]) for s in squares)
|
|
line = '+'.join(['-'*(width*3)]*3)
|
|
for r in rows:
|
|
print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
|
|
for c in cols))
|
|
if r in 'CF':
|
|
print(line)
|
|
print('')
|
|
|
|
|
|
def display_grid(grid):
|
|
"""Display these values as a 2-D grid."""
|
|
line = '+'.join(['- '*3]*3)
|
|
for i in range(9):
|
|
row = ''
|
|
for j in range(9):
|
|
row = row + grid[i*9+j] + ' '
|
|
if j == 2 or j == 5:
|
|
row = row + '|'
|
|
print(row)
|
|
if i == 2 or i == 5:
|
|
print(line)
|
|
print('')
|
|
|
|
|
|
def assign(values, s, d):
|
|
"""Eliminate all the other values (except d) from values[s] and propagate.
|
|
Return values, except return False if a contradiction is detected."""
|
|
other_values = values[s].replace(str(d), '')
|
|
if all(eliminate(values, s, d2) for d2 in other_values):
|
|
return values
|
|
else:
|
|
return False
|
|
|
|
|
|
def eliminate(values, s, d):
|
|
"""Eliminate d from values[s]; propagate when values or places <= 2.
|
|
Return values, except return False if a contradiction is detected."""
|
|
if d not in values[s]:
|
|
return values # Already eliminated
|
|
values[s] = values[s].replace(d, '')
|
|
# (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
|
|
if len(values[s]) == 0:
|
|
return False # Contradiction: removed last value
|
|
elif len(values[s]) == 1:
|
|
d2 = values[s]
|
|
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
|
|
return False
|
|
# (2) If a unit u is reduced to only one place for a value d, then put it there.
|
|
for u in units[s]:
|
|
dplaces = [s for s in u if d in values[s]]
|
|
if len(dplaces) == 0:
|
|
return False # Contradiction: no place for this value
|
|
elif len(dplaces) == 1:
|
|
# d can only be in one place in unit; assign it there
|
|
if not assign(values, dplaces[0], d):
|
|
return False
|
|
return values
|
|
|
|
|
|
#def solve(grid): return search(parse_grid(grid))
|
|
def solve(values): return search(values)
|
|
|
|
|
|
def search(values):
|
|
"""Using depth-first search and propagation, try all possible values."""
|
|
if values is False:
|
|
return False # Failed earlier
|
|
if all(len(values[s]) == 1 for s in squares):
|
|
return values # Solved!
|
|
# Chose the unfilled square s with the fewest possibilities
|
|
n, s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
|
|
return some(search(assign(values.copy(), s, d))
|
|
for d in values[s])
|
|
|
|
|
|
def some(seq):
|
|
"""Return some element of seq that is true."""
|
|
for e in seq:
|
|
if e:
|
|
return e
|
|
return False
|