LeetCode Day 30 Backtracking Algorithm (6/6)
Published:
Today, I’m catching up on the progress I left off before Covid Positive. Finishing up the backtracking piece. The questions are all very difficult, so it’s good to get a clear idea of what’s going on.
Question 1
You are given a list of airline
ticketswheretickets[i] = [fromi, toi]represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.All of the tickets belong to a man who departs from
"JFK", thus, the itinerary must begin with"JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
- For example, the itinerary
["JFK", "LGA"]has a smaller lexical order than["JFK", "LGB"].You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
This is a difficult question with some tough spots to work out:
- A trip with poorly handled flights can easily turn into a loop and become a dead end.
- How to record the mapping relationship of sorting ?
- The mapping relationship of sorting can be solved with hashmap.
I can’t do it by myself, I read the code written by others: used array and backtracking solved the problem!
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
tickets.sort() # To make sure start from smallest lexical order
used = [0] * len(tickets)
path = ['JFK']
results = []
self.backtracking(tickets, used, path, 'JFK', results)
return results[0]
def backtracking(self, tickets, used, path, cur, results):
if len(path) == len(tickets) + 1: # End
results.append(path[:])
return True
for i, ticket in enumerate(tickets):
if ticket[0] == cur and used[i] == 0:
used[i] = 1
path.append(ticket[1])
state = self.backtracking(tickets, used, path, ticket[1], results)
path.pop()
used[i] = 0
if state:
return True
Question 2
The n-queens puzzle is the problem of placing
nqueens on ann x nchessboard such that no two queens attack each other.Given an integer
n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.Each solution contains a distinct board configuration of the n-queens’ placement, where
'Q'and'.'both indicate a queen and an empty space, respectively.
This is a classic puzzle, if n is given a definite value, several finite solutions can be thought of, but n is not given, and it is more complicated when the board area is large. Also converting a two-bit array of boards into a usable array is a challenge.
The following restrictions exist between queens:
- cannot be in the same row
- cannot be in the same column
- cannot be in the same diagonal
The process is still abstracted to traversing the tree and then pruning the unsatisfied conditions.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = []
chessboard = ['.' * n for _ in range(n)]
self.backtracking(n, 0, chessboard, result)
return [[''.join(row) for row in solution] for solution in result]
def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:
if row == n:
result.append(chessboard[:])
return
for col in range(n):
if self.isValid(row, col, chessboard):
chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:] # place Queen
self.backtracking(n, row + 1, chessboard, result)
chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]
def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:
for i in range(row):
if chessboard[i][col] == 'Q':
return False
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if chessboard[i][j] == 'Q':
return False
i -= 1
j -= 1
i, j = row - 1, col + 1
while i >= 0 and j < len(chessboard):
if chessboard[i][j] == 'Q':
return False
i -= 1
j += 1
return True
Question 3
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row.- Each of the digits
1-9must occur exactly once in each column.- Each of the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.The
'.'character indicates empty cells.
The difficulty with this question is the two-dimensional recursion.
There are three dimensions to determine if the board is legal as follows:
- Whether the same row is duplicated
- Whether the same column is duplicated
- Whether the nine palindromes are duplicated
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.backtracking(board)
def backtracking(self, board: List[List[str]]) -> bool:
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] != '.': continue
for k in range(1, 10):
if self.is_valid(i, j, k, board):
board[i][j] = str(k)
if self.backtracking(board): return True
board[i][j] = '.'
return False
return True
def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:
# If conflict in one line
for i in range(9):
if board[row][i] == str(val):
return False
# If conflict in one row
for j in range(9):
if board[j][col] == str(val):
return False
# If conflict in one 9 x 9
start_row = (row // 3) * 3
start_col = (col // 3) * 3
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == str(val):
return False
return True