The aim of the project is to implement an example of a backtracking algorithm (using improvements like Forward-Checking and some heuristics). To do this, we've dealt with the crossword problem. Given a crossword board and using a dictionary of valid words in a language, then we have to find a valid solution for that crossword applying the rules of the popular crossword game.
We'll use a backtracking algorithm variation: forward-checking, with some heuristics (LWF: Largest Word First, MCV: Most Constraining Values and MRV: Minimum Remaining Values) to improve the solving speed
- Solve a crossword board (read from a file)
- Display the solving process the software applies while is solving the crossword. This helps us to check how the algorithm is working and introduce improvements based on its behaviour.
- Generate crossword puzzles given an empty crossword. We'll look for the solutions and afterwards look for the meanings of the words in an online dictionary (currently only in Wiktionary in Catalan language)
The code is written in Python 3, and requires some libraries (available in PyPi):
The following libraries are required for the software to run:
numpy
The following libraries must be present if you want to generate crossword puzzles based on an online dictionary
mwapibeautifulsoup4
The application is command-line based so, open a terminal and change into the repo's root. Then, you can run the application calling to Python interpreter into main script:
python src/main.py -hThe -h argument will help you to discover how the software works and what it can do for you
The code is licensed under Apache Software Foundation (ASF) License v2.0
Made with love in ETSE, UAB by @ccebrecos & @davidlj
