backtracking.crossword_puzzle_solver

Attributes

PUZZLE

Functions

is_valid(→ bool)	Check if a word can be placed at the given position.
place_word(→ None)	Place a word at the given position in the puzzle.
remove_word(→ None)	Remove a word from the puzzle, restoring only cells that were empty
solve_crossword(→ bool)	Solve the crossword puzzle using backtracking.

Module Contents

backtracking.crossword_puzzle_solver.is_valid(puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool) → bool

Check if a word can be placed at the given position. A cell is valid if it is empty or already contains the correct letter (enabling crossing/intersection between words).

>>> puzzle = [['', '', '', ''], ['', '', '', ''],
...           ['', '', '', ''], ['', '', '', '']]
>>> is_valid(puzzle, 'word', 0, 0, True)
True
>>> is_valid(puzzle, 'word', 0, 0, False)
True
>>> puzzle2 = [['w', '', ''], ['o', '', ''], ['r', '', ''], ['d', '', '']]
>>> is_valid(puzzle2, 'word', 0, 0, True)
True
>>> is_valid(puzzle2, 'cat', 0, 0, True)
False

backtracking.crossword_puzzle_solver.place_word(puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool) → None

Place a word at the given position in the puzzle.

>>> puzzle = [['', '', '', ''], ['', '', '', ''],
...           ['', '', '', ''], ['', '', '', '']]
>>> place_word(puzzle, 'word', 0, 0, True)
>>> puzzle
[['w', '', '', ''], ['o', '', '', ''], ['r', '', '', ''], ['d', '', '', '']]

backtracking.crossword_puzzle_solver.remove_word(puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool, snapshot: list[list[str]]) → None

Remove a word from the puzzle, restoring only cells that were empty before placement. Cells shared with crossing words are preserved.

>>> puzzle = [['w', 'o', 'r', 'd'], ['', '', '', ''],
...           ['', '', '', ''], ['', '', '', '']]
>>> snap = [['', 'o', 'r', 'd'], ['', '', '', ''],
...         ['', '', '', ''], ['', '', '', '']]
>>> remove_word(puzzle, 'word', 0, 0, False, snap)
>>> puzzle
[['', 'o', 'r', 'd'], ['', '', '', ''], ['', '', '', ''], ['', '', '', '']]

backtracking.crossword_puzzle_solver.solve_crossword(puzzle: list[list[str]], words: list[str]) → bool

Solve the crossword puzzle using backtracking. Words are tried longest-first to prune the search space early. Intersections between words (shared letters) are supported.

>>> puzzle = [['', '', '', ''], ['', '', '', ''],
...           ['', '', '', ''], ['', '', '', '']]
>>> solve_crossword(puzzle, ['word', 'four', 'more', 'last'])
True
>>> puzzle2 = [['', '', '', ''], ['', '', '', ''],
...            ['', '', '', ''], ['', '', '', '']]
>>> solve_crossword(puzzle2, ['word', 'four', 'more', 'paragraphs'])
False

backtracking.crossword_puzzle_solver.PUZZLE