from __future__ import annotations from dataclasses import dataclass import sys import time from typing import Dict, Iterable, List, Optional, Sequence, Set, Tuple Coordinate = Tuple[int, int] Grid = Dict[Coordinate, str] WORDS = [ "automobile", "re", "magia", "montagna", "principe", "ambiente", "per", "calcio", "pesce", "cane", "vedere", "finestra", "ancora", "altro", "volta", "atleta", "sempre", "nuovo", "libro", ] HORIZONTAL = "H" VERTICAL = "V" @dataclass(frozen=True) class Placement: word: str x: int y: int direction: str intersections: int @property def cells(self) -> List[Coordinate]: if self.direction == HORIZONTAL: return [(self.x + offset, self.y) for offset in range(len(self.word))] return [(self.x, self.y + offset) for offset in range(len(self.word))] @dataclass class CrosswordState: grid: Grid placements: List[Placement] intersections: int def copy(self) -> "CrosswordState": return CrosswordState( grid=dict(self.grid), placements=list(self.placements), intersections=self.intersections, ) @property def placed_words(self) -> int: return len(self.placements) def bounds(self) -> Tuple[int, int, int, int]: xs = [x for x, _ in self.grid] ys = [y for _, y in self.grid] return min(xs), min(ys), max(xs), max(ys) def area(self) -> int: x_min, y_min, x_max, y_max = self.bounds() return (x_max - x_min + 1) * (y_max - y_min + 1) def score(self) -> Tuple[int, int, int]: # Maximize placed words first, then intersections, then prefer compact grids. return (self.placed_words, self.intersections, -self.area()) class CrosswordGenerator: def __init__( self, words: Sequence[str], *, max_candidates_per_word: int = 12, time_limit_seconds: float = 8.0, ) -> None: normalized = [self._normalize(word) for word in words] unique_words = list(dict.fromkeys(word for word in normalized if len(word) >= 2)) self.words = sorted(unique_words, key=lambda word: (-len(word), word)) self.best_state = CrosswordState(grid={}, placements=[], intersections=0) self.max_candidates_per_word = max_candidates_per_word self.time_limit_seconds = time_limit_seconds self.started_at = 0.0 self.visited: Dict[Tuple[frozenset, Tuple[str, ...]], Tuple[int, int, int]] = {} self.nodes_visited = 0 self.spinner_frames = ["-", "/", "|", "\\"] self.spinner_index = 0 self.last_spinner_update = 0.0 @staticmethod def _normalize(word: str) -> str: return word.strip().lower() @staticmethod def _step(direction: str) -> Coordinate: return (1, 0) if direction == HORIZONTAL else (0, 1) @staticmethod def _perpendicular(direction: str) -> Coordinate: return (0, 1) if direction == HORIZONTAL else (1, 0) @staticmethod def _build_letter_index(words: Sequence[str]) -> Dict[str, Set[str]]: index: Dict[str, Set[str]] = {} for word in words: for letter in set(word): index.setdefault(letter, set()).add(word) return index def solve(self) -> CrosswordState: if not self.words: return self.best_state self.started_at = time.perf_counter() self.last_spinner_update = self.started_at self.nodes_visited = 0 first_word = self.words[0] initial_state = self._place_first_word(first_word) self.best_state = initial_state remaining = [word for word in self.words if word != first_word] self._search(initial_state, remaining) self._clear_spinner() return self.best_state def _place_first_word(self, word: str) -> CrosswordState: grid = {(offset, 0): letter for offset, letter in enumerate(word)} placement = Placement(word=word, x=0, y=0, direction=HORIZONTAL, intersections=0) return CrosswordState(grid=grid, placements=[placement], intersections=0) def _search(self, state: CrosswordState, remaining_words: Sequence[str]) -> None: self.nodes_visited += 1 self._tick_spinner(state) if time.perf_counter() - self.started_at > self.time_limit_seconds: return if state.score() > self.best_state.score(): self.best_state = state.copy() if not remaining_words: return if state.placed_words + len(remaining_words) < self.best_state.placed_words: return if state.placed_words + len(remaining_words) == self.best_state.placed_words: max_possible_intersections = state.intersections + sum(len(word) for word in remaining_words) if max_possible_intersections <= self.best_state.intersections: return signature = (frozenset(state.grid.items()), tuple(sorted(remaining_words))) best_seen = self.visited.get(signature) if best_seen is not None and best_seen >= state.score(): return self.visited[signature] = state.score() next_word = self._select_next_word(state, remaining_words) candidates = self._generate_candidates(state, next_word) if not candidates: self._search(state, [word for word in remaining_words if word != next_word]) return candidates.sort( key=lambda placement: ( placement.intersections, len(placement.word), -self._candidate_area_after(state, placement), ), reverse=True, ) candidates = candidates[: self.max_candidates_per_word] next_remaining = [word for word in remaining_words if word != next_word] for placement in candidates: child_state = self._apply_placement(state, placement) self._search(child_state, next_remaining) # Also explore skipping the current word, but only after trying all placements. self._search(state, next_remaining) def _tick_spinner(self, state: CrosswordState) -> None: now = time.perf_counter() if now - self.last_spinner_update < 0.08: return frame = self.spinner_frames[self.spinner_index] elapsed = now - self.started_at message = ( f"\r{frame} elaborazione... " f"nodi={self.nodes_visited} " f"migliore={self.best_state.placed_words} parole, {self.best_state.intersections} incroci " f"attuale={state.placed_words} parole " f"t={elapsed:0.1f}s" ) print(message, end="", file=sys.stderr, flush=True) self.spinner_index = (self.spinner_index + 1) % len(self.spinner_frames) self.last_spinner_update = now @staticmethod def _clear_spinner() -> None: print("\r" + " " * 120 + "\r", end="", file=sys.stderr, flush=True) def _select_next_word(self, state: CrosswordState, remaining_words: Sequence[str]) -> str: ranked_words = sorted( remaining_words, key=lambda word: ( -sum(1 for letter in set(word) if letter in state.grid.values()), -len(word), word, ), ) best_word = ranked_words[0] best_key: Optional[Tuple[int, int, int, str]] = None for word in ranked_words[:5]: candidate_count = len(self._generate_candidates(state, word)) key = ( 0 if candidate_count > 0 else 1, candidate_count if candidate_count > 0 else 10**9, -len(word), word, ) if best_key is None or key < best_key: best_key = key best_word = word return best_word def _generate_candidates(self, state: CrosswordState, word: str) -> List[Placement]: if not state.grid: return [Placement(word=word, x=0, y=0, direction=HORIZONTAL, intersections=0)] candidates: Dict[Tuple[int, int, str], Placement] = {} for index, letter in enumerate(word): for x, y in self._cells_with_letter(state.grid, letter): for direction in (HORIZONTAL, VERTICAL): start_x = x - index if direction == HORIZONTAL else x start_y = y if direction == HORIZONTAL else y - index placement = self._validate_placement(state.grid, word, start_x, start_y, direction) if placement is None: continue candidates[(placement.x, placement.y, placement.direction)] = placement return list(candidates.values()) @staticmethod def _cells_with_letter(grid: Grid, letter: str) -> Iterable[Coordinate]: for coordinate, grid_letter in grid.items(): if grid_letter == letter: yield coordinate def _validate_placement( self, grid: Grid, word: str, start_x: int, start_y: int, direction: str, ) -> Optional[Placement]: dx, dy = self._step(direction) pdx, pdy = self._perpendicular(direction) intersections = 0 before = (start_x - dx, start_y - dy) after = (start_x + dx * len(word), start_y + dy * len(word)) if before in grid or after in grid: return None for offset, letter in enumerate(word): x = start_x + dx * offset y = start_y + dy * offset current = grid.get((x, y)) if current is not None: if current != letter: return None intersections += 1 continue side_a = (x + pdx, y + pdy) side_b = (x - pdx, y - pdy) if side_a in grid or side_b in grid: return None if intersections == 0 and grid: return None return Placement( word=word, x=start_x, y=start_y, direction=direction, intersections=intersections, ) def _apply_placement(self, state: CrosswordState, placement: Placement) -> CrosswordState: child = state.copy() dx, dy = self._step(placement.direction) for offset, letter in enumerate(placement.word): x = placement.x + dx * offset y = placement.y + dy * offset child.grid[(x, y)] = letter child.placements.append(placement) child.intersections += placement.intersections return child def _candidate_area_after(self, state: CrosswordState, placement: Placement) -> int: xs = [x for x, _ in state.grid] ys = [y for _, y in state.grid] pxs = [x for x, _ in placement.cells] pys = [y for _, y in placement.cells] if not xs: return len(placement.word) x_min = min(min(xs), min(pxs)) x_max = max(max(xs), max(pxs)) y_min = min(min(ys), min(pys)) y_max = max(max(ys), max(pys)) return (x_max - x_min + 1) * (y_max - y_min + 1) def render_grid(grid: Grid, placements: Sequence[Placement]) -> str: if not grid: return "(griglia vuota)" x_min = min(x for x, _ in grid) x_max = max(x for x, _ in grid) y_min = min(y for _, y in grid) y_max = max(y for _, y in grid) header = " " + " ".join(f"{x:>2}" for x in range(x_min, x_max + 1)) separator = " " + " ".join("--" for _ in range(x_min, x_max + 1)) lines = [header] lines.append(separator) for y in range(y_min, y_max + 1): row = [f"{y:>3} "] for x in range(x_min, x_max + 1): row.append(grid.get((x, y), ".").upper().rjust(2)) lines.append(" ".join(row)) lines.append("") lines.append("Parole inserite:") for index, placement in enumerate(sorted(placements, key=lambda item: (item.y, item.x, item.direction)), start=1): direction = "orizzontale" if placement.direction == HORIZONTAL else "verticale" lines.append( f"{index:>2}. {placement.word.upper():<12} ({placement.x:>2}, {placement.y:>2}) {direction}, " f"intersezioni: {placement.intersections}" ) return "\n".join(lines) def main() -> None: generator = CrosswordGenerator(WORDS) solution = generator.solve() print("Miglior soluzione trovata") print(f"Parole inserite: {solution.placed_words}/{len(generator.words)}") print(f"Intersezioni totali: {solution.intersections}") print(f"Area occupata: {solution.area()}") print() print(render_grid(solution.grid, solution.placements)) if __name__ == "__main__": main()