Solving Crossword Puzzles: Constraint Satisfaction and Backtracking

This assignment focuses on solving a crossword puzzle using constraint satisfaction techniques. The solution involves defining variables and domains, implementing backtracking search, and incorporating constraint propagation to reduce the search space. The assignment requires the creation of a method to generate the crossword puzzle and a method for arc consistency to test the status of variables. The solution integrates the arc-consistency method into the backtracking algorithm to solve the crossword problem, and the number of assignments needed after making the network arc-consistent is reported. The assignment highlights the practical application of constraint satisfaction in solving real-world problems and demonstrates the importance of efficient search strategies like backtracking and constraint propagation in AI.

Task 2. Constraint Problem Solving
For solving constraint satisfaction problems, we learnt backtracking search in the lecture. There is a
variety of constraint satisfaction problems with high practical relevance in reality beyond
cryptoarithmetic puzzles or Sudoku – all kinds of configuration or scheduling problems can be seen as
constraint satisfaction or constraint optimization problems. In this task, you shall solve a Cross Word
Puzzle as a constraint satisfaction problem.
Consider the following crossword puzzle:
A1D1 D2 D33
A2
A3
Word List:
ADD, ADO, AGE, AGO, AID, AIL, AIM, AIR, AND,
ANY, APE, APT, ARC, ARE, ARK, ARM, ART,
ASH, ASK, AUK, AWE, AWL, AYE, BAD, BAG,
BAN, BAT, BEE, BOA, EAR, EEL, EFT, FAR, FAT,
FIT, LEE, OAF, RAT, TAR, TIE
You must find six three letter words: three words read across (A1, A2, A3) and three words read‐
down (D1, D2, D3). Each word must be chosen from the given word list and can only appear once in
the puzzle.
a) Prepare data structures for variables and domains as well as methods for testing constraints,
testing whether specific values to two variables would fit together.
[There are two different ways of defining variables/domains in this problem: Each cell could be a
variable with letters as domains or the word entries with complete words as variables and‐
domains. My suggestion is to have each word entry (A1,…, D3) as a variable and entries of the
word list as possible domains.]
b) Write a method that generates a crossword puzzle by backtracking search. After each
assignment, do a simple constraint propagation. That means delete values from the domains of
the remaining unassigned variables that don’t make sense anymore with the assignment.
c) Write a method arc‐consistency as given in the lecture on Constraint Satisfaction that tests
whether the status of variables and their remaining domains is still solvable. Use this method in a
function that makes the complete crossword puzzle problem arc consistent by applying the
method to each relevant combination of variables.
d) Integrate the method that makes the crossword problem arc consistent into the backtracking‐
algorithm of task 2b and use it for solving the crossword problem. How many assignments did
you need to do after making the network arc consistent at the beginning?‐
Print the results in a readable way.