问题描述:数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。
解题建议:遇到问题后,最好先手工推导和模拟一下,把思路理清楚,然后再动手写代码。
参考代码:
import random
def init(): # 初始状态,每个格内都是1-9之间的数字 grids = {(r, c):list(range(1,10))\ for r in range(9) for c in range(9)} # 根据文件中的位置和数字设置数独游戏初始状态 with open('values.txt') as fp: for line in fp: line = line.strip() if line == '0': break row, col, value = map(int, line.split(',')) grids[(row,col)] = value return grids
def eachGrid(grids, row, col, value): tempValue = grids[(row,col)] # 删除不可能的数字 if isinstance(tempValue, list): if value in tempValue: tempValue.remove(value) # 如果格内只有一个数字,就拿出来填充 if len(tempValue) == 1: grids[(row,col)] = tempValue[0]
def solve(oldGrids): grids = oldGrids.copy() for r in range(9): for c in range(9): value = grids[(r,c)] if isinstance(value, int): # 处理同一列 for rr in range(9): eachGrid(grids, rr, c, value) # 处理同一行 for cc in range(9): eachGrid(grids, r, cc, value) # 处理小九宫格内的数字 rowStart = r//3 * 3 colStart = c//3 * 3 for rr in range(rowStart, rowStart+3): for cc in range(colStart, colStart+3): eachGrid(grids, rr, cc, value) elif isinstance(value, list) and len(value)==1: # 当前格内只有一个数了,拿出来填充 grids[(r,c)] = value[0] return grids
def output(grids): '''输出grids中的内容''' for row in range(9): for col in range(9): value = grids[(row,col)] if isinstance(value, int): print(grids[(row,col)], end=' ') else: print(' ', end=' ') print()
def check(grids): '''检查grids是否满足数独游戏要求''' for rc in range(9): row = {grids[(rc,c)] for c in range(9)} if len(row) != 9: return False col = {grids[(r,rc)] for r in range(9)} if len(col) != 9: return False for row in range(0,9,3): for col in range(0,9,3): value = {grids[(r,c)]\ for r in range(row,row+3)\ for c in range(col,col+3)} if len(value) != 9: return False return True
def main(oldGrids): grids = oldGrids.copy() steps = 0 while True: steps += 1 grids = solve(grids) if steps > 20: try: position = [(r,c)\ for r in range(9) for c in range(9)\ if isinstance(grids[(r,c)],list)][0] grids[position] = random.choice(grids[position]) except: grids = oldGrids.copy() steps = 0 continue if all({isinstance(grids[(r,c)], int)\ for r in range(9) for c in range(9)}): if check(grids): return grids else: # 当前选择无效,恢复原状,选择下一个 grids = oldGrids.copy() steps = 0 grids = init() output(grids) result = main(grids) print('='*30) output(result) print(check(result))
代码中使用的文本文件values.txt中内容格式,以第一行为例,0,2,9表示第0行第2列的初始数字为9:
运行结果一:
运行结果二:
运行结果三:
运行结果四: