回溯法的应用：数独
回溯法的应用：数独
不可言诉的深渊
发布于 2019-07-28 13:47:55
发布于 2019-07-28 13:47:55
我之前做安卓课程设计找到课本上有一个数独游戏，当时玩的时候发现太费时间了，打算编写一个算法专门用来解数独，可是之前一直忘了这事，现在才想起来。
概述
在解数独之前首先说一下什么是数独，数独就是一个 9*9 的格子，每一个格子是数字 1~9 中的任意一个，要确保其所在的行，所在的列，所在的块（每个 3*3 的块，这样的块一共有 9 个）中都没有重复的数字。
解数独的方法我们首先能够想到的应该就是回溯法吧，没冲突就填上，填到半路发现没法填了就回溯。下面来说一下回溯法解数独的具体步骤。
- 获取数独的最初状态。
- 找到第一个未填项，填入没有冲突的数字，当填完第 i 个未填项之后，第 i+1 个未填项无法填入数字时，回溯到第 i 个，重复之前的操作，直到全部填完。
是不是很简单？为了把数据和基于数据的操作封装在一起，依旧使用面向对象来实现。
初始化
在这个算法中，我们需要获取数独的初始状态，数独的初始状态很简单，一个 9 行 9 列的二维数组，其中未填项是 0。我们直接把这个二维数组作为参数赋值给数独类的实例的属性即可。
def __init__(self, initial_state):
"""
初始化
:param initial_state: 初始状态
"""
self.state = initial_state检测冲突
在编写解数独的算法之前，我们首先需要一个方法来检测当前位置的当前值是不是有冲突，这个算法很简单，如果其所在的行，所在的列，所在的块中有重复的数字，就有冲突，否则没有冲突。
def conflict(self, row, column, value):
"""
检测冲突
:param row: 当前值所在的行
:param column: 当前值所在的列
:param value: 当前值
:return: 有冲突返回 True，无冲突返回 False
"""
for item in self.state[row]:
if item == value:
return True
for row0 in self.state:
if row0[column] == value:
return True
row0, column0 = row//3*3, column//3*3
block = self.state[row0][column0:column0+3]+self.state[row0+1][column0:column0+3] + \
self.state[row0+2][column0:column0+3]
for item in block:
if item == value:
return True
return False获取下一个未填项
获取下一个未填项就是获取二维数组中第一个元素为 0 的行和列，如果没有元素为 0，就返回两个 -1（正常的情况下，返回两个值——行和列，如果在这里返回一个值可能会出现解包错误）。
def get_next(self, row, column):
"""
获取下一个未填项
:param row: 当前行
:param column: 当前列
:return: 下一个未填项的行，下一个未填项的列
"""
for next_column in range(column+1, 9):
if self.state[row][next_column] == 0:
return row, next_column
for next_row in range(row+1, 9):
for next_column in range(9):
if self.state[next_row][next_column] == 0:
return next_row, next_column
return -1, -1算当前未填项
如果当前项是 0，也就是需要给它填上一个非 0 数字，填上的数字要和其所在的行，所在的列，所在的块没有冲突，如果有冲突换一个数，填到半路没法继续填就回溯。
def solve(self, row, column):
"""
解当前未填项
:param row: 当前未填项所在的行
:param column: 当前未填项所在的列
:return: 如果填满就返回 True，否则递归直到填满
"""
if self.state[row][column] == 0:
for value in range(1, 10):
if not self.conflict(row, column, value):
self.state[row][column] = value
next_row, next_column = self.get_next(row, column)
if next_row == -1:
return True
else:
end = self.solve(next_row, next_column)
if not end:
self.state[row][column] = 0
else:
return True运行整个算法
运行整个算法很简单，找到第一个未填项进行填写就行了。
def run(self):
"""
运行整个算法
:return:
"""
if self.state[0][0] == 0:
self.solve(0, 0)
else:
row, column = self.get_next(0, 0)
self.solve(row, column)下面直接给出整个算法的源代码，测试这个算法使用的是芬兰数学家因卡拉花费3个月时间设计出的世界上迄今难度最大的数独。
class Sudoku:
def __init__(self, initial_state):
"""
初始化
:param initial_state: 初始状态
"""
self.state = initial_state
def conflict(self, row, column, value):
"""
检测冲突
:param row: 当前值所在的行
:param column: 当前值所在的列
:param value: 当前值
:return: 有冲突返回 True，无冲突返回 False
"""
for item in self.state[row]:
if item == value:
return True
for row0 in self.state:
if row0[column] == value:
return True
row0, column0 = row//3*3, column//3*3
block = self.state[row0][column0:column0+3]+self.state[row0+1][column0:column0+3] + \
self.state[row0+2][column0:column0+3]
for item in block:
if item == value:
return True
return False
def get_next(self, row, column):
"""
获取下一个未填项
:param row: 当前行
:param column: 当前列
:return: 下一个未填项的行，下一个未填项的列
"""
for next_column in range(column+1, 9):
if self.state[row][next_column] == 0:
return row, next_column
for next_row in range(row+1, 9):
for next_column in range(9):
if self.state[next_row][next_column] == 0:
return next_row, next_column
return -1, -1
def solve(self, row, column):
"""
解当前未填项
:param row: 当前未填项所在的行
:param column: 当前未填项所在的列
:return: 如果填满就返回 True，否则递归直到填满
"""
if self.state[row][column] == 0:
for value in range(1, 10):
if not self.conflict(row, column, value):
self.state[row][column] = value
next_row, next_column = self.get_next(row, column)
if next_row == -1:
return True
else:
end = self.solve(next_row, next_column)
if not end:
self.state[row][column] = 0
else:
return True
def run(self):
"""
运行整个算法
:return:
"""
if self.state[0][0] == 0:
self.solve(0, 0)
else:
row, column = self.get_next(0, 0)
self.solve(row, column)
if __name__ == '__main__':
state = [[8, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 6, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 9, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 7, 0, 0, 0],
[0, 0, 0, 8, 4, 5, 7, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 3, 0],
[0, 0, 1, 0, 0, 0, 0, 6, 8],
[0, 0, 8, 5, 0, 0, 0, 1, 0],
[0, 9, 0, 0, 0, 0, 4, 0, 0]]
sudoku = Sudoku(state)
sudoku.run()
for row1 in sudoku.state:
print(row1)运行结果如图所示。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-06-25，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 Python机器学习算法说书人 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读