python实现的数独算法
Python #数独 #算法2012-11-15 09:19
目前只有两个解法，对一般的数独题均能应付。从sudoku up2010上不同难度的个选了3个，其中困难的未解出，非常困难的解出一个。解题思路间代码注释部分。
sudoku.py
# _*_ coding = utf-8 _*_
def gather_col_row(row, col, sudoku):
"""收集二维数组sudoku(mxm)中元素(row, col)所在行的元素至rows中，所在列的元素至cols中"""
rows = []
cols = []
m = len(sudoku)
for i in range(m):
rows.append(sudoku[row][i])
cols.append(sudoku[i][col])
return rows, cols
def gather_block(row, col, sudoku):
"""收集二维数组sudoku(mxm)中元素(row, col)所在的宫中的元素的列表"""
blocks = []
i = row // 3
j = col // 3
for k in range(i*3, (i+1)*3):
blocks += sudoku[k][j*3 : (j+1)*3]
return blocks
def position(sudoku):
"""返回sudoku中0所在的位置(row, col),即没有数的位置的列表，如[(2,3),(0,8)]"""
return [(row, col) for row in range(9) for col in range(9) if sudoku[row][col] == 0]
def possible_dict(sudoku):
"""以字典形式返回sudoku中所有0元素位置中可能放置的数字，键为(row,col)对，值为可能数的集合，如{(2, 3):{2,4,5}}"""
digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}
ans = {}
for pos in position(sudoku):
row, col = pos
rows, cols = gather_col_row(row, col, sudoku)
blocks = gather_block(row, col, sudoku)
possible = digits - set(rows) - set(cols) - set(blocks)
ans[pos] = possible
return ans
def possible_set(row, col, sudoku):
"""以集合形式返回sudoku中(row, col)元素中可能放置的数字，如{2,4,5}"""
digits = {1, 2, 3, 4, 5, 6, 7, 8, 9}
rows, cols = gather_col_row(row, col, sudoku)
blocks = gather_block(row, col, sudoku)
possible_num = digits - set(rows) - set(cols) - set(blocks)
return possible_num
def by_row_col(seq, row_or_col):
"""按行或按列收集序列seq中的元素,row_or_col=0,按行，1，按列,用于解法二"""
row = list(set([i[row_or_col] for i in seq]))
ans = []
for r in row:
tmp = []
for s in seq:
if s[row_or_col] == r:
tmp.append(s)
ans.append(tmp)
return ans
def solve1(sudoku):
# 解法一：元素所在位置的行、列及块的交集中只有一个数的情况，也是最简单的情况 http://yige.org/
update = True
while update:
update = False
for k, v in possible_dict(sudoku).items():
if len(v) == 1:
sudoku[k[0]][k[1]] = list(v)[0]
update = True
return None
def unique(seq):
# 返回系列seq中只出现一次的数字和它的位置
# seq形如[((2,6),{9,5,6}),((2,7),{9,6}),((row,col),{possible_number})]
numbers = []
unique_num = []
for a in seq:
for i in a[1]:
numbers.append(i)
for num in numbers:
if numbers.count(num) == 1:
unique_num.append(num)
position = []
for unum in unique_num:
for a in seq:
if unum in a[1]:
position.append(a[0])
return position, unique_num
def solve2(sudoku):
# 解法二：分别按照行、按列、按块，如果某个数仅出现一次，则该位置为该数
# 如(8,8):{8,9,2,7},(8,7):{8,9,2},(8,5):{8,2},(8,1):{8,9,2},则(8,8):{7}
update = True
while update:
update = False
pos = position(sudoku)
possible = possible_dict(sudoku)
# 按行
rows = by_row_col(pos, 0)
for row in rows:
pos_num = unique([(p, possible[p]) for p in row])
if pos_num[0]:
for i in range(0, len(pos_num), 2): # pos_num中可能返回的数不止一个
sudoku[pos_num[i][0][0]][pos_num[i][0][1]] = pos_num[i+1][0]
update = True
# 按列
cols = by_row_col(pos, 1)
for col in cols:
pos_num = unique([(p, possible[p]) for p in col])
if pos_num[0]:
for i in range(0, len(pos_num), 2): # pos_num中可能返回的数不止一个
sudoku[pos_num[i][0][0]][pos_num[i][0][1]] = pos_num[i+1][0]
update = True
solve1(sudoku)
return None
if __name__ == "__main__":
"""sudoku = [[0, 0, 2, 0, 4, 0, 8, 0, 0],
[9, 5, 0, 0, 0, 0, 0, 4, 1],
[0, 0, 0, 2, 0, 3, 0, 0, 0],
[0, 6, 0, 9, 0, 5, 0, 1, 0],
[7, 0, 0, 0, 0, 0, 0, 0, 4],
[0, 3, 0, 6, 0, 4, 0, 5, 0],
[0, 0, 0, 7, 0, 6, 0, 0, 0],
[4, 7, 0, 0, 0, 0, 0, 3, 5],
[0, 0, 6, 0, 3, 0, 1, 0, 0]]"""
sudokus = []
difficulty = []
f = open('sudoku.txt', 'r')
for line in f.readlines():
line = line.strip()
if line.startswith('#'):
difficulty.append(line[1:])
else:
numbers = line.split(',')
sudoku = []
for number in numbers:
tmp = []
for num in number:
tmp.append(int(num))
sudoku.append(tmp)
sudokus.append(sudoku)
f.close()
cnt = 0
for sudoku in sudokus:
print(difficulty[cnt//3])
sdk = sudoku[:]
solve1(sudoku)
solve2(sudoku)
for i in range(9):
print(sudoku[i], " ", sdk[i])
cnt += 1
input()sudoku.txt# very easy http://yige.org 000010902,020460007,679200400,901000023,000103649,003972801,097051000,340807096,800000275 607910000,000040670,301600024,004070006,726084090,030090247,503420010,010768539,000031400 825000416,470152080,903060000,000720950,502801700,000043062,040000090,251370040,030204170 # easy 080000000,100300500,096102037,020930085,000008764,650700200,060870420,010005678,007060300 904806057,050010000,008047900,400000000,076390080,890700004,561900008,300060592,209403000 500019000,830600010,100030070,000041700,014300500,000200601,309578100,251090860,000062903 # moderate 060000009,700100030,050006000,005007000,000092054,100450600,400000763,200804910,003069042 000500002,020000900,600902350,080206000,001008004,400100000,200030089,004829013,008061070 530006094,012004070,490002065,960500000,001200480,080000000,300100700,000490501,100000008 # difficult 000000100,096200800,800000600,100082003,000140060,760050000,600400901,004020000,950001000 700040080,010080204,000005000,079000800,030604007,040030020,800000010,000860700,007100090 050031460,000090000,038060700,000000000,000100270,207500001,070000500,060020904,400800100 # very difficult 142000387,003040201,080132005,090000106,000520704,000004000,608200009,020000000,001070000 041020000,000000007,080005200,610080000,000010460,000490050,006000000,437009106,102000090 003279000,020501009,000080003,000060500,690003000,005000000,000000064,700600080,060920007
截图：
相关文章
- 那些你忽略的python性能杀手 2012/11/15
- 让Python线程支持excepthook 2012/11/14
- 制作python的exe可执行程序 2012/11/14
- Python监控引用计数 2012/11/14