Skip to content

Instantly share code, notes, and snippets.

@yattom
Created December 3, 2012 05:26
Show Gist options
  • Save yattom/4192943 to your computer and use it in GitHub Desktop.
Save yattom/4192943 to your computer and use it in GitHub Desktop.
Sudoku
# coding: utf-8
class Sudoku(object):
def __init__(self, initial):
self.board = {}
for col in range(9):
for row in range(9):
self.board[(col, row)] = initial[col][row]
def member_of_row(self, row):
s = set()
for col in range(9):
s.add(self.board[(col, row)])
s.discard(' ')
return s
def member_of_col(self, col):
s = set()
for row in range(9):
s.add(self.board[(col, row)])
s.discard(' ')
return s
def member_of_block(self, base_col, base_row):
s = set()
for col in range((base_col / 3) * 3, (base_col / 3) * 3 + 3):
for row in range((base_row / 3) * 3, (base_row / 3) * 3 + 3):
s.add(self.board[(col, row)])
s.discard(' ')
return s
def dump(self):
dump = ''
for col in range(9):
for row in range(9):
dump += self.board[(col, row)]
if row % 3 == 2:
dump += '|'
dump += '\n'
if col % 3 == 2:
dump += '---+---+---+\n'
return dump
def solve(self):
while self.solve_cycle():
print self.dump()
def solve_cycle(self):
for col in range(9):
for row in range(9):
if self.board[(col, row)] != ' ':
continue
s = (self.member_of_row(row).
union(self.member_of_col(col)).
union(self.member_of_block(col, row)))
remain = set('123456789').difference(s)
if len(remain) == 1:
c = remain.pop()
print "(%d, %d) [%s]"%(row, col, c)
self.board[(col, row)] = c
return True
return False
def main():
initial = [
'7 4 1',
' 14 ',
'3 1 469',
'62 581734',
'1 4 ',
'483 62195',
'837945216',
'94612 3 ',
'5128 947',
]
sudoku = Sudoku(initial)
print sudoku.dump()
sudoku.solve()
if __name__=='__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment