Python数独解法

数独问题怎样解决呢？数字相信大家都很熟悉，但是数独应该怎么解决呢？下面就让小编带大家一起了解吧！

数独

数独（すうどく/ Sūdoku）是一种数学逻辑游戏，游戏由9×9个格子组成，玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少17个数字使得解答谜题只有一个答案。

数独游戏通常由9个3×3个的九宫格组成。每一列、每一行和每一宫 (block) 均须包含数字1～9，不能缺少也不能重复。

解题思路

1. 筛选：对每个空单元格，根据其所在行、列、宫的已有数字，筛选出可以填入的候选数字；
2. 排序：按每个空单元格候选数字的个数进行排序；
3. 定位+填数：找到候选数字个数最少的空单元格，填入候选数字中的任意一个数；
4. 循环：重复步骤1～3，直至整张9×9矩阵非空单元格个数等于81。

Python代码

1. 定义类 sudoku 和方法 getBlocks()。sudoku类用于存放原始矩阵、宫矩阵和候选数字矩阵等。

import numpy as np
from nptyping import NDArrayclass sudoku:def __init__(self, matrix: NDArray) -> None:self.originMatrix = matrix.copy()self.matrix = Nonetry:shape = matrix.shapeexcept:passelse:if shape == (9,9):self.matrix = matrixself.numlist = list(range(1, 10))try:self.blocks = self.getBlocks()except:self.blocks = Nonetry:self.feasibleDict, self.feasibleMat = self.screen()except:self.feasibleDict = Noneself.feasibleMat = Nonedef getBlocks(self) -> dict:sep = [0, 3, 6, 9]sepTuple = [(sep[i], sep[i+1]) for i in range(len(sep)-1)]sepKey = [int(tup[0]/3) for tup in sepTuple]blocks = {}for i in range(len(sepTuple)):for j in range(len(sepTuple)):blocks[(sepKey[i], sepKey[j])] = self.matrix[sepTuple[i][0]:sepTuple[i][1], sepTuple[j][0]:sepTuple[j][1]]return blocks

2. 定义方法 filter() 用于筛选候选数字。对一个空单元格，按照所在行、列、宫已有数字，筛选可以填入的数字，返回该单元格可填数字列表。对已有数字的单元格，返回nan。

def filter(self, pos) -> list:rowNum = pos[0]colNum = pos[1]mat = self.matrixblock_r, block_c = rowNum // 3, colNum // 3block = self.blocks[(block_r, block_c)]blockUni = np.unique(block)blockNum = blockUni[blockUni > 0]if mat[rowNum, colNum] != 0:return np.nanelse:row = mat[rowNum, :]col = mat[:, colNum]rowKeep = self.numlist.copy()colKeep = self.numlist.copy()blockKeep = self.numlist.copy()for i in range(len(rowKeep)):if rowKeep[i] in row:rowKeep[i] = -1for j in range(len(colKeep)):if colKeep[j] in col:colKeep[j] = -1for k in range(len(blockKeep)):if blockKeep[k] in blockNum:blockKeep[k] = -1rowKeep = [n for n in rowKeep if n > 0]colKeep = [n for n in colKeep if n > 0]blockKeep = [n for n in blockKeep if n > 0]filterNum = list(set(blockKeep).intersection(list(set(rowKeep).intersection(set(colKeep)))))return filterNum

3. 定义 screen() 方法用于遍历所有空单元格，分别以字典和数组形式返回可填数字列表及个数。例如：

# 空单元格可填候选数字字典 (key: 空单元格位置)
{(0, 0): [3,7],(0, 1): [8],(1, 0): [1,5,9](1, 1): nan
}# 可填候选数字个数矩阵
[[2 1],
[3 0]]

4. 整合以上方法到 solve() 并填数，返回填数更新后的矩阵。

def solve(self) -> NDArray:mat = self.matrixfeasMat = self.feasibleMatfeasDict = self.feasibleDictminPos = np.argwhere(feasMat == np.min(feasMat[feasMat>0]))[0]feasNum = feasDict[minPos[0], minPos[1]]inputNum = feasNum[0]mat[minPos[0], minPos[1]] = inputNumself.matrix = matself.feasibleDict, self.feasibleMat = self.screen()return mat

5. 循环调用方法，直至满足退出条件。

while np.count_nonzero(sudoku(arr).matrix) != 81:try:Sudoku.solve()except:break

例题

数组形式（用0代表空单元格）

    arr = np.array([[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]])

完整代码

import numpy as np
from nptyping import NDArrayclass sudoku:def __init__(self, matrix: NDArray) -> None:self.originMatrix = matrix.copy()self.matrix = Nonetry:shape = matrix.shapeexcept:passelse:if shape == (9,9):self.matrix = matrixself.numlist = list(range(1, 10))try:self.blocks = self.getBlocks()except:self.blocks = Nonetry:self.feasibleDict, self.feasibleMat = self.screen()except:self.feasibleDict = Noneself.feasibleMat = Nonedef getBlocks(self) -> dict:sep = [0, 3, 6, 9]sepTuple = [(sep[i], sep[i+1]) for i in range(len(sep)-1)]sepKey = [int(tup[0]/3) for tup in sepTuple]blocks = {}for i in range(len(sepTuple)):for j in range(len(sepTuple)):blocks[(sepKey[i], sepKey[j])] = self.matrix[sepTuple[i][0]:sepTuple[i][1], sepTuple[j][0]:sepTuple[j][1]]return blocksdef filter(self, pos) -> list:rowNum = pos[0]colNum = pos[1]mat = self.matrixblock_r, block_c = rowNum // 3, colNum // 3block = self.blocks[(block_r, block_c)]blockUni = np.unique(block)blockNum = blockUni[blockUni > 0]if mat[rowNum, colNum] != 0:return np.nanelse:row = mat[rowNum, :]col = mat[:, colNum]rowKeep = self.numlist.copy()colKeep = self.numlist.copy()blockKeep = self.numlist.copy()for i in range(len(rowKeep)):if rowKeep[i] in row:rowKeep[i] = -1for j in range(len(colKeep)):if colKeep[j] in col:colKeep[j] = -1for k in range(len(blockKeep)):if blockKeep[k] in blockNum:blockKeep[k] = -1rowKeep = [n for n in rowKeep if n > 0]colKeep = [n for n in colKeep if n > 0]blockKeep = [n for n in blockKeep if n > 0]filterNum = list(set(blockKeep).intersection(list(set(rowKeep).intersection(set(colKeep)))))return filterNumdef screen(self) -> tuple:mat = self.matrixscreenDict = {}screenMat = np.zeros(mat.shape)for r in range(mat.shape[0]):for c in range(mat.shape[1]):filterNum = self.filter(pos=[r, c])screenDict[(r, c)] = filterNumif filterNum is not np.nan:screenMat[r, c] = len(filterNum)return screenDict, screenMatdef solve(self) -> NDArray:mat = self.matrixfeasMat = self.feasibleMatfeasDict = self.feasibleDictminPos = np.argwhere(feasMat == np.min(feasMat[feasMat>0]))[0]feasNum = feasDict[minPos[0], minPos[1]]inputNum = feasNum[0]mat[minPos[0], minPos[1]] = inputNumself.matrix = matself.feasibleDict, self.feasibleMat = self.screen()return matif __name__ == "__main__":arr = np.array([[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]])Sudoku = sudoku(arr)while np.count_nonzero(Sudoku.matrix) != 81:try:Sudoku.solve()except:breakprint(f"Origin:\n{Sudoku.originMatrix}\nSolved:\n{Sudoku.matrix}")

运行结果

Origin:
[[5 3 0 0 7 0 0 0 0] [6 0 0 1 9 5 0 0 0] [0 9 8 0 0 0 0 6 0] [8 0 0 0 6 0 0 0 3] [4 0 0 8 0 3 0 0 1] [7 0 0 0 2 0 0 0 6] [0 6 0 0 0 0 2 8 0] [0 0 0 4 1 9 0 0 5] [0 0 0 0 8 0 0 7 9]]
Solved:
[[5 3 4 6 7 8 9 1 2] [6 7 2 1 9 5 3 4 8] [1 9 8 3 4 2 5 6 7] [8 5 9 7 6 1 4 2 3] [4 2 6 8 5 3 7 9 1] [7 1 3 9 2 4 8 5 6] [9 6 1 5 3 7 2 8 4] [2 8 7 4 1 9 6 3 5] [3 4 5 2 8 6 1 7 9]]

大家可能会很惊讶人怎么会用Python做数独呢？但事实就是这样，小编也感到非常惊讶。

以上就是关于Python解决数独问题的事情了，大家有什么想法呢？欢迎在评论区告诉小编一起讨论哦！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！