37.解数独
编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。
空白格用 '.'
表示。(左侧为题目,右侧为一个解答)
Note:
- 给定的数独序列只包含数字
1-9
和字符'.'
。 - 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9
形式的。
解题思路
9×9:看作3×3,然后每个单元又是一个3×3小块 Solution:初始化小块 big_permutations:大块中挑选组合数最少的小块, 原因在于,一旦小块确定下来,周边的小块的组合数会下降(由于限定条件增加), 加快搜索速度,确定某个组合数最少的小块,就把数字填入board, 再从剩余小块筛选组合数最少的小块,以此类推。 possible_blk:每个候选小块(有些小块已经确定,就不在候选范围内)的可能组合, 取其中组合数最少的返回,为了不浪费,生成n个生成器,不用马上那个取回所有结果, 而是先定义生成器,然后用next(生成器)来取,谁先取完,就是组合数最少的一个 small_permutations:小块的组合 比如小块中有4个空白, 每个空白可选值如下(由于块,行,列已经填入数字的限制) [['4'], ['2', '7'], ['2', '7'], ['1']] 那么可能的组合如下: ['4', '2', '7', '1'] ['4', '7', '2', '1']
代码
class Solution37(object): def solveSudoku(self, board): blk = [[board[b//3 * 3+ i//3][(b%3)*3+i%3] for i in range(9)]for b in range(9)] blank_pos = [[i for i in range(9) if blk[k][i]=='.'] for k in range(9)] blank_val = [[str(i) for i in range(1,10) if not str(i) in blk[no]] for no in range(9)] for res in self.big_permutations(board,blank_pos,blank_val): return res def big_permutations(self,board,blank_pos,blank_val,b_no=[]): no,pp = self.possible_blk(board,blank_pos,blank_val,b_no) for p3 in pp: for i in range(len(p3)): board[no//3*3 + blank_pos[no][i]//3][(no%3)*3 + blank_pos[no][i]%3] = p3[i] if len(b_no) == 8: yield board[:] else: for res in self.big_permutations(board,blank_pos,blank_val,b_no + [no]): yield res for i in range(len(p3)): board[no//3*3 + blank_pos[no][i]//3][(no%3)*3 + blank_pos[no][i]%3] = '.' def possible_blk(self,board,blank_pos,blank_val,b_no): pno_other = [i for i in range(9) if not i in b_no] p3 = [[] for i in range(9-len(b_no))] y3 = [] row = [[board[y][x] for x in range(9) if board[y][x]!='.'] for y in range(9)] col = [[board[y][x] for y in range(9) if board[y][x]!='.'] for x in range(9)] for k in range(len(p3)): no = pno_other[k] p = [0] * len(blank_pos[no]) for i in range(len(p)): y,x = no//3*3 + blank_pos[no][i]//3,(no%3)*3 + blank_pos[no][i]%3 p[i] = [m for m in blank_val[no] if not m in (row[y]+col[x])] y3.append(self.small_permutations(p)) while True: for k in range(len(p3)): try: res = next(y3[k]) p3[k].append(res) except StopIteration as e: return [pno_other[k],p3[k]] def small_permutations(self,p,per=[]): cur_floor = len(per) for pos in range(len(p[cur_floor])): t = per + [p[cur_floor][pos]] if len(set(t)) == len(t): if len(t) == len(p): yield [p[cur_floor][pos]] else: for result in self.small_permutations(p,per + [p[cur_floor][pos]]): yield [p[cur_floor][pos]] + result result = Solution37().solveSudoku([["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]) for r in result: print(r) print("-------------------------------")
在速度提高上下了功夫: