Add a SAT-solver-based crossword solver plugin
Why?
- To see if it's possible (as far as I understand it should be)
- If it's possible, see how fast it is
- Because it sounds fun
What?
- New solver + plugin to add in
croiseur-solver
folder. - No architecture/external interface impact, the solver will be usable like the others.
How?
That's the hard part. Naively, I would get started with these steps:
-
Express the problem as a SAT problem -
Select a SAT solver -
Feed the problem to the SAT solver -
Translate the solution back to a crossword puzzle
See also
- Phil which is a crossword maker using a modified version of a SAT solver called Glucose.
- SAT4j a SAT solver in Java.
- NP-Completeness
Edited by Antoine Belvire