uab-projects / crossword

Project to learn and understand backtracking algorithms with the goal to solve a crossword puzzle

Crossword Solver

What is Crossword Solver?

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.

The algorithm

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

What can the Crossword Solver do?

1. Solve a crossword board (read from a file)
2. 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.
3. 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)

About the code

The code is written in Python 3, and requires some libraries (available in PyPi):

Libraries

Required

The following libraries are required for the software to run:

• numpy

Optional

The following libraries must be present if you want to generate crossword puzzles based on an online dictionary

• mwapi
• beautifulsoup4

Running the application

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 -h

The -h argument will help you to discover how the software works and what it can do for you

License

The code is licensed under Apache Software Foundation (ASF) License v2.0

Made with love in ETSE, UAB by @ccebrecos & @davidlj

crossword's Issues

Problem of 'stty'

I met the problem of 'stty' is not recognized as an internal or external command,
operable program or batch file. How to fix it?