Skip to content

Backtracking Exhaustive Search and Pruning

Table of Contents

3211. Generate Binary Strings Without Adjacent Zeros

967. Numbers With Same Consecutive Differences

1415. The k-th Lexicographical String of All Happy Strings of Length n

1219. Path with Maximum Gold

from typing import List


def exist(board: List[List[str]], word: str) -> bool:
    m, n = len(board), len(board[0])
    path = set()
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))

    def dfs(r, c, i):
        if i == len(word):
            return True

        if (
            r < 0
            or r >= m
            or c < 0
            or c >= n
            or board[r][c] != word[i]
            or (r, c) in path
        ):
            return False

        path.add((r, c))

        for dr, dc in dirs:
            if dfs(r + dr, c + dc, i + 1):
                return True

        path.remove((r, c))
        return False

    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True

    return False


board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
word = "ABCCED"
print(exist(board, word))  # True

980. Unique Paths III

1255. Maximum Score Words Formed by Letters

473. Matchsticks to Square

212. Word Search II

from typing import List

from leetpattern.utils import Trie


# Backtracking + Trie
def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    trie = Trie()
    for word in words:
        trie.add_word(word)

    m, n = len(board), len(board[0])
    result, visit = set(), set()

    def dfs(r, c, node, word):
        if (
            r < 0
            or r >= m
            or c < 0
            or c >= n
            or (r, c) in visit
            or board[r][c] not in node.children
        ):
            return None

        visit.add((r, c))

        node = node.children[board[r][c]]
        word += board[r][c]
        if node.is_word:
            result.add(word)

        dfs(r - 1, c, node, word)
        dfs(r + 1, c, node, word)
        dfs(r, c - 1, node, word)
        dfs(r, c + 1, node, word)

        visit.remove((r, c))

    for r in range(m):
        for c in range(n):
            dfs(r, c, trie.root, "")

    return list(result)


def test_find_words():
    board = [
        ["o", "a", "a", "n"],
        ["e", "t", "a", "e"],
        ["i", "h", "k", "r"],
        ["i", "f", "l", "v"],
    ]
    words = ["oath", "pea", "eat", "rain"]
    result = findWords(board, words)
    assert sorted(result) == ["eat", "oath"]

37. Sudoku Solver

"""
- [Sudoku Solver](https://leetcode.com/problems/sudoku-solver/)
- [解数独](https://leetcode.cn/problems/sudoku-solver/)
- Hard
"""

from pprint import pprint
from typing import List


# Backtracking - Board
def solveSudoku(board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """

    def backtracking(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 is_valid(i, j, k, board):
                        board[i][j] = str(k)
                        if backtracking(board):
                            return True
                        board[i][j] = "."
                return False
        return True

    def is_valid(row: int, col: int, val: int, board: List[List[str]]) -> bool:
        for i in range(9):
            if board[row][i] == str(val):
                return False
        for j in range(9):
            if board[j][col] == str(val):
                return False
        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

    backtracking(board)


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"],
]

solveSudoku(board)
pprint(board)
# [['5', '3', '4', '6', '7', '8', '9', '1', '2'],
#  ['6', '7', '2', '1', '9', '5', '3', '4', '8'],
#  ['1', '9', '8', '3', '4', '2', '5', '6', '7'],
#  ['8', '5', '9', '7', '6', '1', '4', '2', '3'],
#  ['4', '2', '6', '8', '5', '3', '7', '9', '1'],
#  ['7', '1', '3', '9', '2', '4', '8', '5', '6'],
#  ['9', '6', '1', '5', '3', '7', '2', '8', '4'],
#  ['2', '8', '7', '4', '1', '9', '6', '3', '5'],
#  ['3', '4', '5', '2', '8', '6', '1', '7', '9']]

638. Shopping Offers

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

1240. Tiling a Rectangle with the Fewest Squares

679. 24 Game

282. Expression Add Operators

126. Word Ladder II

691. Stickers to Spell Word

  • LeetCode | 力扣

  • Tags: Array, Hash Table, String, Dynamic Programming, Backtracking, Bit Manipulation, Memoization, Bitmask

2056. Number of Valid Move Combinations On Chessboard

2386. Find the K-Sum of an Array

488. Zuma Game

2664. The Knight’s Tour

247. Strobogrammatic Number II

248. Strobogrammatic Number III

411. Minimum Unique Word Abbreviation

1088. Confusing Number II

Comments