File size: 8,667 Bytes
486eff6 |
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 |
import math
from typing import List, Optional, Tuple
def place_words_in_crossword(words: List[str], size: Optional[int] = None) -> List[List[str]]:
"""
Places words in a square grid to form a crossword puzzle using backtracking.
Args:
words: List of uppercase words to place (2-15 chars each)
size: Optional grid size (n x n). If None, automatically calculated
Returns:
2D list representing the grid with letters or '.' for empty cells.
Returns empty list if placement is impossible.
"""
# Handle edge cases
if not words:
return []
# Remove duplicates and filter valid words
valid_words = list(set([word.upper() for word in words if 2 <= len(word) <= 15]))
if not valid_words:
return []
# Sort words by length descending for better placement strategy
valid_words.sort(key=len, reverse=True)
# Calculate grid size if not provided
if size is None:
# Estimate based on total character count and longest word
total_chars = sum(len(word) for word in valid_words)
min_size = max(
math.ceil(math.sqrt(total_chars * 2)), # Character density estimate
len(valid_words[0]) # Must fit longest word
)
size = min_size
# Try progressively larger grids if placement fails
max_attempts = 3
for attempt in range(max_attempts):
current_size = size + attempt
grid = _create_empty_grid(current_size)
if _place_words_backtrack(grid, valid_words, 0, []):
return grid
return [] # Failed to place all words
def _create_empty_grid(size: int) -> List[List[str]]:
"""Creates an empty grid filled with dots."""
return [['.' for _ in range(size)] for _ in range(size)]
def _place_words_backtrack(grid: List[List[str]], words: List[str],
word_index: int, placed_words: List[Tuple]) -> bool:
"""
Recursive backtracking function to place words in the grid.
Args:
grid: Current state of the grid
words: List of words to place
word_index: Index of current word being placed
placed_words: List of (word, row, col, direction) tuples for placed words
Returns:
True if all words can be placed, False otherwise
"""
# Base case: all words placed successfully
if word_index == len(words):
return True
current_word = words[word_index]
grid_size = len(grid)
# Try all possible positions and orientations
for row in range(grid_size):
for col in range(grid_size):
for direction in ['horizontal', 'vertical']:
if _can_place_word(grid, current_word, row, col, direction):
# Place the word
original_state = _place_word(grid, current_word, row, col, direction)
placed_words.append((current_word, row, col, direction))
# Recursively try to place remaining words
if _place_words_backtrack(grid, words, word_index + 1, placed_words):
return True
# Backtrack: remove the word and restore grid state
_remove_word(grid, current_word, row, col, direction, original_state)
placed_words.pop()
return False
def _can_place_word(grid: List[List[str]], word: str, row: int, col: int, direction: str) -> bool:
"""
Checks if a word can be placed at the given position and direction.
Args:
grid: Current grid state
word: Word to place
row, col: Starting position
direction: 'horizontal' or 'vertical'
Returns:
True if word can be placed, False otherwise
"""
grid_size = len(grid)
word_len = len(word)
# Check if word fits in grid bounds
if direction == 'horizontal':
if col + word_len > grid_size:
return False
# Check each position
for i, char in enumerate(word):
current_cell = grid[row][col + i]
if current_cell != '.' and current_cell != char:
return False
else: # vertical
if row + word_len > grid_size:
return False
# Check each position
for i, char in enumerate(word):
current_cell = grid[row + i][col]
if current_cell != '.' and current_cell != char:
return False
# Additional validation: ensure word doesn't create invalid adjacent letters
return _validate_word_placement(grid, word, row, col, direction)
def _validate_word_placement(grid: List[List[str]], word: str, row: int, col: int, direction: str) -> bool:
"""
Validates that placing a word doesn't create invalid letter adjacencies.
"""
grid_size = len(grid)
if direction == 'horizontal':
# Check cells before and after the word
if col > 0 and grid[row][col - 1] != '.':
return False
if col + len(word) < grid_size and grid[row][col + len(word)] != '.':
return False
# Check perpendicular adjacencies
for i, char in enumerate(word):
current_col = col + i
if grid[row][current_col] == '.': # Only check empty cells
# Check above and below
if row > 0 and grid[row - 1][current_col] != '.' and not _has_crossing_word(grid, row - 1, current_col, 'vertical'):
return False
if row < grid_size - 1 and grid[row + 1][current_col] != '.' and not _has_crossing_word(grid, row + 1, current_col, 'vertical'):
return False
else: # vertical
# Check cells before and after the word
if row > 0 and grid[row - 1][col] != '.':
return False
if row + len(word) < grid_size and grid[row + len(word)][col] != '.':
return False
# Check perpendicular adjacencies
for i, char in enumerate(word):
current_row = row + i
if grid[current_row][col] == '.': # Only check empty cells
# Check left and right
if col > 0 and grid[current_row][col - 1] != '.' and not _has_crossing_word(grid, current_row, col - 1, 'horizontal'):
return False
if col < grid_size - 1 and grid[current_row][col + 1] != '.' and not _has_crossing_word(grid, current_row, col + 1, 'horizontal'):
return False
return True
def _has_crossing_word(grid: List[List[str]], row: int, col: int, direction: str) -> bool:
"""
Checks if there's a word crossing at the given position in the specified direction.
"""
# This is a simplified check - in a full implementation, you'd track placed words
return True # For now, allow crossings
def _place_word(grid: List[List[str]], word: str, row: int, col: int, direction: str) -> List[Tuple]:
"""
Places a word in the grid and returns the original state for backtracking.
Returns:
List of (row, col, original_char) tuples for restoration
"""
original_state = []
if direction == 'horizontal':
for i, char in enumerate(word):
original_state.append((row, col + i, grid[row][col + i]))
grid[row][col + i] = char
else: # vertical
for i, char in enumerate(word):
original_state.append((row + i, col, grid[row + i][col]))
grid[row + i][col] = char
return original_state
def _remove_word(grid: List[List[str]], word: str, row: int, col: int,
direction: str, original_state: List[Tuple]) -> None:
"""
Removes a word from the grid by restoring the original state.
"""
for r, c, original_char in original_state:
grid[r][c] = original_char
# Example usage
if __name__ == "__main__":
# Test with simple words
words = ["CAT", "DOG", "ACT"]
grid = place_words_in_crossword(words)
if grid:
print("Generated crossword grid:")
print('\n'.join(' '.join(row) for row in grid))
else:
print("Could not generate crossword grid")
print("\n" + "="*30 + "\n")
# Test with longer words
words2 = ["HELLO", "WORLD", "PYTHON"]
grid2 = place_words_in_crossword(words2)
if grid2:
print("Generated crossword grid for longer words:")
print('\n'.join(' '.join(row) for row in grid2))
else:
print("Could not generate crossword grid for longer words") |