Show HN: A dense NYT-style crossword constructor using wave function collapse

• WaveFunctionCollapse

  99 22,675 4.8 C#

  Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics

Hi! In my spare time, I’ve been making Crosswyrd, a web app for quickly and simply constructing, sharing, and playing dense New York Times-style crossword puzzles. The idea for the project came when I was dabbling in procedural generation recently and came across wave function collapse, which is a procedural generation algorithm inspired by quantum mechanics. To my knowledge wave function collapse hasn’t been applied to crossword puzzle generation before, so I was excited to explore how it fared in this context. The GitHub page (https://github.com/mxgmn/WaveFunctionCollapse) explains it well--in short, the algorithm starts with a blank canvas as an output, called a “wave,” where each tile is in some superposition of states; i.e., each tile could be any of the possible tiles. In the case of a crossword puzzle, each tile can be one of 26 letters. Then, the algorithm iteratively collapses each stretch of tiles into one of its possible words--and given the rules between the tiles (i.e., each intersecting stretch of tiles, "across" and "down," must be a word in a dictionary), propagates the resulting constraints across the rest of the board--until each tile has only one state. Each iteration, Crosswyrd’s algorithm collapses the “across” or “down” stretch of tiles with the lowest average Shannon entropy. If it finds a contradiction, it backs up and tries again with a different word. If all possible words at a given step are exhausted, it backs up to the previous level to try new words and so on.

You can see this algorithm in action yourself using the Auto-Fill button. I’d recommend picking one of the preset 15x15 patterns and clicking Auto-Fill to see it go. The darker blue the tile, the lower the entropy for that tile.

In practice, I am happy with how well and quickly the algorithm generates valid puzzles, and more importantly, I think it enables the app to push back some of the complexity of thinking about how words intersect to make space for more human creativity in constructing crossword puzzles. For example, by inspecting the state of the “wave,” it suggests words to the user that might work well in the selected slot, and it offers a word bank the user can fill out to click and drag their own words into valid slots in the puzzle. Of course, you can also just type words directly into the puzzle, and Crosswyrd will propagate the new constraints across the board as you go.

A limitation of using wave function collapse for crossword constructing, as opposed to an algorithm that fully solves the puzzle, is that I can’t guarantee the user that the current puzzle state has a valid solution. For example, the user may place a word that the algorithm thinks is likely valid, only to find upon placing it that it causes a contradiction--this is because collapsing tile states causes constraints to cascade across the board, sometimes uncovering previously-unknown contradictions. However, I have some ideas for simple ways to mitigate this drawback, such as testing out the suggested words in the background as the user views them and updating the UI with the results of the tests as they come in.

Feel free to play around with building your own puzzle, even publishing and sharing it! The crossword player I built adapts to both mobile and desktop screen sizes, so puzzles made in Crosswyrd should be playable on just about any device with a web browser and a screen.

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

Suggest a related project