Crossword Construction using Constraint Satisfaction and Simulated Annealing
Name
Pavel Tomozov
Abstract
The main goal of this thesis is to create a program that allows constructing crosswords, using
two different algorithms. Given a grid and a text file with words (dictionary), the program
should search for suitable words from a dictionary to fill the grid. The program should be able
to complete this task in two different ways, in this case using constraint satisfaction method
(CSM) with greedy algorithm and simulated annealing.
Afore-mentioned algorithms were chosen mainly for educational purposes, since construction
of the fastest algorithm is not a goal of this work. Along with other similar Artificial
Intelligence problems, like N queens problem, map colouring and Sudoku solving (which is
also NP-complete problem), crossword construction is a good example of simple, yet
nontrivial task.
The choice of CSM with greedy algorithm is obvious. If there are no constraints, the program
will simply try to fill each entry by placing up to all, and that means also the words that are
of inappropriate length, words in vocabulary until it finds first suitable or runs out of words.
For example, by putting constraints on words length and already filled letters, the
construction time can be drastically reduced.
The simulated annealing was chosen with intention to show that the same problem can be
solved in different ways and also to illustrate the difference in algorithm processing and its
effectiveness. In addition, simulated annealing is quite similar to greedy algorithm, thus
making their comparison a bit easier, but more interesting.
Graduation Thesis language
English
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Mare Koit
Defence year
2013