Mots croisés

Voici un dictionnaire. Ne gardez que les mots qui sont en minuscules et qui contiennent la lettre “k”.

Voici une grille.

###############
###..........##
#.#.#.#.#.#.###
#.......#.....#
#.#.#.#.#.#.#.#
#....#........#
#.###.#.#.#.#.#
#......#......#
#.#.#.#.#.###.#
#........#....#
#.#.#.#.#.#.#.#
#.....#.......#
###.#.#.#.#.#.#
##..........###
###############

Aides

Je propose un modèle qui combine le modèle primal et dual pour ce problème. Ayez des variables pour les cases mais également des variables pour les segments.

#   variable name: triplet of the form
#   (i, j, 0) for a cell in position (i,j)
#   (i, j, +l) for horizontal segment of length l starting at (i, j)
#   (i, j, -l) for vertical segment of length l starting at (i, j)

Stockez le dictionnaire par longueur des mots pour constituer le domaine des variables segments. Rappel on lit un fichier texte de la manière suivante.

from collections import defaultdict
from string import ascii_lowercase

from constraint_programming import constraint_program

words_file = "words2.txt"          # or sys.argv[1]

BORDER = '#'
EMPTY = '.'

alphabet = set(ascii_lowercase)
words = defaultdict(set)     # length -> set of words of this length
relation = defaultdict(set)  # (length, position i) -> set of pairs (w,w[i])

# read the dictionary
for s in open(words_file, "r"):
    s = s.strip()     # remove white spaces
    l = len(s)
    if s != s.lower() or "k" not in s:
        continue
    words[l].add(s)
    # ... fill up relation