N-Queens, Word Search, Sudoku.
Продвинутые задачи backtracking с ограничениями. Используем sets для проверки атак и mark/restore для обхода сеток.
Условие: Задача о расстановке n ферзей на шахматной доске n×n так, чтобы ни один ферзь не атаковал другой.
Верните все возможные решения. Каждое решение представлено как массив строк, где 'Q' — ферзь, '.' — пустая клетка.
Примеры:
Ввод: n = 4
Вывод: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Ввод: n = 1
Вывод: [["Q"]]
Ограничения:
💡 Подсказка: Используйте 3 set для проверки атак: колонки, главные диагонали (row+col), побочные диагонали (row-col).
Решение:
def solveNQueens(n):
result = []
board = [['.'] * n for _ in range(n)]
cols = set()
pos_diag = set() # row + col
neg_diag = set() # row - col
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
# Проверяем атаки
if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
continue
# Размещаем ферзя
cols.add(col)
pos_diag.add(row + col)
neg_diag.add(row - col)
board[row][col] = 'Q'
backtrack(row + 1)
# Backtrack
cols.remove(col)
pos_diag.remove(row + col)
neg_diag.remove(row - col)
board[row][col] = '.'
backtrack(0)
return resultОбъяснение:
Сложность:
Условие: Задача о расстановке n ферзей на шахматной доске n×n так, чтобы ни один ферзь не атаковал другой.
Верните количество различных решений.
Примеры:
Ввод: n = 4
Вывод: 2
Ввод: n = 1
Вывод: 1
Ограничения:
Решение:
def totalNQueens(n):
cols = set()
pos_diag = set() # row + col
neg_diag = set() # row - col
count = [0]
def backtrack(row):
if row == n:
count[0] += 1
return
for col in range(n):
if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
continue
cols.add(col)
pos_diag.add(row + col)
neg_diag.add(row - col)
backtrack(row + 1)
cols.remove(col)
pos_diag.remove(row + col)
neg_diag.remove(row - col)
backtrack(0)
return count[0]Объяснение:
Сложность:
Условие:
Дана двумерная сетка board и слово word. Верните true, если слово существует в сетке.
Слово строится из букв последовательно соседних клеток (горизонтально или вертикально). Одна и та же клетка не может использоваться более одного раза.
Примеры:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Вывод: true
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Вывод: false
Ограничения:
💡 Подсказка: Помечайте посещённую клетку '#', затем восстанавливайте значение после DFS.
Решение:
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, index):
if index == len(word):
return True
if (r < 0 or c < 0 or r >= rows or c >= cols or
board[r][c] != word[index]):
return False
# Помечаем как посещённый
temp = board[r][c]
board[r][c] = '#'
found = (dfs(r + 1, c, index + 1) or
dfs(r - 1, c, index + 1) or
dfs(r, c + 1, index + 1) or
dfs(r, c - 1, index + 1))
# Восстанавливаем
board[r][c] = temp
return found
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return FalseОбъяснение:
Сложность:
Условие:
Дана двумерная сетка board и список слов words. Верните все слова из списка, которые можно построить из букв на сетке.
Слово строится из букв последовательно соседних клеток. Одна и та же клетка не может использоваться более одного раза в одном слове.
Примеры:
Ввод: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
words = ["oath","pea","eat","rain"]
Вывод: ["eat","oath"]
Ввод: board = [["a","b"],["c","d"]], words = ["abcb"]
Вывод: []
Ограничения:
💡 Подсказка: Используйте Trie для оптимизации. DFS с backtracking, удаляйте найденные слова из Trie.
Решение:
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # Если не None, это конец слова
def findWords(board, words):
# Строим Trie
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.word = word # Сохраняем слово в конечном узле
result = []
rows, cols = len(board), len(board[0])
def dfs(r, c, node):
char = board[r][c]
if char not in node.children:
return
next_node = node.children[char]
# Проверка: нашли слово
if next_node.word:
result.append(next_node.word)
next_node.word = None # Убираем, чтобы не дублировать
# Помечаем как посещённый
board[r][c] = '#'
# Исследуем соседей
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, next_node)
# Восстанавливаем
board[r][c] = char
# Оптимизация: удаляем листы Trie
if not next_node.children:
del node.children[char]
for i in range(rows):
for j in range(cols):
dfs(i, j, root)
return resultОбъяснение:
Сложность:
Условие: Напишите программу для решения судоку.
Правила:
Примеры:
Ввод: board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Вывод: board заполняется решением
Ограничения:
💡 Подсказка: Используйте 3 sets для проверки: rows, cols, boxes. Бокс определяется (row//3, col//3).
Решение:
def solveSudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# Заполняем sets начальными значениями
for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = board[i][j]
rows[i].add(num)
cols[j].add(num)
boxes[(i // 3) * 3 + j // 3].add(num)
def backtrack(row, col):
# Базовый случай: прошли все строки
if row == 9:
return True
# Переходим к следующей строке
if col == 9:
return backtrack(row + 1, 0)
# Пропускаем заполненные клетки
if board[row][col] != '.':
return backtrack(row, col + 1)
# Пробуем цифры 1-9
for num in '123456789':
box_idx = (row // 3) * 3 + col // 3
if num not in rows[row] and num not in cols[col] and num not in boxes[box_idx]:
# Размещаем цифру
rows[row].add(num)
cols[col].add(num)
boxes[box_idx].add(num)
board[row][col] = num
if backtrack(row, col + 1):
return True
# Backtrack
rows[row].remove(num)
cols[col].remove(num)
boxes[box_idx].remove(num)
board[row][col] = '.'
return False
backtrack(0, 0)Объяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| N-Queens | 3 sets: cols, pos_diag (row+col), neg_diag (row-col) |
| N-Queens II | Считаем количество вместо сохранения |
| Word Search | Mark/restore: board[r][c] = '#' |
| Word Search II | Trie + DFS, удаляем найденные слова |
| Sudoku Solver | 3 sets: rows, cols, boxes |
Проблема: Путаем главные и побочные диагонали.
# ❌ Неправильно
pos_diag = row - col # Это neg_diag!
neg_diag = row + col # Это pos_diag!
# ✅ Правильно
pos_diag = row + col # Главные диагонали (\)
neg_diag = row - col # Побочные диагонали (/)Почему это неправильно: Диагонали определяются неправильно, ферзи будут атаковать друг друга.
Как исправить: Запомните: pos_diag = row + col (константа для ), neg_diag = row - col (константа для /).
Проблема: Не восстанавливаем значение после DFS.
# ❌ Неправильно
board[r][c] = '#'
found = dfs(r + 1, c, index + 1) or ...
# Забыли board[r][c] = temp!
# ✅ Правильно
temp = board[r][c]
board[r][c] = '#'
found = dfs(r + 1, c, index + 1) or ...
board[r][c] = temp # ВосстанавливаемПочему это неправильно: Клетка остаётся помеченной, влияет на другие пути поиска.
Как исправить: Всегда восстанавливайте значение после DFS.
Проблема: Неправильно вычисляем индекс бокса 3×3.
# ❌ Неправильно
box_idx = row // 3 + col // 3 # Даёт 0-4, а не 0-8!
# ✅ Правильно
box_idx = (row // 3) * 3 + col // 3 # Даёт 0-8Почему это неправильно: Боксы нумеруются 0-8 слева направо, сверху вниз.
Как исправить: Используйте формулу (row // 3) * 3 + col // 3.
Backtracking: N-Queens и задачи на сетках — продвинутые задачи с ограничениями.
Ключевые принципы:
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.