用 Python 解数独

import random import itertools from copy import deepcopy test = [[None, None, 3, None, 6, 9, None, 1, 7], [None, 1, None, 2, 4, 8, None, None, 9], [4, None, 9, 7, 1, None, None, 2, 6], [9, 7, 2, 1, 8, 4, 6, 3, 5], [1, None, 8, None, 5, 2, 7, 9, 4], [6, 4, 5, 9, 3, 7, None, None, None], [None, 9, None, 4, None, None, 2, None, 8], [None, 6, None, 8, None, 1, None, 4, 3], [None, None, None, None, None, None, 5, 7, 1]] ''' +++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++ &&& || || 3 &&& || 6 || 9 &&& || 1 || 7 &&& +++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++ &&& || 1 || &&& 2 || 4 || 8 &&& || || 9 &&& +++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++ &&& 4 || || 9 &&& 7 || 1 || &&& || 2 || 6 &&& +++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++ &&& 9 || 7 || 2 &&& 1 || 8 || 4 &&& 6 || 3 || 5 &&& +++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++ &&& 1 || || 8 &&& || 5 || 2 &&& 7 || 9 || 4 &&& +++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++ &&& 6 || 4 || 5 &&& 9 || 3 || 7 &&& || || &&& +++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++ &&& || 9 || &&& 4 || || &&& 2 || || 8 &&& +++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++ &&& || 6 || &&& 8 || || 1 &&& || 4 || 3 &&& +++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++ &&& || || &&& || || &&& 5 || 7 || 1 &&& +++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++&&&&&++&&&&&++&&&&&+++''' def full_board(): board = None while board is None: board = attmpt_board() return board def attmpt_board(): nums = list(range(1,10)) board = [[None for _ in range(9)] for _ in range(9)] for i,j in itertools.product(range(9),repeat=2):#这个函数可以将两层甚至多层循环简写一下 i0,j0 = i - i % 3,j - j % 3 random.shuffle(nums) for x in nums: if(x not in board[i] and all(x != row[j] for row in board) and all(x not in row[j0:j0 + 3] for row in board[i0:i])): board[i][j] = x break else: return None return board def get_board(full_board,level=1): #难度等级 board = deepcopy(full_board) omit = [0,35,60,81] #挖出的方块数，因为随机挖的时候可能重复挖到某个，所以一般小于该数 for _ in range(omit[level]): i = random.randint(0,8) #随机取0——8中的一个数 j = random.randint(0,8) board[i][j] = None return board def print_board(board): spacer = '+++-----++-----++-----+++-----++-----++-----+++-----++-----++-----+++' for i in range(9): if i % 3 ==0: print(spacer.replace('-','&')) else: print(spacer) print('&&& {} || {} || {} &&& {} || {} || {} &&& {} || {} || {} &&&' .format(*(cell or ' ' for cell in board[i]))) print(spacer.replace('-','&')) def isfull(board): for i,j in itertools.product(range(9),repeat=2): if board[i][j] == None: return False return True def list_cell(board,x,y): #返回某个空格可以填入的数字的列表 nums = set(range(1,10)) row = set(board[x]) #所在的行已有的数字 col = set(row[y] for row in board) #列 x0,y0 = x - x % 3,y - y % 3 block = set(board[i][j] for i,j in itertools.product(range(x0,x0+3),range(y0,y0+3))) #块 result = nums - row - col - block return list(result) def min_pos(board): #返回最短的可填列表所在的坐标 min_,x,y = 9,-1,-1 for i,j in itertools.product(range(9),repeat=2): if board[i][j] == None: temp = len(list_cell(board,i,j)) if temp < min_: min_ = temp x,y = i,j return x,y def next_pos(x,y): #返回下个位置的坐标 pos = 9 * x + y x = ((pos+1) % 81)//9 y = (pos+1) % 9 return x,y def solve_board(board): if isfull(board): return board while True: x,y = min_pos(board) nums = list_cell(board,x,y) if len(nums) == 1: board[x][y] = nums[0] else: break x,y = min_pos(board) result = core_fun(board,x,y) return result def core_fun(board,x,y): if isfull(board): return board while board[x][y]: x,y = next_pos(x,y) numbers = list_cell(board,x,y) if len(numbers) == 0: return False for num in numbers: board[x][y] = num flag = core_fun(board,next_pos(x,y)[0],next_pos(x,y)[1])#一直往下递归 if flag == False: #递归到某个空任何数都不能填进去的时候 board[x][y] = None #因为上一步操作是让board[x][y]=n，表明赋值为n是不对的。接着往下走，取numbers中的下一个数 else: return board #board不断的在改变,直到求解出答案 #这里不好理解，这表明numbers中的所有数据用完了，还不对，怎么可能呢？ #通过上面的numbers = list_cell(board,x,y)算出来的numbers肯定是对的啊。所以肯定到不了这一步啊 #其实吧，因为这里有递归，当前层的numbers是在上一层选了一个数字之后得出的，有可能上一层选的数字就不对 #所以这里试将上一层的那个错误的数置为空 board[x][y] = None return False FullBoard = full_board() print('fullboard:\n') print_board(FullBoard) print() my_board = get_board(FullBoard,3) print('my_board:\n') print_board(my_board) result = solve_board(my_board) print('\nanswer:\n') print_board(result)