Python/backtracking/crossword_puzzle_solver.py at 7b7ee2e5c3e7def46b7a6e31afa9daae4de63ebf · TheAlgorithms/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
# https://www.geeksforgeeks.org/solve-crossword-puzzle/


def 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
    """
    rows, cols = len(puzzle), len(puzzle[0])
    for i, ch in enumerate(word):
        r, c = (row + i, col) if vertical else (row, col + i)
        if r >= rows or c >= cols:
            return False
        cell = puzzle[r][c]
        if cell not in ("", ch):
            return False
    return True


def 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', '', '', '']]
    """
    for i, ch in enumerate(word):
        if vertical:
            puzzle[row + i][col] = ch
        else:
            puzzle[row][col + i] = ch


def 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'], ['', '', '', ''], ['', '', '', ''], ['', '', '', '']]
    """
    for i in range(len(word)):
        r, c = (row + i, col) if vertical else (row, col + i)
        if snapshot[r][c] == "":
            puzzle[r][c] = ""


def 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
    """
    if not words:
        return True

    remaining = sorted(words, key=len, reverse=True)
    word, rest = remaining[0], remaining[1:]

    for row in range(len(puzzle)):
        for col in range(len(puzzle[0])):
            for vertical in (True, False):
                if is_valid(puzzle, word, row, col, vertical):
                    snapshot = [r[:] for r in puzzle]
                    place_word(puzzle, word, row, col, vertical)
                    if solve_crossword(puzzle, rest):
                        return True
                    remove_word(puzzle, word, row, col, vertical, snapshot)

    return False


if __name__ == "__main__":
    PUZZLE = [[""] * 3 for _ in range(3)]
    WORDS = ["cat", "dog", "car"]
    if solve_crossword(PUZZLE, WORDS):
        print("Solution found:")
        for row in PUZZLE:
            print(" ".join(cell or "." for cell in row))
    else:
        print("No solution found.")