Course:CPSC312-2016-Project1-Crossword
Crossword Puzzle
Authors: Theo Chitayat, Jack Mandeville, Alexander Booth
What is the problem?
To solve a crossword puzzle in the form of a constraint satisfaction problem using prolog. The contraints lie in the length of words, as well as their intersection with the other words in the puzzle. We will start with simple crosswords with a limited word bank, and expand to solve larger and more complicated crosswords.
What is the something extra?
We would like to add clues and have our program parse them ideally to get the correct word, or limit the number of possible words to make it solve faster.
What did we learn from doing this?
We learned how useful prolog is for solving constraint problems; our function to solve a crossword without clues was surprisingly efficient. However, once we expanded our knowledge base with enough words, it produced many solutions to the same board, which made the use of clues necessary. Prolog is definitely a suitable language to solve these types of problems, but it would require an extremely large database of words in order to solve any puzzle (assuming that it only uses dictionary words). On top of that, many real crosswords include cultural references, proper nouns, and acronyms that simply couldn't all be stored in the knowledge base, but this would be an issue for any language, not just prolog. The only real setback presented was that creating a board takes quite a long time, and is hard to imagine when reading the code. Creating a GUI for it would make it much quicker and easier to read, but we don't think it's possible in prolog.
Crossword Examples
We created this puzzle to be purposely ambiguous, so that our program would have to parse the clues in order to decide which words to use. For example, 1 could be either "crab" or "bear" based on the constraint intersection problem, and they are both words which are defined in our knowledge base. 3 could also be either "donkey" or "dinner", and 5 could be either "apple" or "apron".
