Backtracking: N-Queens и задачи на сетках

Продвинутые задачи backtracking с ограничениями. Используем sets для проверки атак и mark/restore для обхода сеток.

#1. N-Queens (LeetCode 51) 🔴 Hard

Ссылка: https://leetcode.com/problems/n-queens/

Условие: Задача о расстановке n ферзей на шахматной доске n×n так, чтобы ни один ферзь не атаковал другой.

Верните все возможные решения. Каждое решение представлено как массив строк, где 'Q' — ферзь, '.' — пустая клетка.

Примеры:

Ввод: n = 4
Вывод: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Ввод: n = 1
Вывод: [["Q"]]

Ограничения:

1 <= n <= 9

💡 Подсказка: Используйте 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

Объяснение:

cols — колонки под атакой
pos_diag — главные диагонали (): row + col = const
neg_diag — побочные диагонали (/): row - col = const
Базовый случай: row == n — все ферзи размещены

Сложность:

Время: O(n!)
Память: O(n)

#2. N-Queens II (LeetCode 52) 🔴 Hard

Ссылка: https://leetcode.com/problems/n-queens-ii/

Условие: Задача о расстановке n ферзей на шахматной доске n×n так, чтобы ни один ферзь не атаковал другой.

Верните количество различных решений.

Примеры:

Ввод: n = 4
Вывод: 2

Ввод: n = 1
Вывод: 1

Ограничения:

1 <= n <= 9

Решение:

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]

Объяснение:

Та же логика, что в N-Queens I
Вместо сохранения решений просто считаем количество
Используем count[0] для изменяемого счётчика

Сложность:

Время: O(n!)
Память: O(n)

#3. Word Search (LeetCode 79) 🟦 Medium

Ссылка: https://leetcode.com/problems/word-search/

Условие: Дана двумерная сетка 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

Ограничения:

m == board.length
n == board[i].length
1 <= m, n <= 6
1 <= word.length <= 15

💡 Подсказка: Помечайте посещённую клетку '#', затем восстанавливайте значение после 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[r][c] = '#' для предотвращения повторного посещения
После DFS восстанавливаем значение
Начинаем с каждой клетки, где board[i][j] == word[0]

Сложность:

Время: O(m × n × 4^L), где L — длина слова
Память: O(L) — глубина рекурсии

#4. Word Search II (LeetCode 212) 🔴 Hard

Ссылка: https://leetcode.com/problems/word-search-ii/

Условие: Дана двумерная сетка 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"]
Вывод: []

Ограничения:

m == board.length
n == board[i].length
1 <= m, n <= 12
words.length <= 3 × 10^4

💡 Подсказка: Используйте 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

Объяснение:

Строим Trie из всех слов
DFS с backtracking, проходя по Trie
next_node.word != None — нашли слово
Удаляем найденные слова (word = None), чтобы не дублировать
Оптимизация: удаляем листы Trie для ускорения

Сложность:

Время: O(m × n × 4^L), где L — длина самого длинного слова
Память: O(total characters in all words) для Trie

#5. Sudoku Solver (LeetCode 37) 🔴 Hard

Ссылка: https://leetcode.com/problems/sudoku-solver/

Условие: Напишите программу для решения судоку.

Правила:

Каждая цифра 1-9 должна встречаться ровно один раз в каждой строке
Каждая цифра 1-9 должна встречаться ровно один раз в каждом столбце
Каждая цифра 1-9 должна встречаться ровно один раз в каждом из 9 блоков 3×3

Примеры:

Ввод: 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 заполняется решением

Ограничения:

board.length == 9
board[i].length == 9
board[i][j] — цифра '1'-'9' или '.'

💡 Подсказка: Используйте 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)

Объяснение:

3 sets для проверки: rows, cols, boxes
box_idx = (row // 3) * 3 + col // 3 — индекс бокса 0-8
Базовый случай: row == 9 — все клетки заполнены
Пробуем цифры 1-9, проверяем валидность

Сложность:

Время: O(9^(m×n)) — в худшем случае
Память: O(1) — фиксированный размер 9×9

#6. Шпаргалка

Задача	Ключевая идея
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

#7. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильная проверка диагоналей

Проблема: Путаем главные и побочные диагонали.

# ❌ Неправильно
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 (константа для /).

#❌ Ошибка 2: Забыли восстановить клетку

Проблема: Не восстанавливаем значение после 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: Неправильный индекс бокса в Sudoku

Проблема: Неправильно вычисляем индекс бокса 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.

#8. Заключение

Backtracking: N-Queens и задачи на сетках — продвинутые задачи с ограничениями.

Ключевые принципы:

N-Queens: 3 sets для проверки атак (cols, pos_diag, neg_diag)
Word Search: mark/restore с '#' для посещённых клеток
Sudoku: 3 sets (rows, cols, boxes) + box_idx = (row//3)*3 + col//3
Trie + DFS для оптимизации поиска слов

Ввод: 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

Ввод: 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"] Вывод: []

Ввод: 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 заполняется решением

Задача

Ключевая идея

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

Backtracking: Продвинутый