Created in less than 24 hours by Akshay Joshi, Joseph Cai, Aiden Cohen, and Sriram Bharadwaj for CheeseHacks 2023
Endless Crossword is your ticket to a world of limitless, procedurally-generated crosswords, featuring clues sourced from prestigious publications like the New York Times and more!
Endless Crossword has many exciting features, including:
- Revolutionary Puzzles: Our algorithm conjures up crossword puzzles that are always new and one-of-a-kind.
- Unlimited Play: Say goodbye to waiting every day for a new crossword. With just a click of the Generate Button, a new puzzle is instantly created.
- Tailored Challenge: Endless Crossword lets you choose from a spectrum of difficulty levels.
- Easily Share: Send your generated crossword to your friends using the unique seed found right on the webpage.
- Solve Like a Pro: Stuck on a tricky clue? Endless Crossword has a range of tools to assist you when you get stuck, including Generative AI to substitute clues on the fly.
UPDATE 7/28/24 - Endless Crossword is no longer live.
We created an application using Vite and Svelte for the frontend. We also used ReactAdapter to integrate React components within our Svelte application. JavaScript eventBus was used to communicate between the React and Svelte components.
Endless Crossword's backend is made using Python, Flask, SQLite, Docker deployed to Render.
Our crossword generating algorithm implements the methods described in this paper Crossword generating and solving is a form of a Constraint Satisfaction Problem (CSP), which is NP-Complete. A naive backtracking solution would take immense amount of computation to yield a valid grid. However, we can use several heuristics to make the search much faster.
- Forward checking: use current instantiations of variables to prune domains of variables that have not yet been instantiated.
- Dynamic variable ordering (DVO): attempts to select the best variables to explore at every point in the search. In our implementations, we used the minimum remaining values (MRV) heuristic, which selects variables to instantiate whose remaining domains of possible values are smallest.
- Conflict-directed backjumping (CBJ): maintains a list of the levels in the search with which every variable conflicts.
We wrote the algorithm in C and used bit maps to massively speed up the algorithm. The algorithm uses the wordlist from this dataset which has over 6 million clues and 400k unique words. We found that a large dictionary is critical to the runtime of the algorithm.