本文选自王硕等编著的《你也能看的懂的python算法》
什么是回溯算法
简单来讲，回溯算法利用试错的方法解决问题。一旦发现当前步骤失败，回溯方法就返回上一个步骤，选择另一种方案继续试错。
回溯算法应用
遍历所有排序方式
对红黄蓝绿进行排序，一共有24中排序方式。
class Solution():
def solvePermutation(self, array):
self.helper(array, [])
def helper(self, array, solution):
if len(array) == 0:
print(solution)
return
for i in range(len(array)):
newSolution = solution + [array[i]]
newArray = array[:i] + array[i + 1:]
self.helper(newArray, newSolution)
Solution().solvePermutation(["红", "黄", "蓝", "绿"])
查找单词问题
在一堆字母中横向或竖向找出单词，不但可以上下左右，还可以拐弯。
class Solution():
def wordSearch(self, board, word):
for i in range(len(board)):
for j in range(len(board[0])):
if self.helper(board, word, i, j):
return True
return False
def helper(self, board, current, row, column):
if len(current) == 0:
return True
if 0 <= row < len(board) and 0 <= column < len(board[0]):
if board[row][column] == current[0]:
board[row][column] = ""
if self.helper(board, current[1:], row - 1, column):
return True
if self.helper(board, current[1:], row + 1, column):
return True
if self.helper(board, current[1:], row, column - 1):
return True
if self.helper(board, current[1:], row, column + 1):
return True
board[row][column] = current[0]
return False
board = [["a", "c", "r", "y", "l"], ["l", "w", "o", "r", "i"], ["a", "f", "d", "l", "c"], ["k", "e", "e", "w", "e"],
["o", "d", "r", "o", "s"]]
a = Solution().wordSearch(board, "week")
八皇后问题
class Solution(object):
def solveNQueens(self, n):
self.helper([-1] * n, 0, n)
def helper(self, columnPositions, rowIndex, n):
if rowIndex == n:
self.printSolution(columnPositions, n)
return
for column in range(n):
columnPositions[rowIndex] = column
if self.isValid(columnPositions, rowIndex):
self.helper(columnPositions, rowIndex + 1, n)
def isValid(self, columnPositions, rowIndex):
for i in range(rowIndex):
if columnPositions[i] == columnPositions[rowIndex]:
return False
elif abs(columnPositions[i] - columnPositions[rowIndex]) == rowIndex - i:
return False
return True
def printSolution(self, columnPosition, n):
for row in range(n):
line = ""
for column in range(n):
if columnPosition[row] == column:
line += "Q"
else:
line += "."
print(line)
print("\n")
Solution().solveNQueens(8)
解数独
class Solution():
def solveSuduku(self, board):
self.helper(board, 0)
def helper(self, board, index):
if index >= 81:
self.printSolution(board)
return
if board[index] == 0:
for i in range(1, 10):
if self.isValid(board, index, i):
board[index] = i
self.helper(board, index + 1)
board[index] = 0
else:
self.helper(board, index + 1)
def printSolution(self, board):
for i in range(0, 81, 9):
print(board[i: i + 9])
def isValid(self, board, index, num):
row = index // 9
column = index % 9
for i in range(index + 9, 81, 9):
if board[i] == num:
return False
for i in range(index - 9, -1, -9):
if board[i] == num:
return False
for i in range(9 * row, 9 * (row + 1)):
if board[i] == num:
return False
for i in range(row - row % 3, 3 + row - row % 3):
for j in range(column - column % 3, 3 + column - column % 3):
if board[j + i * 9] == num:
return False
return True
|