Python基础|使用Python求解数独 random|python

【Python基础|使用Python求解数独】之前学习xlrd和xlwt模块的时候，突发奇想，能不能用Python写个求解数独的小程序呢？然后找找资料，在实验楼上发现了现成的例子，然后花了一晚上，改动了一部分，自己写了一遍。（这里的数独并不满足对角线原则，试了下，把对角线的要求加进去，通过这种方法生成一个数独太耗时间了，你们要是有兴趣，可以改进下这里）
直接上程序吧，下次有空过来整理整理。

import random import itertools from copy import deepcopytest = [[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 = Nonewhile board is None: board = attmpt_board() return boarddef 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 boarddef 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 boarddef 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 Truedef 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,ydef next_pos(x,y): #返回下个位置的坐标 pos = 9 * x + y x = ((pos+1) % 81)//9 y = (pos+1) % 9 return x,ydef solve_board(board): if isfull(board): return boardwhile True: x,y = min_pos(board) nums = list_cell(board,x,y) if len(nums) == 1: board[x][y] = nums[0] else: breakx,y = min_pos(board) result = core_fun(board,x,y) return resultdef core_fun(board,x,y): if isfull(board): return boardwhile board[x][y]: x,y = next_pos(x,y)numbers = list_cell(board,x,y)if len(numbers) == 0: return Falsefor 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 FalseFullBoard = 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)

运行截图