Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS resolution order and backtracking solution in Clear category for Crossword Solver by Phil15
import itertools as it # groupby (mostly), chainobject
def prepare_words(words, lengths):
"""{3: [words of length 3], ...} (only for the given lengths)."""
# "words" may be big so I prefer iterate only once on it.
words_by_len = {length: [] for length in set(lengths)}
for word in words:
if len(word) in words_by_len:
words_by_len[len(word)].append(word)
return words_by_len
def find_places(crossword):
"""Find where words are in the empty crossword."""
places = []
# Horizontal places.
for row, line in enumerate(crossword):
places.extend([(row, col) for col, _ in group]
for empty, group in it.groupby(enumerate(line),
key=lambda x: x[1] == '.')
if empty)
# Vertical places.
for col, line in enumerate(zip(*crossword)):
places.extend([(row, col) for row, _ in group]
for empty, group in it.groupby(enumerate(line),
key=lambda x: x[1] == '.')
if empty)
# Single letters are not words. Use tuples to use them in a set later.
return [tuple(p) for p in places if len(p) > 1]
def resolution_path(places):
"""Determine a great way to fill the crossword."""
# All words are connected in tests, so a single BFS is enough.
# Resolution is way faster than with a DFS path.
visited = set()
queue = [places[0]]
while queue:
place = queue.pop(0)
if place not in visited:
yield place
visited.add(place)
# Add unvisited places connected to the current place.
queue.extend(p for p in places if p not in visited
and set(p) & set(place))
def solver(crossword, words):
"""Fill the crossword with some given words."""
print_grid(crossword)
places = find_places(crossword)
path = list(resolution_path(places))
visualize(crossword, path) # Visualize how the crossword will be filled.
words = prepare_words(words, map(len, places))
grid = dict.fromkeys(it.chain.from_iterable(places), '')
used_words = set()
# "rc" is a position (row, col) in the grid.
def possible_words(place):
"""
Generate words we can use at the given place (and backtracking moment),
and changes it would bring to the grid.
"""
for word in words[len(place)]:
if word in used_words:
continue # We would use this word twice.
okay, changes = True, []
for rc, letter in zip(place, word):
if grid[rc] != letter:
if grid[rc]:
okay = False # We would change a letter in the grid.
break
changes.append((rc, letter))
if okay:
yield word, changes
def backtracking(index=0):
"""Fill places in path order, in a backtracking way."""
for word, changes in possible_words(path[index]):
# Put the word at this place.
used_words.add(word)
for rc, letter in changes:
grid[rc] = letter
# Try to fill other places in the grid.
if index == len(path) - 1 or backtracking(index + 1):
return True
# Can't fill the grid with this word: remove it from this place.
used_words.remove(word)
for rc, letter in changes:
grid[rc] = ''
backtracking()
result = tuple(''.join(grid.get((r, c), symb)
for c, symb in enumerate(row))
for r, row in enumerate(crossword))
print_grid(result)
return result
# Helper functions
def print_grid(grid):
for row in grid:
print(row.replace('X', ' '))
print()
def visualize(crossword, path):
"""Just visualize the resolution path."""
grid = list(map(list, crossword))
for label, place in zip('123456789ABCDEF', path):
for r, c in place:
if grid[r][c] == '.':
grid[r][c] = label
print_grid(map(''.join, grid))
April 8, 2020
Comments:
