Skip to content

Instantly share code, notes, and snippets.

@KorbenC
Created January 2, 2014 12:03
Show Gist options
  • Save KorbenC/8218275 to your computer and use it in GitHub Desktop.
Save KorbenC/8218275 to your computer and use it in GitHub Desktop.
Simple Sudoku solver from an interview question
#!/usr/bin/env python
class MyException(Exception):
pass
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)
def r(a):
i = a.find('0')
if i == -1:
#sys.exit(a)
raise MyException(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:
r(a[:i]+m+a[i+1:])
def display(res):
rowcount = 1
colcount = 1
print "-----------------------"
for n in res:
print n,
if colcount % 3 == 0:
print "|",
if colcount % 9 == 0:
print ""
if rowcount % 3 == 0:
print "-----------------------"
rowcount += 1
colcount += 1
def main():
if len(sys.argv) == 2:
filename = sys.argv[1]
f = open(filename)
sudoku = "".join([line.strip("\n").strip() for line in f.readlines()])
f.close()
if len(sudoku) != 81:
sys.exit("File incorrectly formatted - must contain 81 digits")
print "Input\n"
display(sudoku)
print "\n"
try:
r(sudoku)
except MyException as e:
print "Answer\n"
display(str(e))
else:
print 'Usage: python sudoku.py puzzle'
print 'where puzzle is an 81 char string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank'
if __name__ == '__main__':
status = main()
sys.exit(status)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment