Skip to content

Instantly share code, notes, and snippets.

@felix021 felix021/sudoku.py
Last active Aug 29, 2015

Embed
What would you like to do?
Sudoku:解数独
#!/usr/bin/python
import copy
def grid_id(x, y):
return ((x - 1) / 3 * 3) + (y - 1) / 3 + 1
class Position:
def __init__(self, x, y):
self.x = x
self.y = y
self.gid = grid_id(x, y)
self.moves = set()
self.solution = 0
def sudoku(in_board, need_all_solutions=False):
board = copy.deepcopy(in_board)
horizon = [[0] * 10 for i in range(10)]
vertical = [[0] * 10 for i in range(10)]
grid = [[0] * 10 for i in range(10)]
for i in range(9):
for j in range(9):
x, y, gid = i + 1, j + 1, grid_id(i + 1, j + 1)
t = board[i][j]
if t != 0:
horizon[x][t] = 1
vertical[y][t] = 1
grid[gid][t] = 1
todo = []
for i in range(9):
for j in range(9):
if board[i][j] == 0:
x, y, gid = i + 1, j + 1, grid_id(i + 1, j + 1)
p = Position(x, y)
for s in range(1, 10):
if horizon[x][s] + vertical[y][s] + grid[gid][s] == 0:
p.moves.add(s)
todo.append(p)
def solve(n):
if n >= len(todo):
for p in todo:
board[p.x-1][p.y-1] = p.solution
for line in board:
print line
return True
else:
remain = todo[n:]
remain.sort(key=lambda p: len(p.moves))
todo[n:] = remain
p = todo[n]
for s in p.moves:
x, y, gid = p.x, p.y, p.gid
p.solution = s
horizon[x][s] += 1
vertical[y][s] += 1
grid[gid][s] += 1
affected = []
for j in range(n + 1, len(todo)):
q = todo[j]
if q.x == x or q.y == y or q.gid == gid:
if s in q.moves:
q.moves.remove(s)
affected.append(q)
solved = solve(n + 1)
if solved == True and not need_all_solutions:
return True
for q in affected:
q.moves.add(s)
horizon[x][s] -= 1
vertical[y][s] -= 1
grid[gid][s] -= 1
return False
solve(0)
board = [
[0,0,0,0,0,0,0,0,0],
[0,9,1,0,5,2,0,0,0],
[7,0,0,0,0,9,0,0,4],
[6,0,2,0,8,0,0,0,9],
[0,0,4,1,9,0,0,0,0],
[5,0,9,0,6,0,0,0,3],
[9,4,0,0,0,5,0,0,8],
[0,5,7,0,4,8,0,0,0],
[0,0,0,0,0,0,0,0,0],
]
sudoku(board, need_all_solutions=False)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.