Untitled

import random

class CrosswordSolver:
    def __init__(self, grid, word_bank):
        self.grid = grid
        self.word_bank = word_bank
        self.rows = len(grid)
        self.cols = len(grid[0]) if self.rows > 0 else 0
        self.slots = self.find_slots()

    def find_slots(self):
        """Identifies all horizontal and vertical slots in the grid."""
        slots = []

        # Finding horizontal slots
        for row in range(self.rows):
            start = None
            for col in range(self.cols):
                if self.grid[row][col] == '-':
                    if start is None:
                        start = col
                else:
                    if start is not None and col - start > 1:
                        slots.append(("H", row, start, col - start))
                    start = None
            if start is not None and self.cols - start > 1:
                slots.append(("H", row, start, self.cols - start))

        # Finding vertical slots
        for col in range(self.cols):
            start = None
            for row in range(self.rows):
                if self.grid[row][col] == '-':
                    if start is None:
                        start = row
                else:
                    if start is not None and row - start > 1:
                        slots.append(("V", start, col, row - start))
                    start = None
            if start is not None and self.rows - start > 1:
                slots.append(("V", start, col, self.rows - start))

        print(f"Slots identified: {slots}")  # Debug: Print identified slots
        return slots

    def can_place_word(self, slot, word):
        """Check if the word can be placed in the given slot without conflict."""
        direction, row, col, length = slot
        if len(word) != length:
            return False

        for i in range(length):
            if direction == "H":
                if self.grid[row][col + i] not in ('-', word[i]):
                    return False
            else:  # Vertical slot
                if self.grid[row + i][col] not in ('-', word[i]):
                    return False
        return True

    def place_word(self, slot, word):
        """Place a word in a given slot and return the updated grid."""
        print(f"Placing word {word} in slot {slot}")  # Debug: Print word placement
        direction, row, col, length = slot
        for i in range(length):
            if direction == "H":
                self.grid[row][col + i] = word[i]
            else:  # Vertical slot
                self.grid[row + i][col] = word[i]

    def remove_word(self, slot):
        """Remove a word from a given slot (restore empty cells)."""
        print(f"Removing word from slot {slot}")  # Debug: Print word removal
        direction, row, col, length = slot
        for i in range(length):
            if direction == "H":
                self.grid[row][col + i] = '-'
            else:  # Vertical slot
                self.grid[row + i][col] = '-'

    def solve_crossword(self, index=0):
        """Backtracking function to solve the crossword puzzle."""
        if index == len(self.slots):
            return True  # All slots filled successfully

        slot = self.slots[index]

        for word in self.word_bank:
            if self.can_place_word(slot, word):
                # Place the word in the slot
                self.place_word(slot, word)
                # Remove the word from word bank temporarily
                self.word_bank.remove(word)

                # Recursively try to fill the next slot
                if self.solve_crossword(index + 1):
                    return True

                # Backtrack: remove the word and try another one
                self.remove_word(slot)
                self.word_bank.append(word)

        return False

    def print_grid(self):
        """Prints the crossword grid in a readable format."""
        for row in self.grid:
            print("".join(row))


# Sample grid and word bank
grid = [
     ['#', '-', '-', '-', '#'],
     ['#', '#', '-', '#', '#'],
     ['#', '#', '-', '-', '-'],
     ['#', '#', '-', '#', '#'],
     ['#', '#', '-', '-', '-']

]
word_bank = ["EAT", "APPLE", "PEA", "HAT", "EAR", "CAT", "CAR"]
random.shuffle(word_bank)

# Create the crossword solver and solve
solver = CrosswordSolver(grid, word_bank)

# Attempt to solve the crossword
if solver.solve_crossword():
    print("Crossword Solved:")
    solver.print_grid()
else:
    print("No solution found.")