Correction Devoir maison 1 - Crossword puzzle

The Problem

A crossword puzzle consists of a dictionary in form of a list of words and of a grid with empty cells, represented by dots, or blocked cells, represented by a hashtag. For convenience we assume that the grid is surrounded with blocked cells, which makes the implementation a bit easier.

A segment is a maximal sequence of empty consecutive cells in a same row or column and of length at least 2. The goal is to assign letters to the empty grid cells such that every segment corresponds to a word of the dictionary.

The Model

One possible model would be to introduce a variable for every cell, and a constraint for every segment asking that the word resulting in the concatenation of its cells is in the dictionary. The problem with this model is that the constraints involve more than 2 variables and we cannot use our constraint programming solver for this model.

Another possible model would be to introduce a variable for every segment, where its domain is the set of all words in the dictionary of the corresponding length. There would be a constraint for every pair of intersecting segments asking that the words have the same letter at the intersection. The problem with this model is that it has variables with huge domains. This results in an inefficient resolution, as there are many possibilities to explore for every node in the search tree.

The natural improvement is to combine both models. Now for every cell C and segment S such that S contains C at position pos, there is a constraint forcing the letter of S in position pos to be exactly the letter C. This is the model that we implemented.

The Implementation

We read the dictionary line by line, transform each word into lower case letters and store them in a python dictionary words associating to every length the set of words of this length. Here are the number of words of each length from the input file.

len	number
2	49
3	535
4	2235
5	4171
6	6171
7	7363
8	7073
9	6082
10	4592
11	3069
12	1880
13	1137
14	545
15	278
16	103
17	57
18	23
19	3
20	3
21	2
22	1
23	0
24	0
25	0
26	0
27	0
28	1

These numbers confirm that we don’t want a model with only segment variables. The input dictionary is read as follows.

from collections import defaultdict
from string import ascii_lowercase

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
f = open(words_file, "r")
for s in f:
    s = s.strip()     # remove white spaces
    l = len(s)
    s = s.lower()     # convert to lower case letters
    words[l].add(s)
    for pos in range(l):
        relation[l, pos].add((s, s[pos]))

We denote the variables by triplets (i,j,l), corresponding to the cell at coordinates (i,j) if l is zero, or corresponding to a horizontal segment of length l starting at (i,j) if l is positive, or corresponding to a vertical segment of length -l starting at (i,j) if l is negatif.

The segments are detected by scanning the rows and columns in the grid and remembering in a variable start the beginning of the segment. Note that we allow the grid to have some cells forced to given letters.

from string import ascii_lowercase

alphabet = set(ascii_lowercase)

BORDER = '#'
EMPTY = '.'

var = {}

# declare cell variables
for i in rows:
    for j in cols:
        if grid[i][j] == EMPTY:
            var[i, j, 0] = set(alphabet)
        elif grid[i][j] in alphabet:
            var[i, j, 0] = {grid[i][j]}     # force initially filled cell

# declare horizontal segment variables
for i in rows:
    start = -1
    for j in cols:
        if grid[i][j] != BORDER:
            if start == -1:
                start = j
        else:
            if start != -1:
                l = j - start
                if l >= 2:
                    var[i, start, +l] = set(words[l])
                start = -1

# declare vertical segment variables
for j in cols:
    start = -1
    for i in rows:
        if grid[i][j] != BORDER:
            if start == -1:
                start = i
        else:
            if start != -1:
                l = i - start
                if l >= 2:
                    var[start, j, -l] = set(words[l])
                start = -1

And this is how constraints are declared:

# create a constraint program
P = constraint_programming(var)

# and generate the constraints
for (i, j, l) in var:
    if l > 0:
        for pos in range(l):
            P.addConstraint((i, j, l), (i, j + pos, 0), relation[l, pos])
    elif l < 0:
        for pos in range(-l):
            P.addConstraint((i, j, l), (i + pos, j, 0), relation[-l, pos])

And to finish, this is how a the solver is called, and the solution extracted.

# P.maintain_arc_consistency()  # optional
sol = P.solve()

if sol:
    for (i, j, l) in sol:
        if l == 0:
            grid[i][j] = sol[i, j, l]

    for line in grid:
        print(" ".join(line))
else:
    print("no solution")

The Experiments

We experienced the resolution with and without maintaining arc consistency. Here are the grids that we used for the experiments.

crossword1.txt
#####
##.##
#...#
##.##
#####

crossword2.txt
###############
###..........##
#.#.#.#.#.#.###
#.......#.....#
#.#.#.#.#.#.#.#
#....#........#
#.###.#.#.#.#.#
#......#......#
#.#.#.#.#.###.#
#........#....#
#.#.#.#.#.#.#.#
#.....#.......#
###.#.#.#.#.#.#
##..........###
###############

crossword3.txt
########
#......#
#......#
#..##..#
#......#
#......#
########

And made the following observations.

test file	without	with AC
crossword1.txt	<1 sec	<1 sec
crossword2.txt	1.5 sec	4 sec
crossword3.txt	60 sec	2 sec

Now let’s try to understand the results. The first crossword grid was just too easy to solve. How about the second one? We observe that using arc consistency slows the resolution down. Here is how the exploration trees created during the resolution look like.

Without arc consistency

With arc consistency

We see that the instance was quite easy to solve. The overhead of maintaining arc consistency slowed down the exploration of the search tree, and even though some unsuccessful branches where cut, it did not compensated. The number of nodes in the search tree could be reduced from 782 to 144, which gives a factor of about 5.

For the third crossword grid, the situation is quite different. The grid is hard to solve, and the solver spends most of his time in unsuccessful branches. Here arc consistency can help to cut these branches. Indeed it reduced the number of nodes in the search tree from 233800 to 60.

Honestly, these experiments are not rigorous. The performance depends a lot on the grid, and also is not deterministic, due to the arbitrary order in which Python loops over elements of a set. But at least they tell us that there is not a single answer to the question whether arc consistency helps for the problem resolution.