【经典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

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'

????????????????????pie_hash.add(row +?col)

????????????????????na_hash.add(row -?col)

????????????????????col_hash.add(col)

????????????????????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]?!=?'.':

????????????????????row_set[i].add(board[i][j])

????????????????????col_set[j].add(board[i][j])

????????????????????square_set[i//3][j//3].add(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:

????????????????????row[i].add(ch)

????????????????????col[j].add(ch)

????????????????????palace[i//3][j//3].add(ch)

????????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

????????????????row[i].add(num)

????????????????col[j].add(num)

????????????????palace[i//3][j//3].add(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