Skip to content

Instantly share code, notes, and snippets.

@ksze
Created November 24, 2012 04:05
Show Gist options
  • Save ksze/4138297 to your computer and use it in GitHub Desktop.
Save ksze/4138297 to your computer and use it in GitHub Desktop.
import sys
def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
class InconsistentPositionError(Exception):
pass
def still_consistent(a):
"""Check if a (partially filled) position is still consistent.
Positional argument:
1 - The 81-digit string that represents a (partially filled) sudoku position
Returns:
True - if the position is still consistent
False - if the position is not consistent
"""
# Initialize the lists of missing numbers
row_missing_numbers = list()
col_missing_numbers = list()
grd_missing_numbers = list()
for i in range(9):
row_missing_numbers.append(set('123456789'))
col_missing_numbers.append(set('123456789'))
for j in range(3):
grd_missing_numbers.append(list())
for k in range(3):
grd_missing_numbers[j].append(set('123456789'))
# Remove the numbers that are NOT missing
for l in range(81):
row_missing_numbers[l/9].discard(a[l])
col_missing_numbers[l%9].discard(a[l])
grd_missing_numbers[l/27][(l%9)/3].discard(a[l])
# Initialize the lists of excluded numbers
excluded_numbers = list()
for m in range(81):
if a[m] != '0':
excluded_numbers.append(set('123456789'))
else:
excluded_numbers.append(set())
for n in range(81):
if a[n] != '0' and (same_row(m,n) or same_col(m,n) or same_block(m,n)):
excluded_numbers[m].add(a[n])
try:
# See if any row is inconsistent
## 1. If a number is missing from a row and also excluded from every cell in
## that row, the position is inconsistent.
for o in range(9):
sets = [ excluded_numbers[o*9 + x] for x in range(9) ]
sets.append(row_missing_numbers[o])
if len(set.intersection(*sets)) > 0:
# print 'The position:'
# for x in range(9):
# print ''.join(a[x*9:x*9+9])
# print 'Row {} causes inconsistency: {}'.format(o, a[o*9:o*9+9])
# print 'Excluded numbers for row {}:'.format(o)
# for x in sets:
# print repr(x)
# print 'Row {} missing numbers: '.format(o) + repr(row_missing_numbers[o])
raise InconsistentPositionError()
## 2. If a number appears more than once in any row, the position is
## inconsistent.
for i in range(9):
present_numbers = set()
for j in range(9):
if a[i*9 + j] in present_numbers:
# print 'Row {} has duplicate numbers: {}'.format(o, a[o*9:o*9+9])
raise InconsistentPositionError()
elif a[i*9 + j] != '0':
present_numbers.add(a[i*9 + j])
# See if any column is inconsistent
## 1. If a number is missing from a column and also excluded from every cell
## in that row, the position is inconsistent.
for o in range(9):
sets = [ excluded_numbers[x*9 + o] for x in range(9) ]
sets.append(col_missing_numbers[o])
if len(set.intersection(*sets)) > 0:
# print 'Col {} causes inconsistency: {}'.format(o, [a[o + y*9] for y in range(9)])
raise InconsistentPositionError()
## 2. If a number appears more than once in any column, the position is
## inconsistent.
for i in range(9):
present_numbers = set()
for j in range(9):
if a[j*9 + i] in present_numbers:
# print 'Col {} causes inconsistency: {}'.format(o, [a[o + y*9] for y in range(9)])
raise InconsistentPositionError()
elif a[j*9 + i] != '0':
present_numbers.add(a[j*9 + i])
# See if any grid is inconsistent
## 1. If a number is missing from a column and also excluded from every cell
## in that row, the position is inconsistent.
for y in range(3):
for x in range(3):
sets = [ excluded_numbers[y*27 + x*3 + j*9 + i] for i in range(3) for j in range(3)]
sets.append(grd_missing_numbers[y][x])
if len(set.intersection(*sets)) > 0:
# print 'Grid {},{} causes inconsistency'.format(y, x)
raise InconsistentPositionError()
## 2. If a number appears more than once in any grid, the position is
## inconsistent.
for y in range(3):
for x in range(3):
present_numbers = set()
for j in range(3):
for i in range(3):
if a[y*27 + x*3 + j*9 + i] in present_numbers:
print a[y*27 + x*3 + j*9 + i]
print repr(present_numbers)
# print 'Grid {},{} has duplicate numbers'.format(y, x)
for k in range(9):
print ''.join(a[k*9:k*9+9])
raise InconsistentPositionError()
elif a[y*27 + x*3 + j*9 + i] != '0':
present_numbers.add(a[y*27 + x*3 + j*9 + i])
except InconsistentPositionError:
return False
return True
solution = None
def r(a):
"""Recursively try to solve a sudoku puzzle by filling a cell at each level of
recursion.
Positional arguments:
1 - The 81-digit string that represents a (partially filled) sudoku position
"""
# print a
global solution
i = a.find('0')
if i == -1:
solution = a
#sys.exit(a)
# print ''.join(a)
elif still_consistent(a):
excluded_numbers = set()
for j in range(81):
if same_row(i,j) or same_col(i,j) or same_block(i,j):
excluded_numbers.add(a[j])
for m in '123456789':
if m not in excluded_numbers:
# At this point, m is not excluded by any row, column, or block, so let's place it and recurse
r(a[:i]+m+a[i+1:])
if solution != None:
break;
if __name__ == '__main__':
if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
#try:
r(sys.argv[1])
if solution == None:
print 'The puzzle is unsolvable!'
else:
print 'The solution:'
for x in range(9):
print ''.join(solution[x*9:x*9+9])
#except InconsistentPositionError:
# print 'This puzzle is unsolvable!'
else:
print 'Usage: python sudoku.py puzzle'
print ' where puzzle is an 81-digit string representing the puzzle read left-to-right,'
print ' top-to-bottom, and with 0 representing a blank cell.'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment