#! /usr/bin/env python
'''Very simple sudoku solver. Based on the method outlined at:
http://www.instructables.com/id/EJLUBKN48JEPD7QXGR/?ALLSTEPS
It is stated in the comments on that page that this solver will not solve
complex sudoku puzzles where approximately < 25 numbers are on the board.
I haven't found an example of such a board yet though. All of the ones I
can find on the internets labelled "hard" have at least 27 numbers, and
they've been solvable using this code.
In any case, a simple extension would be to add a brute-force solver to the
end of the code in the case where the logic-based solver can do no more.
Version 1.0 by Richard Jones, and released
into the Public Domain.
'''
# step 1 - the board
input='''
060104050
008305600
200000001
800407006
006000300
700901004
500000002
007206900
040508070
'''
# step 2 -fill in the "Missing Grid"
board = {}
known = 0
for i,line in enumerate(input.strip().splitlines()):
for j,cell in enumerate(map(int, line.strip())):
if not cell: board[i,j] = set(range(1,10))
else:
board[i,j] = cell
known += 1
print 'Solving board, knowing %s cells'%known
def solve(board):
changed = False
for i in range(9):
for j in range(9):
num = board[i,j]
if not isinstance(num, int): continue
# step 3 - Erase "Across"
for k in range(9):
cell = board[i,k]
if isinstance(cell, set) and num in cell:
cell.remove(num)
if len(cell) == 1:
board[i,k] = cell.pop()
changed = True
# step 5 - Erase "All Around"
imaj = i/3 * 3
jmaj = j/3 * 3
for k in range(imaj, imaj + 3):
for l in range(jmaj, jmaj + 3):
cell = board[k,l]
if isinstance(cell, set) and num in cell:
cell.remove(num)
if len(cell) == 1:
board[k,l] = cell.pop()
changed = True
for j in range(9):
for i in range(9):
num = board[i,j]
if not isinstance(num, int): continue
# step 4 - Erase "Down"
for k in range(9):
cell = board[k,j]
if isinstance(cell, set) and num in cell:
cell.remove(num)
if len(cell) == 1:
board[k,j] = cell.pop()
changed = True
# step 8
for i in range(9):
for j in range(9):
cell = board[i,j]
if not isinstance(cell, set): continue
# check row for number that only appears in one block
for num in list(cell):
for k in range(9):
if k == j: continue
other_cell = board[i,k]
if isinstance(other_cell, set) and num in other_cell:
# not unique
break
if isinstance(other_cell, int) and num == other_cell:
# not unique
break
else:
board[k,j] = num
changed = True
break
# check column for number that only appears in one block
for k in range(9):
if k == i: continue
other_cell = board[k,j]
if isinstance(other_cell, set) and num in other_cell:
break
if isinstance(other_cell, int) and num == other_cell:
break
else:
board[k,j] = num
changed = True
break
# step 8 - look around a quadrant
imaj = i/3 * 3
jmaj = j/3 * 3
for k in range(imaj, imaj + 3):
for l in range(jmaj, jmaj + 3):
if (k,l) == (i,j): continue
other_cell = board[k,l]
if isinstance(other_cell, set) and num in other_cell:
break
if isinstance(other_cell, int) and num == other_cell:
break
else:
# didn't break - keep looking
continue
break
else:
board[k,j] = num
changed = True
break
return changed
def is_solved(board):
for i in range(9):
for j in range(9):
if isinstance(board[i,j], set): return False
return True
while 1:
changed = solve(board)
solved = is_solved(board)
if not changed:
break
if solved:
# display
print 'SOLVED!'
for i in range(9):
print ''.join([str(board[i,j]) for j in range(9)])
else:
print 'NOT SOLVED!'