Constraint Satisfaction Problems: Solving Crossword Puzzles

Todd Sullivan, Harry Robertson, Pavani Vantimitta
Stanford's Reasoning Methods in Artificial Intelligence Course
Project 2 of 4
Stanford Department of Computer Science

In this project we created a CSP solver to solve crossword puzzles. As our project's feedback shows, our implementation was the fastest out of all seven groups. In some cases, we were 10 times faster than the second place team and almost 4,000 times faster than the worst performing team! Our performance is especially exciting for me since, as the contribution section details, I implemented all optimizations and the majority of the code base.

We were given no starter code for the assignment. We were only given a plain text file containing one word on each line (the dictionary), and a printout containing images of the four crossword puzzles (see the project description).

Technical Report

Member Contributions

The following list details all group contributions. These contributions were not the original tasks assigned to each group member, but were the end result due to each member's abilities and other issues.

  • Harry and I pair programmed the forward checking functionality.
  • Pavani and I pair programmed the AC3 functionality.
  • I implemented all optimizations and all other portions of the code base.
  • I performed all experiments, collected all data, and organized all results.
  • Pavani wrote the introduction and algorithm descriptions for the report (Sections 1 and 2).
  • I wrote the optimizations and experimental method sections of the report (Sections 3 and 4).
  • Harry and I discussed the results while Harry wrote the results analysis section of the report (Sections 5 and 6).
  • Harry edited Pavani's portion of the report (Sections 1 and 2) and my portion of the report (Sections 3 and 4).
  • I edited Harry's portion of the report (Sections 5 and 6).
  • Pavani converted the Excel-based results tables to a Word document.
  • I created the sample solutions document.
  • I applied all formatting and presentation features to the report and annex.

Source Code

Since this assignment will be used in future versions of the reasoning methods course, I am not releasing the code at this time.