| 经典数字游戏 | 您所在的位置：网站首页 › 极限数独的讲解 › 经典数字游戏 |
经典数字游戏
|
原创文章，转载请注明出处 导语“数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。” 1 比如这个数独，左上角有1个9，则红线标出的位置都不能再填9。 总的来说，数独是一个逻辑推理的数字游戏，规则简单，上手容易，逼格高端，提神健脑，是防痴呆、防迟钝的不二神器，应该勤做多练。但是本人是甘于懒惰的，所以写一个解法，让机器自动解数独。 思路深度优先搜索，回溯搜索算法。 使用4个List，List1(9*9)按位置记录填入数独的数字，List2记录所有当前空白格的坐标，List3（9*9*9）按位置记录该位置1-9这9个数字是否可填（值为该行、该列和该宫某一数字出现的次数，比如List3[ 1 ][ 2 ][ 5 ]=3，表示第1行和第2列和(1,2)这一格所在宫共有3个5，值大于0表示该数字被占用不能填入，值等于0表示该数字未被占用可以填入），List4作为栈缓存每一次遇到分支时的List1、List2和List3。 寻找唯一解填入。唯一解是该空格只能填某一个数字，即对于List3[ i ][ j ][ x ]只有一个x（1-9中的某个数字）对应的值等于0。唯一解寻找完毕，寻找尝试解。尝试解是该空格可以有多种可能数填入。这里有一个规则是先尝试可能数少的，这样可以更快的找到答案，减少回溯次数。执行一步尝试解，List4则存入本次填数前的List1，List2，List3（要剪枝）。循环执行1、2步，遇到无尝试解时，则从List4取最后一步状态，重新继续循环，循环跳出条件为List2为空。 代码 import numpy as np from copy import deepcopy import time import xlrd import xlwt StartTime=time.time() wb=xlrd.open_workbook(r'C:\Users\Administrator\Desktop\Python\Sudoku.xlsx') sheet=wb.sheets()[0] input_tmp=[] steps=0 #记录总步数 sudoku=[] #记录填写数字 sudoku_origin=[] #记录原始数字 SudokuRecord=[] #记录尝试记录 blanks_list=[] #记录空白格坐标 SudokuNum=[[[0 for x in range(9)] for y in range(9)] for z in range(9)] #记录每格可用数字 for m in range(1,10): for n in range(1,10): if sheet.cell(m,n).value=='': input_tmp.append(0) blanks_list.append((m-1,n-1)) else: input_tmp.append(int(sheet.cell(m,n).value)) sudoku.append(input_tmp) input_tmp=[] sudoku_origin=deepcopy(sudoku) print(np.array(sudoku),'\n') def Occupy(i,j,num,mType): #占位和清除占位 global SudokuNum global blanks_list for x in range(0,7,3): #查找所在宫左上角坐标 if i>=x: m=x if j>=x: n=x for x in range(9): #同行同列 if mType==1: SudokuNum[i][x][num-1]+=1 #本行占位+1 elif mType==2: SudokuNum[i][x][num-1]-=1 #本行占位-1 if x!=i: if mType==1: SudokuNum[x][j][num-1]+=1 #本列占位+1 elif mType==2: SudokuNum[x][j][num-1]-=1 #本列占位-1 for x in range(3): #所在宫 for y in range(3): if m+x!=i and n+y!=j: if mType==1: SudokuNum[m+x][n+y][num-1]+=1 elif mType==2: SudokuNum[m+x][n+y][num-1]-=1 for m in range(9): for n in range(9): if sudoku[m][n]!=0: Occupy(m,n,sudoku[m][n],1) def CordsRecord(i,j): global blanks_list for x in range(len(blanks_list)): if blanks_list[x][0]==i and blanks_list[x][1]==j: return x break def Unique(): #唯一解 global blanks_list global SudokuNum global steps flag=False cords_list=[] #记录要删除的空白坐标下标 for cord in blanks_list: if SudokuNum[cord[0]][cord[1]].count(0)==1: for x in range(9): if SudokuNum[cord[0]][cord[1]][x]==0: sudoku[cord[0]][cord[1]]=x+1 Occupy(cord[0],cord[1],x+1,1) cords_list.append(CordsRecord(cord[0],cord[1])) flag=True steps+=1 break for x in reversed(range(len(cords_list))):#倒序删 blanks_list.pop(cords_list[x]) return flag def MinProb(): global blanks_list num=10 for x in blanks_list: if SudokuNum[x[0]][x[1]].count(0) |
【本文地址】
公司简介
联系我们