Skip to content

Instantly share code, notes, and snippets.

@BYK
Last active April 24, 2016 00:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save BYK/f65c7debef220de26c76 to your computer and use it in GitHub Desktop.
Save BYK/f65c7debef220de26c76 to your computer and use it in GitHub Desktop.
class SudokuSolver(object):
def __init__(self, n=3):
self.n = n
self.size = self.n * self.n
self.matrix = [
[set(range(1, self.size+1)) for i in range(self.size)] for
j in range(self.size)
]
def show(self):
for i in range(self.size):
print(' '.join(str(n) for n in self.matrix[i]))
def setNum(self, y, x, n):
matrix = self.matrix
matrix[y][x] = n
# invalidate rows and columns
for i in range(self.size):
if isinstance(matrix[y][i], set):
matrix[y][i].discard(n)
for j in range(self.size):
if isinstance(matrix[j][x], set):
matrix[j][x].discard(n)
# invalidate small square
x_outer = x - (x % self.n)
y_outer = y - (y % self.n)
for i in range(y_outer, y_outer+self.n):
for j in range(x_outer, x_outer+self.n):
if isinstance(matrix[i][j], set):
matrix[i][j].discard(n)
def substitute(self):
matrix = self.matrix
count = 0
for i in range(self.size):
for j in range(self.size):
if isinstance(matrix[i][j], set) and len(matrix[i][j]) == 1:
count += 1
self.setNum(i, j, matrix[i][j].pop())
return count
def simple_solve(self):
count = 0
last = 1;
while last:
last = self.substitute()
count += last
return count
def is_only_in_box(self, y, x, n):
x_outer = x - (x % self.n)
y_outer = y - (y % self.n)
return all(
n not in self.matrix[i][j]
for j in range(x_outer, x_outer+self.n)
for i in range(y_outer, y_outer+self.n)
if (i != y or j != x) and isinstance(self.matrix[i][j], set)
)
def is_only_in_row(self, y, x, n):
return all(n not in self.matrix[y][i]
for i in range(self.size)
if i != x and isinstance(self.matrix[y][i], set)
)
def is_only_in_col(self, y, x, n):
return all(n not in self.matrix[i][x]
for i in range(self.size)
if i != y and isinstance(self.matrix[i][x], set)
)
def inductive_solve(self):
count = 0
for i in range(self.size):
for j in range(self.size):
if not isinstance(self.matrix[i][j], set): continue
for val in self.matrix[i][j]:
if (
self.is_only_in_box(i, j, val) or
self.is_only_in_row(i, j, val) or
self.is_only_in_col(i, j, val)
):
count +=1
self.setNum(i, j, val)
return count
def solve(self):
while self.simple_solve() + self.inductive_solve():
print('.', end='')
print('')
def main():
import fileinput
sdk = SudokuSolver()
y = 0
for line in fileinput.input(bufsize=10):
if not line.strip(): break
if line.startswith('#'): continue
for x in range(sdk.size):
if line[x] != '-':
sdk.setNum(y, x, int(line[x]))
y += 1
if y != sdk.size:
continue
y = 0
sdk.solve()
sdk.show()
sdk = SudokuSolver()
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment