Last active
January 4, 2016 13:42
-
-
Save qiuchengxuan/f7a9cf73bab9335dfe06 to your computer and use it in GitHub Desktop.
simple sudoku solver
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/python | |
| # -*- coding:utf-8 -*- | |
| import sys | |
| def parse(s): | |
| return list(map(lambda c : 0 if c == ' ' else ord(c) - ord('0'), s)) | |
| board = [parse(input()) for i in range(9)] | |
| # s = input() | |
| # board = [parse(s[i * 9 : i * 9 + 9]) for i in range(9)] | |
| # input() | |
| # answer = [parse(input()) for i in range(9)] | |
| remain = [9] * 9 | |
| for x in range(9): | |
| for y in range(9): | |
| e = board[x][y] | |
| if e == 0: | |
| continue | |
| remain[e - 1] -= 1 | |
| all_remain = sys.maxsize | |
| while sum(remain) < all_remain: | |
| all_remain = sum(remain) | |
| b = [[]] * 9 | |
| for row in range(9): | |
| b[row] = list(map(lambda x: 1 if x > 0 else 0, board[row])) | |
| for row in range(9): | |
| if sum(b[row]) == 8: | |
| val = sum(range(1, 10)) - sum(board[row]) | |
| board[row][b[row].index(0)] = val | |
| remain[val - 1] -= 1 | |
| break | |
| def col_to_line(matrix, col): | |
| return list(map(lambda x: x[col], matrix)) | |
| for col in range(9): | |
| if sum(col_to_line(b, col)) == 8: | |
| val = sum(range(1, 10)) - sum(col_to_line(board, col)) | |
| board[col_to_line(b, col).index(0)][col] = val | |
| remain[val - 1] -= 1 | |
| break | |
| def block_to_line(maxtrix, index): | |
| x = index // 3 * 3 | |
| y = index % 3 * 3 | |
| return matrix[x][y : y + 3] + matrix[x + 1][y : y + 3] \ | |
| + matrix[x + 2][y : y + 3] | |
| for i in range(1, 10): | |
| if remain[i - 1] == 0: | |
| continue | |
| b = [[]] * 9 | |
| for row in range(9): | |
| if i in board[row]: # 此行有该元素，此行赋1 | |
| b[row] = [1] * 9 | |
| else: # 此行空白处赋0 | |
| b[row] = list(map(lambda x: 1 if x > 0 else 0, board[row])) | |
| for col in range(9): | |
| for row in range(9): | |
| if i != board[row][col]: | |
| continue | |
| for r in range(9): # 此列有该元素，此列赋1 | |
| b[r][col] = 1 | |
| for r in range(row // 3 * 3, row // 3 * 3 + 3): # 此块赋1 | |
| for c in range(col // 3 * 3, col // 3 * 3 + 3): | |
| b[r][c] = 1 | |
| def doit(b): | |
| for row in range(9): | |
| if sum(b[row]) == 8: | |
| return row, b[row].index(0) | |
| for col in range(9): | |
| column = list(map(lambda x: x[col], b)) | |
| if sum(column) == 8: | |
| return column.index(0), col | |
| return -1, -1 | |
| row, col = doit(b) | |
| if row != -1: | |
| board[row][col] = i | |
| remain[i - 1] -= 1 | |
| break | |
| for row in range(9): | |
| for col in range(9): | |
| if col % 3 == 0: | |
| print('|', end="") | |
| print(board[row][col], end="") | |
| print("") | |
| if row % 3 == 2: | |
| print("-") | |
| if all_remain > 0: | |
| print("remain: %s"%str(remain)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
running on python 3