Untitled

from collections import defaultdict
import random
import copy

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 and get all possible solutions."""
    solutions = []
    backtrack(grid, word_bank, slots, intersections, {}, solutions)
    return solutions

def backtrack(grid, word_bank, slots, intersections, slot_to_word, solutions):
    """Perform backtracking with intelligent slot selection and constraint propagation."""
    # If all slots are filled, store the current grid configuration
    if len(slot_to_word) == len(slots):
        if validate_grid_words(grid, word_bank):
            solutions.append(copy.deepcopy(grid))
        return

    # 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
        backtrack(grid, word_bank, slots, intersections, slot_to_word, solutions)

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

def print_grid(grid):
    """Print the crossword grid in a readable format."""
    for row in grid:
        print("".join(row))
    print()  # For better separation between solutions

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

word_bank = [
    'AP', 'ACH', 'DAO', 'DNA', 'GAP', 'GDP', 'HAT', 'HDC', 'HMT', 'NMJ', 'RHO', 'RNA', 'TSS',
    'UGA', 'UPR', 'UTR', 'VAT', 'NE', 'NA', 'BETA', 'CAMP', 'CHAT', 'DOPA', 'EXIT', 'EXON',
    'FULL', 'GENE', 'GPCR', 'HDAC', 'KDEL', 'MAST', 'MRNA', 'MULE', 'OCAT', 'RATE', 'RRNA',
    'SNAP', 'STOP', 'TATA', 'TRNA', 'VAMP', 'VMAT', 'CGMP', 'ALPHA', 'AMINE', 'CODON',
    'DIMER', 'EDMAN', 'GAMMA', 'GOLGI', 'HELIX', 'NOCAT', 'PROBE', 'SHEET', 'SNARE', 'SPARE',
    'TOXIN', 'TRANS', 'VIRUS', 'BIASED', 'CODING', 'ENZYME', 'FUSION', 'GENOME', 'GRADED',
    'GYRASE', 'INTRON', 'KINASE', 'LIGAND', 'MYELIN', 'NERNST', 'PLASMA', 'POLLEN', 'PURINE',
    'RIBOSE', 'SANGER', 'SODIUM', 'TRIMER', 'ULCERS', 'URACIL', 'ADENINE', 'ADRENAL',
    'AGONIST', 'ALLERGY', 'ANTIGEN', 'CAPPING', 'CHOLINE', 'COCAINE', 'CYCLASE', 'CYTOSOL',
    'DOCKING', 'FOLDING', 'GOLDMAN', 'HISTONE', 'HORMONE', 'INVERSE', 'ITCHING', 'KINESIN',
    'MEDULLA', 'OKAZAKI', 'PARTIAL', 'PEPTIDE', 'POTENCY', 'PRIMARY', 'PROTEIN', 'QUANTAL',
    'RELEASE', 'SOMATIC', 'SUBUNIT', 'ADENYLYL', 'AFFINITY', 'ANTIBODY', 'ARCHAEAN',
    'ARRESTIN', 'CARBOXYL', 'CHLORIDE', 'CYTOSINE', 'DOPAMINE', 'ENHANCER', 'ENVELOPE',
    'EFFICACY', 'ERGOSOME', 'GRANULES', 'HAYFLICK', 'HELICASE', 'KINETICS', 'OBLIGATE',
    'PEPTIDYL', 'POLYSOME', 'PROMOTER', 'RECEPTOR', 'RESPONSE', 'RIBOSOME', 'SILENCER',
    'SPLICING', 'SVEDBERG', 'SYNAPTIC', 'SYNTHASE', 'TELOMERE', 'TERTIARY', 'TETRAMER',
    'TOPOLOGY', 'TRIMERIC', 'TYROSINE', 'CONSTITUTIVE', 'POLYRIBOSOME', 'SCOMBROTOXIN',
    'STREPTOMYCES', 'TRANSDUCTION', 'ACETYLCHOLINE', 'AMPLIFICATION', 'COMMUNICATION',
    'COMPLEMENTARY', 'INTRACELLULAR', 'NEUROMUSCULAR', 'NORADRENALINE', 'PHENYLALANINE',
    'PHOSPHOLIPASE', 'PREINITIATION', 'PROTEINOGENIC', 'TOPOISOMERASE', 'TRANSCRIPTION',
    'CONFORMATIONAL', 'HETEROTETRAMER', 'NOREPINEPHRINE', 'SELENOCYSTEINE',
    'COMPLEMENTATION', 'DESENSITIZATION', 'PARASYMPATHETIC', 'PHOSPHORYLATION',
    'POLYADENYLATION', 'ULTRACENTIRFUGE', 'ACTIVATOR', 'AMINOACYL', 'AUTOCRINE', 'AUTONOMIC',
    'CYCLIC GMP', 'CHROMATIN', 'CYTOPLASM', 'ENDOCRINE', 'EUKARYOTE', 'GUANYLATE',
    'HISTAMINE', 'INTRINSIC', 'MESSENGER', 'MONOMERIC', 'PACKAGING', 'PARACRINE',
    'PHOSPHATE', 'POTASSIUM', 'RECEPTION', 'REPRESSOR', 'SCOMBROID', 'SECONDARY',
    'SYNTHESIS', 'TERMINATE', 'TETHERING', 'NICOTINIC', 'ADRENALINE', 'ALLOSTERIC',
    'ANTAGONIST', 'APPOSITION', 'AUREOMYCIN', 'BIOPOLYMER', 'CARBOXYLIC', 'DEPENDENCE',
    'ELONGATION', 'EXPRESSION', 'GANGLIONIC', 'IMMUNOBLOT', 'INITIATION', 'MUSCARINIC',
    'NARCOLEPSY', 'NUCLEOSOME', 'NUCLEOTIDE', 'POLYMERASE', 'PROKARYOTE', 'PYRIMIDINE',
    'QUATERNARY', 'REGULATION', 'STOCHASTIC', 'TELOMERASE', 'ACETYLATION', 'COMPETITIVE',
    'DEOXYRIBOSE', 'EPINEPHRINE', 'EQUILIBRIUM', 'HYDROXYLASE', 'METHYLATION',
    'POLYPEPTIDE', 'RECOGNITION', 'REPLICATION', 'SYMPATHETIC', 'TERMINATION', 'TRANSLATION',
    'DEPHOSPHORYLATION', 'METHYLTRANSFERASE', 'NEUROTRANSMITTER'
]


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 and get all solutions
solutions = solve_crossword(grid, word_bank, slots, intersections)

# Step 4: Print all solutions
print(f"Total Solutions: {len(solutions)}")
for solution in solutions:
    print_grid(solution)