# 【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列：单词搜索、N皇后问题、判断有效数独、解数独

### 单词搜索

class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
self.m = len(board)
self.n = len(board[0])
for i in range(self.m):
for j in range(self.n):
if board[i][j] == word[0]:
if self.check(board,i,j,word, 0):
return True
return False

def check(self, board, i, j, word, index):
if i < 0 or i >= self.m or j < 0 or j >= self.n or board[i][j] != word[index]:
return False
if index == len(word) - 1:
return True
# 把当前坐标的值保存下来，为了在最后复原,回溯
t = board[i][j]
# 然后修改当前坐标的值，避免之前找到过的元素又被找到一次
board[i][j] = '.'
res = self.check(board,i,j-1,word,index + 1) or self.check(board,i,j+1,word,index + 1) or self.check(board,i-1,j,word,index + 1) or self.check(board,i+1,j,word,index + 1)
board[i][j] = t
return res

### N皇后问题

class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def isValid(row, col):
for i in range(row):
for j in range(n):
# 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等
# 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等
if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
return False
return True
def backtrack(board, row):
if row >= n:
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
for i in range(n):
if isValid(row, i, board):
board[row][i] = 'Q'
backtrack(board, row+1)
board[row][i] = '.'
res = []
board = [['.'] * n for _ in range(n)]
backtrack(board,0)
return res
# 优化，通过集合记录之前放置过元素的正向对角线，负向对角线，及列，判断当前点是否在集合中，在的话说明不满足要求
def solveNQueens(self, n: int) -> List[List[str]]:
def isValid(row, col):
# 注：左斜对角线上，同一条斜线上的每个位置满足行下标与列下标之差相等
# 注：右斜对角线上，同一条斜线上的每个位置满足行下标与列下标之和相等
if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash:
return False
return True
def backtrack(board, row):
if row >= n:
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
for col in range(n):
if isValid(row, col, board):
board[row][col] = 'Q'
backtrack(board, row+1)
board[row][col] = '.'
pie_hash.remove(row + col)
na_hash.remove(row-col)
col_hash.remove(col)
res = []
board = [['.'] * n for _ in range(n)]
pie_hash = set()
na_hash = set()
col_hash = set()
backtrack(board,0)
return res

### 判断有效数独

class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row_set = [set() for _ in range(9)]
col_set = [set() for _ in range(9)]
square_set = [[set() for _ in range(3)] for _ in range(3)]  #3*3
for i in range(9):
for j in range(9):
if board[i][j] in row_set[i] or board[i][j] in col_set[j] or board[i][j] in square_set[i//3][j//3]:
return False
if board[i][j] != '.':
return True

### 解数独

class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
nums = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
row = [set() for _ in range(9)]
col = [set() for _ in range(9)]
palace = [[set() for _ in range(3)] for _ in range(3)]  # 3*3
blank = []
# 初始化，按照行、列、宫 分别存入哈希表
for i in range(9):
for j in range(9):
ch = board[i][j]
if ch == ".":
blank.append((i, j))
else:
def dfs(n):
if n == len(blank):
return True
i, j = blank[n]
rst = nums - row[i] - col[j] - palace[i//3][j//3]  # 剩余的数字
### rst = nums - (row[i] | col[j] | palace[i//3][j//3])
if not rst:
return False
for num in rst:
board[i][j] = num
if dfs(n+1):
return True
row[i].remove(num)
col[j].remove(num)
palace[i//3][j//3].remove(num)
dfs(0)

class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.board = board
self.solve()

def findUnassigned(self):
for row in range(9):
for col in range(9):
if self.board[row][col] == ".":
return row, col
return -1, -1

def solve(self):
row, col = self.findUnassigned()
#no unassigned position is found, puzzle solved
if row == -1 and col == -1:
return True
for num in ["1","2","3","4","5","6","7","8","9"]:
if self.isSafe(row, col, num):
self.board[row][col] = num
if self.solve():
return True
self.board[row][col] = "."
return False

def isSafe(self, row, col, ch):
boxrow = row - row%3
boxcol = col - col%3
if self.checkrow(row,ch) and self.checkcol(col,ch) and self.checksquare(boxrow, boxcol, ch):
return True
return False

def checkrow(self, row, ch):
for col in range(9):
if self.board[row][col] == ch:
return False
return True

def checkcol(self, col, ch):
for row in range(9):
if self.board[row][col] == ch:
return False
return True

def checksquare(self, row, col, ch):
for r in range(row, row+3):
for c in range(col, col+3):
if self.board[r][c] == ch:
return False
return True

|
29天前
|
C语言

11 1
|
14天前
|

14 0
|
1月前
|

【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
【LeetCode刷题】滑动窗口解决问题：串联所有单词的子串（困难）、最小覆盖子串（困难）
24 1
|
26天前

10 0
|
26天前
|

12 0
|
26天前
|

10 0
|
26天前
|

13 0
|
26天前
|

12 0
|
1月前
|

【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
36 0
|
1月前
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（4）
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
15 0