Project: Crossword Generator
Project: Crossword Generator
Project: Crossword Generator
Programmation Structurée
1 Preamble
The objective of this project is to implement a program that generates crosswords. We consider
crosswords in a non-compact format, as depicted in Figure 1. The program picks words from a
given lexicon and lays them out in a way that respects crossword rules. Note that, from a player
point-of-view, the program actually generates the solution to a crossword. Furthermore, here we
do not consider the problem of providing hints for the player to ll the crossword.
crispy
h
choreography
r u
t t
luckier h
n e
films n
t
i
court
2 Crossword generation
Generating a balanced crossword in an ecient manner is actually a very dicult problem. We
will now detail a simple brute-force solution. First, we assume that:
The lexicon is read from a le;
The program stores the crossword in a matrix (with many empty cells).
2. Pick a new word from the lexicon and iterate on each matrix cell until you nd a valid
starting cell for that word;
3. Repeat the previous step with new words.
Figure 2 details a set of invalid crosswords, where the word depicted in red is laid out
incorrectly. These examples should help you determine the criteria for a cell to be a valid
starting cell for a given word. In these examples, we are trying to add the word crispy to an
existing crossword.
1
s s
crispy h harder
choreography o a
choreography crispy crispyi
t t n
(a) No intersection
(b) Conict with neigh- (c) Conict at the
bouring words end
lexicon-american : an american lexicon. This lexicon is very large, and probably should not
be used directly for your tests. Instead, you can generate a smaller random lexicon from it
using command shuf (see man shuf).
3 Your work
You must write a command-line tool that generates crosswords. The tool must support the
following features:
2. Generate a dummy crossword, that lays out words of the lexicon without checking for validity
constraints. This is a meant as a way for you to perform some simple preliminary tests. You must
provide two dierent modes: in the horizontal mode, there is one word per line. In the vertical mode,
there is one word per column;
3. Generate a crossword following the method described in the previous section. Check for validity
constraints before adding a new word to the crossword;
4. (Bonus) Add a playable mode. In this mode, when printing the crossword, letters are initially
replaced by '*'. The words used for the crossword are also displayed (but not their position). The player
wins when successfully guessing the start position of each word;
4 Evaluation
You must work as a pair with another student (binômes). No trio is allowed. This student
must be in the same group as you (TP group). This implies that some students will work on
their own. Evaluation will be more generous to them. Please ll out this form as soon as
possible to specify who is working with who.
We will evaluate your work based on an archive that must respect the following constraints:
The archive must be in either format .zip or .tgz;
2
Deposit the archive on the NextCloud website of the University: https://nextcloud. univ-
lille.fr/
The deadline for the deposit is 07/01/2022 (any time of the day).
The following criteria will be taken into account to evaluate the quality of your code:
Time/space complexity;
No magic numbers (check the web in case you do not know this
term); Variable and procedure names are explicit;
No code duplication.