https www geeksforgeeks orgsolvecrosswordpuzzle check if a word can be placed at the given position puzzle isvalidpuzzle word 0 0 true true puzzle isvalidpuzzle word 0 0 false true place a word at the given position puzzle placewordpuzzle word 0 0 true puzzle w o r d remove a word from the given position puzzle w o r d removewordpuzzle word 0 0 true puzzle solve the crossword puzzle using backtracking puzzle words word four more last solvecrosswordpuzzle words true puzzle words word four more paragraphs solvecrosswordpuzzle words false https www geeksforgeeks org solve crossword puzzle check if a word can be placed at the given position puzzle is_valid puzzle word 0 0 true true puzzle is_valid puzzle word 0 0 false true place a word at the given position puzzle place_word puzzle word 0 0 true puzzle w o r d remove a word from the given position puzzle w o r d remove_word puzzle word 0 0 true puzzle solve the crossword puzzle using backtracking puzzle words word four more last solve_crossword puzzle words true puzzle words word four more paragraphs solve_crossword puzzle words false
def is_valid(
    puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool
) -> bool:
    
    for i in range(len(word)):
        if vertical:
            if row + i >= len(puzzle) or puzzle[row + i][col] != "":
                return False
        else:
            if col + i >= len(puzzle[0]) or puzzle[row][col + i] != "":
                return False
    return True


def place_word(
    puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool
) -> None:
    
    for i, char in enumerate(word):
        if vertical:
            puzzle[row + i][col] = char
        else:
            puzzle[row][col + i] = char


def remove_word(
    puzzle: list[list[str]], word: str, row: int, col: int, vertical: bool
) -> None:
    
    for i in range(len(word)):
        if vertical:
            puzzle[row + i][col] = ""
        else:
            puzzle[row][col + i] = ""


def solve_crossword(puzzle: list[list[str]], words: list[str]) -> bool:
    
    for row in range(len(puzzle)):
        for col in range(len(puzzle[0])):
            if puzzle[row][col] == "":
                for word in words:
                    for vertical in [True, False]:
                        if is_valid(puzzle, word, row, col, vertical):
                            place_word(puzzle, word, row, col, vertical)
                            words.remove(word)
                            if solve_crossword(puzzle, words):
                                return True
                            words.append(word)
                            remove_word(puzzle, word, row, col, vertical)
                return False
    return True


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(row))
    else:
        print("No solution found:")