Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Recursive solution in Clear category for Crossword Solver by Leonix
from collections import defaultdict
def solver(crossword, words):
return recursive_solver(tuple(crossword), dict_by_len(words))
def dict_by_len(words):
""" dict of lists with words arranged by length """
words_dict = defaultdict(set)
for w in words:
words_dict[len(w)].add(w)
return words_dict
def recursive_solver(crossword, words_dict):
# Find a place to insert a word. When not found, the crossword is solved.
word_template, row, col, direction = find_unsolved(crossword)
if not word_template:
return crossword
# Try all possible options for a single word place,
# then recursively call self to fill in the rest.
for candidate in words_dict[len(word_template)]:
if matches(candidate, word_template):
result = recursive_solver(replace_cells(crossword, row, col, direction, candidate), remove_word(words_dict, candidate))
if result:
return result
return None
def find_unsolved(crossword):
""" Find a suitable place to insert a word. """
candidates = [(word, row, col, 'right') for word, row, col in find_unsolved_horizontal(crossword)]
candidates += [(word, row, col, 'down') for word, col, row in find_unsolved_horizontal(transposed(crossword))]
if not candidates:
return (None,)*4
return max(candidates, key=lambda t: [count_letters(t[0]), len(t[0])])
def find_unsolved_horizontal(crossword):
for row, row_string in enumerate(crossword):
for word in row_string.split('X'):
if len(word) > 2 and '.' in word:
yield word, row, row_string.index(word)
def count_letters(word):
return sum(1 for c in word if c != '.')
def matches(candidate, word_template):
return all((c1 == '.' or c1 == c2) for c1, c2 in zip(word_template, candidate))
def replace_cells(crossword, row, col, direction, word):
""" Return a copy of `crossword` overwriting given `word` at given position. """
if direction != 'right':
row, col, crossword = col, row, transposed(crossword)
assert isinstance(crossword, tuple)
crossword = list(crossword)
newrow = list(crossword[row])
newrow[col:col+len(word)] = word
crossword[row] = "".join(newrow)
if direction != 'right':
return transposed(crossword)
else:
return tuple(crossword)
def remove_word(words_dict, word):
""" Return a copy of `words_dict` without given word. """
new_words_dict = words_dict.copy()
new_words_dict[len(word)] = words_dict[len(word)].copy()
new_words_dict[len(word)].remove(word)
return new_words_dict
def transposed(crossword):
return tuple(map("".join, zip(*crossword)))
April 4, 2016
Comments: