Crossy

Crossy is an interactive automated crossword generator. A user can specify a theme, which provides seed words to feed the crossword generation. Users can generate all kinds of unique boards!

Comment

Inspiration

Our group wanted to explore a topic outside of a simple web app or anything that required a call to GPT. All of us are interested in crosswords, and after talking to our friend on the Michigan Daily (who writes the crosswords), we were inspired and given apt advice on how to think about the construction. Additionally, we found this was an extremely difficult problem, one that did garner a lot of interest.

What it does

Our project has a basic front end that will take in user input, which defined a theme. From there, we generate a few seed words based off that theme to help build our crossword. These seed words are generated from our ML model, that analyzes common crossword answer/clue pairings, and prunes seldom used ones. We then make a call to a crossword building website, Crosserville, which can take in a specified size and any specific word lengths. (which come from our generated words) Once we read that into a file, we then pass it into "Ingrid," a Rust package that can fill in a crossword with words from a specified word list and given "priorities." After that, we construct both a JSON that our front end reads from to generate the crossword, as well as a PDF of the crossword and its solution.

How we built it

We started by first looking into different Python packages to build a physical crossword, relying initially on blacksquare to do so. Our initial ideas for generation included building a graph of a random sample of n words, and then connected them via similarity/shared letters. We found this method was a bit too over the top, and required a lot of edge cases. We then shifted to exploring other options: another being a web scraping method to try and build a board that we got online. This was more fruitful, but we found that we may want to more easily generate boards. Finally, after playing around with some web tools, we found we can make a curl request and some scraping to get the board, then change it into a different format.

From here, we found another tool that can fill in a crossword given an input of "."'s and "#"'s, and even starter words. Using our ML model to generate common and themed words, we pass that in and obtained a now filled crossword. From here, we do two final things on the backend: Create a JSON of the word/clue/direction/position for each one, and also a PDF as well, just for comparison.

The front end we found online as an existing implementation. This was an already built, interactive crossword game. (Built in Svetle, i.e. JavaScript) For this part, we did two simple things: One, build an input bar to send a theme from the user to the python backend. Two, obtain the output JSON and generate the new Crossword.

Challenges we ran into

The biggest hurdle was the actual generation of some crossword with spaces and blocks. This is an NP-Complete problem, and required a lot of bookkeeping and overhead to handle. This cost us time, as we realized we could make a simple request to an existing implementation that generates a board.

We also ran into issues trying to fine-tune our model, as some of the clues we were getting were very esoteric and hard to decipher. This was done by addressing our ML model, and fine-tuning/preprocessing our data further.

One of the last issues we faced was trying to insert the generated words. It is not guaranteed that the words will fit completely with each other when the board is generated. (since if they have to intersect: we need to both have enough space AND have any intersections that occur be consistent, i.e. sharing the same letter in said space) We ended up taking a more liberal approach, by fitting in as much as possible, then just cutting down if we could not fit all the words.

Accomplishments that we're proud of

We were able to leverage existing tooling to generate the crossword via Rust, and then process it in our own Python libraries, that allow any generation to be properly filled. This was one of our best moments, as we were worried about the representations and building from the start. We also had great success find-tuning our model, and being able to filter our obscure clues and focus more on mainstream ones (i.e. NYT, New Yorker)

What we learned

We learned a lot about crossword construction and the difficulty that automating it requires. Because crossword solving is NP-Complete, and thus construction is too via a simple reduction, we realized a bit late that trying to redo this design took too much time. Another thing we learned was how Python can effectively interact with multiple different languages besides C/C++/JavaScript, namely, Rust. This was exciting, since only a couple of us had Rust experience, and got to understand cargo package management and how it can fit into non-Rust projects. Lastly, we gained an understanding (at a basic level) of Svetle, an open-source front-end framework.

What's next for Crossy

We want to continue refactoring our model to provide more unique clues and words, as well as exploring different datasets for more unique designs. Additionally, we want to explore a way to effectively insert existing clues into the board, rather than our simplifying assumption. We loved building this, and hope you enjoy it!

Share this project:

Updates