Untitled

from collections import defaultdict
import random

def find_slots(grid):
    """Identify all horizontal and vertical slots in the grid."""
    slots = []
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0

    # Finding horizontal slots
    for row in range(rows):
        start = None
        for col in range(cols):
            if 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 cols - start > 1:
            slots.append(("H", row, start, cols - start))

    # Finding vertical slots
    for col in range(cols):
        start = None
        for row in range(rows):
            if 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 rows - start > 1:
            slots.append(("V", start, col, rows - start))

    return slots

def get_intersections(slots):
    """Find all intersections between slots."""
    intersections = defaultdict(list)

    for i, slot1 in enumerate(slots):
        dir1, row1, col1, length1 = slot1
        for j, slot2 in enumerate(slots):
            if i >= j:
                continue

            dir2, row2, col2, length2 = slot2
            if dir1 == "H" and dir2 == "V":
                if col2 in range(col1, col1 + length1) and row1 in range(row2, row2 + length2):
                    intersections[i].append((j, col2 - col1, row1 - row2))
                    intersections[j].append((i, row1 - row2, col2 - col1))
            elif dir1 == "V" and dir2 == "H":
                if row2 in range(row1, row1 + length1) and col1 in range(col2, col2 + length2):
                    intersections[i].append((j, row2 - row1, col1 - col2))
                    intersections[j].append((i, col1 - col2, row2 - row1))

    return intersections

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

    for i in range(length):
        if direction == "H":
            if grid[row][col + i] not in ('-', word[i]):
                return False
        elif direction == "V":
            if grid[row + i][col] not in ('-', word[i]):
                return False
    return True

def place_word(grid, word, slot):
    """Place a word in the given slot."""
    direction, row, col, length = slot
    for i in range(length):
        if direction == "H":
            grid[row][col + i] = word[i]
        elif direction == "V":
            grid[row + i][col] = word[i]

def remove_word(grid, slot):
    """Remove a word from the slot (restore empty cells)."""
    direction, row, col, length = slot
    for i in range(length):
        if direction == "H":
            grid[row][col + i] = '-'
        elif direction == "V":
            grid[row + i][col] = '-'

def validate_grid_words(grid, word_bank):
    """Check that every filled horizontal and vertical word is in the word_bank."""
    slots = find_slots(grid)
    words_formed = []

    for direction, row, col, length in slots:
        word = ""
        for i in range(length):
            if direction == "H":
                word += grid[row][col + i]
            elif direction == "V":
                word += grid[row + i][col]
        words_formed.append(word)

    return all(word in word_bank for word in words_formed)

def solve_crossword(grid, word_bank, slots, intersections):
    """Backtracking function to solve the crossword with dynamic constraint propagation."""
    # Sort slots based on number of words that can fit (most constrained slot first)
    word_bank = sorted(word_bank, key=len, reverse=True)  # Sort words by length (longest first)
    return backtrack(grid, word_bank, slots, intersections, {})

def backtrack(grid, word_bank, slots, intersections, slot_to_word):
    """Perform backtracking with intelligent slot selection and constraint propagation."""
    # If all slots are filled, return True
    if len(slot_to_word) == len(slots):
        return validate_grid_words(grid, word_bank)

    # Choose the most constrained slot
    slot_idx = min([i for i in range(len(slots)) if i not in slot_to_word],
                   key=lambda idx: len([w for w in word_bank if can_place_word(grid, w, slots[idx])]))

    # Find all valid words for this slot
    slot = slots[slot_idx]
    valid_words = [word for word in word_bank if can_place_word(grid, word, slot)]

    for word in valid_words:
        # Place the word in the slot
        place_word(grid, word, slot)
        slot_to_word[slot_idx] = word
        word_bank.remove(word)

        # Propagate constraints to intersecting slots
        if backtrack(grid, word_bank, slots, intersections, slot_to_word):
            return True

        # Backtrack: remove the word and restore state
        remove_word(grid, slot)
        word_bank.append(word)
        del slot_to_word[slot_idx]

    return False

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

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

word_bank = ["APE", "DEW", "DYE", "EKE", "IMP", "MAP", "OIL", "RUE", "SKI", "SKY", "SLY", "SUM",
             "TAP", "WRY", "YES", "YOU", "ACHE", "BEER", "GASP", "GUSH", "HARM",
             "ISLE", "JERK", "MAMA", "MUTT", "OUCH", "PICK", "ROOT", "SPAT", "TIME", "TOGO", "TONS",
             "WHOM", "YELL", "PUMA", "TOGA", "MEW", "OLL"]
random.shuffle(word_bank)

# Step 1: Identify the slots in the grid
slots = find_slots(grid)

# Step 2: Find intersections between slots
intersections = get_intersections(slots)

# Step 3: Solve the crossword
if solve_crossword(grid, word_bank, slots, intersections):
    print("Crossword Solved:")
    print_grid(grid)
else:
    print("No solution found.")