# Prior art investigation ## Notes * I think this project should focus on manual construction aids over autofill-specific upgrades, because manual construction is always necessary, whereas autofill is a nicety that *may* be useful in certain cases. * Some of these notes are about features that are not relevant to this project. For example, PuzzleMe's AI capabilities. But I'm using this opportunity to do a complete overview of all the different crossword construction software out there. I think this document will be useful to have on hand when developing Crosswords, even outside of the GSoC context. For that reason, I'm also adding a short review of each software. ## [Qxw](https://www.quinapalus.com/qxw.html) * Exet acknowledgements mentions this editor. * Open source. * [Manual](https://www.quinapalus.com/qxw-guide-20200708.pdf). ## [Exet](https://viresh-ratnakar.github.io/exet.html) * Open source. * Analysis tab: * Grid analysis: * Miscellaneous info like symmetrical or not, number of blocked cells, any consecutive unches, etc. * Smallest horizontal and vertical [through-cut](https://github.com/viresh-ratnakar/exet#:~:text=The%20Analysis%20tab,the%20Analysis%20panel.). * Solutions words and clues analysis: * Various stats that GNOME Crosswords also has, like letter distribution, word length distribution. * Word popularity distribution. * Word stems repeated in clues. * Word lengths of clues. * Repeated substrings on grid. * Different sized red circles appear on cells to indicate how many options that cell has. Turns purple if a cell is unfillable. * Has a limited amount of [look-ahead](https://github.com/viresh-ratnakar/exet#:~:text=The%20grid%2Dfill%20suggestions%20shown,and%20also%20updates%20the%20viablots.). So if a cell can be filled with *A* to create a valid ACROSS word, but the DOWN word becomes a dead end, then *A* will not count as a possibility for the cell. (Maybe I'm misinterpreting this.) * Options for the autofill: * Minimum popularity. * Exclude proper nouns. * Avoid reusing words with common stems. * Specify preferred words for the autofill to use. * Specify blacklisted words for the autofill to never use. * Try to get a pangram (all letters used at least once). Can also specify a subgrid where you want the pangram. * Autofill lets you go step by step. So you can stop if it generates a word you don't like, change it, and then resume the autofill. * Autofill provides a bunch of data while it's running. * Shows ghost letters in cells if there's only one possible letter. * Variations of current word: * Anagrams. * Charades. * Word letter modifications (deletions, insertions, substitutions). * Homophones and spoonerisms. * Hidden answers and reverse hidden answers. * Alterations. * Lists: third-party wordplay and cryptic abbreviation lists. ### Review UI is not great. Looks outdated and is hard to navigate. But Exet has a lot of tools for word generation. I think it's probably very good for cryptics. But probably less useful for American-style crosswords. ## [CrossFire](https://beekeeperlabs.com/crossfire/) * **Summary** tab: * Number of words. * Average word length. * Number of black cells. * Number of letters. * Average word score. * Word-length counts. * Letter counts. (How many *A*, *B*, etc. are in the grid.) * Click on a letter count to highlight all occurrences of that letter in the grid. * [**Fill** tab](https://beekeeperlabs.com/crossfire/docs/index.html#FILL): * The fill tab contains the word suggestions for the current slot. It's closely integrated with the autofill algorithm. * Here is how the word [suggestion generation process](https://beekeeperlabs.com/crossfire/walkthrough.html#:~:text=Immediately%20after%20you,as%20unbolded%20%22candidates%22) works: 1. You select a slot on the grid. 2. Generating candidates: CrossFire generates words that fit into the slot and lists them for the user to see. 3. Evaluating candidates: CrossFire attempts an autofill with each candidate. This is essentially like Exet's [limited look-ahead](https://github.com/viresh-ratnakar/exet#:~:text=The%20grid%2Dfill%20suggestions%20shown,and%20also%20updates%20the%20viablots.) ability, but it goes all the way. * CrossFire removes unfillable candidates from the suggested words list. * CrossFire bolds fillable candidates. * Each suggested word has two properties that CrossFire dynamically calculates; these are calculated using the [first fill found](https://beekeeperlabs.com/crossfire/docs/index.html#:~:text=These%20scores%20are,expected%20fill%20quality.), so there's some randomness, and the quality of the scores is dependant on the time/quality configuration: * Grid score - a measure of how easy/hard it is to fill the neighbours around the word, if it's placed into the current slot. * Final score - a measure of how good a complete grid fill is, if the word is placed in the current slot. (Docs don't specify how this value is calculated. [Tutorial](https://beekeeperlabs.com/crossfire/walkthrough.html#:~:text=The%20final%20score%20numbers%20are%20formed%20by%20using%20CrossFires%20internal%20%22fill%20quality%22%20rating%20for%20each%20candidate%20and%20dividing%20it%20by%20the%20fill%20quality%20for%20the%20first%20fill%20that%20was%20found.) contains a little more info.) * Click on a word suggestion, and CrossFire will update the grid with [additional information](https://beekeeperlabs.com/crossfire/docs/index.html#:~:text=Whenever%20you%20select%20a%20potential%20fill%20word%2C%20you%20will%20see%20that%20word%20in%20the%20grid.%20You%20will%20be%20typically%20be%20shown%20other%20information%2C%20depending%20on%20the%20setting%20of%20the%20%22Fill/Show%20Sample%20Fill%22%20and%20%22Fill/Show%20Possible%20Letters%22%20menu%20items%2C%20as%20follows%3A) related to that word (configurable): * CrossFire shows the sample fill, in light grey ghost letters. * CrossFire shows forced letters in dark grey ghost letters. * Note: these are forced letters for the selected word suggestion. This is different from the brown ghost letters, which are forced letters for the grid, independent of any word suggestion. * For cells that are constrained to 2-9 letters, CrossFire shows those letters as black mini-letters. * If you enter a word suggestion into a slot, and then undo, CrossFire highlights that word suggestion yellow, in the suggestions list. This lets you know that you tried that word suggestion and it didn't work out. * You can also manually mark word suggestions as either good (green) or bad (red). * The fill tab indicates if a grid is unfillable. * This is useful to prevent you from going down a path that you don't realize is unfillable. * The only negative I can think of for this is this: Let's say that CrossFire says your current grid is unfillable. But, there's actually a word you know of that would make it fillable. It's just not in the word list. But all you see is that the grid is unfillable, so you delete some words and move on. (Actually, I just saw [a note](https://beekeeperlabs.com/crossfire/docs/index.html#FILL:~:text=\(Note%20that%20by%20selecting%20the%20%22Fill/Show%20eliminated%20candidates%22%20menu%20option%20you%20can%20disable%20the%20deletion%20of%20unsuccessful%20fills.%20Some%20constructors%20find%20this%20handy%20if%20they%20wish%20to%20try%20hand%2Dfilling%20with%20words%20that%20aren%27t%20in%20their%20dictionaries.%20Others%20merely%20find%20it%20distracting.\)) in the docs talking about this.) * So this feature relies on a good, complete word list. * You can filter the suggested words list. * Fill config options: * Minimum word score. * Longest shared substring. * Candidate quality ranking. * Speed/quality tradeoff. * Quick fill tool: * This is what CrossFire calls its autofill feature. It runs an autofill on the grid. * You can also run it on a subsection of the grid. This works even if the subsection "cuts off" a slot, such that the subsection contains only part of a slot---so for example, CrossFire can autofill the first 3 letters of a 5 letter slot. * [**Words** tab](https://beekeeperlabs.com/crossfire/docs/index.html#WORDTAB) (complete words that appear on the grid): * Gives *XScore*, which is a measure for how easy a word is to solve, taking into consideration the intersecting words. So a difficult word with many intersecting difficult words will have a very low XScore. * Shared substrings in words are highlighted. Click on a word to see shared substrings on the grid. * Easily change the spelling or score of a word. * Shared substrings are highlighted. * **Clues** tab: * Can show clues from third-party [clue database](https://tiwwdty.com/clue/) maintained by Matt Ginsberg. * Context menu on word lets you look up the word on the web (Google by default). * **Lookup** tab: * Search for words in word list, according to filters. * [Example query:](https://beekeeperlabs.com/crossfire/CrossFireTutorial004a.jpg) * Words that \[**start with**, end with, both\] substring `air`. * Words that are **lowercase**. * Words that are **10-12 or 15** letters long. * Words with minimum word score **0**. * Regex also works. * Grid: * When hovering your mouse over a cell, CrossFire shows the top 10 suggested ACROSS and DOWN words. * Light pink highlight = unches or two-letter slots. * Dark pink highlight = no word possible (given the existing letters) in this slot. * Green highlight = duplicate substring. * Brown ghost letter means it's the only possible letter for that cell. * Option to show the different possible letters inside a cell. * You can mark theme words to make them appear purple on the grid. They also do not disappear when you clear the grid. * **Best location** button moves your cursor to hardest-to-fill slot. * Word list (CrossFire calls it [*dictionary*](https://beekeeperlabs.com/crossfire/docs/index.html#MAINTENANCE)): * Can add words to word lists (without having to create a whole new word list). * Can change scores of words in word list. * Can make various edits to the word list with the app. ### Review I think this is one of the best editors. The biggest selling point for me is the fact that it uses the autofill algorithm to find suggested words. I'm not sure how useful the grid score / final score is. It might be very useful, but it would take much more testing to figure that one out. So for now, it's a question mark. Visually, it looks kind of outdated. But the UI is perfect otherwise. It's clean and feels great to use. ## [Crossword Compiler](https://www.crossword-compiler.com/) * Comes with grid pattern generator, which has a lot of options to customize. * There is a "guided" autofill tool. Essentially, you pick the word at each step. * Grid insight provides warnings for typical grid problems. * Puzzle statistics: * Contains common stats * **Accidental words** section warns you if you have any words from their blacklist. * Scrabble score. ### Review UI is clean, but feels a little difficult to use. Controls are a bit different from other editors. ## [Crosserville](https://www.crosserville.com/) * If you see a word score, you can easily modify it by clicking on it. This works anywhere in the app. * [**Puzzle stats**](https://www.crosserville.com/stats): see puzzle stats from various publishers. I think this is intended for people trying to get their crosswords published to see how their puzzle's stats compare to their desired publication. * [**Theme search**](https://www.crosserville.com/search/theme): search for published crosswords, by theme. Seems like it could be useful for inspiration. Probably not very legal though, since they're just rehosting all the puzzles. * [**Grid search**](https://www.crosserville.com/search/grid) lets you search for grids, with filters: * Specify how many 8, 9, ..., and 15 letter slots the grid has. * Specify the total number of words in the grid. * Specify symmetry type. * Specify number of 3 letter slots. * You can rotate and reflect the grids that the search returns. * [**Word lookup**](https://www.crosserville.com/builder?m=lookup): search for words and see useful stats about them, like number of occurrences in puzzles, frequency distribution by day of the week, clues for the word. * It looks like this and the puzzle stats both rely on their internal archive of puzzles from the WSJ, NYT, etc. * [**Grid builder**](https://www.crosserville.com/builder): This is the actual crossword editor. * **Info**: puzzle stats and info. * Grid size * Total words * Black squares count * Average word length * [Grid flow](https://www.crosserville.com/FAQ#:~:text=are%20grid%20scores%3F-,What%20is%20Grid%20Flow%3F,-What%20are%20stale) - a measure of how connected the slots in a grid are. (As in physically connected; this is about the grid itself and has nothing to do with the words.) * Word counts * **Words**: list of complete words on the grid. * Words that never appeared in the NYT are bolded. * **Fill**: autofill and word suggestions. * If your cursor is in an independent sub-region of the grid, then autofill algorithm limits itself to that subregion. This applies to both the grid autofill tool, as well as the word suggestions generator. So breaking a grid up is a great way to speed up the autofill algorithm if it's too slow. [Video for more info](https://www.youtube.com/watch?v=qADZHK_rxO4&t=762s). * Autofill: * Can set minimum score and word length for autofill. * Can count number of possible fills. * Can goto next and previous solution. But this is usually just modifying one or two letters, with each "next," so I don't think it's very useful. It would be better if it generated a completely new fill, with a different seed in the current slot or something. * You can click on any autofilled word on the grid, and Crosserville shows you the most popular clue for that word, from its database. * You can also exclude that word from the word list, or grid, or fill. * Word suggestions: * You have to click a button for it to start generating suggestions. * Suggestions are ranked based on "grid score." The grid score is calculated like this: 1. For each word suggestion: 1. Add the suggestion into the grid. 2. Find the best possible fill for the area surrounding the suggestion. 3. Compute the cumulative score of all the words in that fill. The result is the grid score for the suggestion. 2. Normalize all the grid scores to 1, based on the highest grid score calculated so far. * Option to exclude word from dictionary or grid. * Option to highlight duplicate substrings. * Slot filter: create either a whitelist or blacklist for the current slot. These filters are preserved even if you move the cursor away, and you can show all slot filters. * Grid: * If a slot has 10 or less possible words, Crosserville highlights it yellow. * If a slot has a single possible word, Crosserville adds ghost letters corresponding to that word. * If a slot has no possible words, Crosserville highlights it red. * **Accept Forced Letters** button adds in all ghost letters (forced letters). ### Review The actual editor has a lot of features, but the UI isn't very good. The tools that are based on their NYT, etc. crosswords archive do seem useful. ## [PuzzleMe](https://puzzleme.amuselabs.com/pmm/puzzle-create) * AI-powered crossword creation options: * AI: * ==**New:** Ok, so after thinking about this further, I think the simplest way to describe it is this: it's like the feature that some editor programs have, where you input a word list, and it generates a grid using those words---except this tool uses AI to handle the word list generation part, as well as the clues generation part. So there's no effort required on the human's part, unless they want to improve the clues.== * Grid is asymmetrical. * Clues are very straightforward and boring. Though you can always change them. * The one use case I can think of for this is in education. Like if a teacher is doing a lesson on World War 1, then they can use this tool to quickly generate a World War 1 themed crossword puzzle, where the words are things that the students are expected to know. * ==**New:** Actually, I see that the CrossFire FAQ describes this style as a ["School (word list) crossword"](https://beekeeperlabs.com/crossfire/faq.html#h.jcey7bv31946:~:text=supported%20in%20CrossFire.-,School%20(word%20list)%20crosswords%3F,are%20far%20better%20off%20using%20one%20of%20them%20rather%20than%20CrossFire.,-Buying%20CrossFire) (though it doesn't appear to be a standardized term). Now that I think of it, I definitely remember getting these crosswords in school. So this is certainly the main use case of the word-list-crossword-generator tool that many editors have.== * [Example with the prompt, *Linux*.](https://puzzleme.amuselabs.com/pmm/crossword?id=022fea7f&set=007371bb701e26da876928959b282ebca45e38192ae67c9125b0c343e1a5b5b1) (Use **Assist > Reveal grid**.) * Magic fill: * This also uses AI, but it works differently from the standard *AI* option described above. * It's designed for dense and small grids. * You give it some required words (they recommend 2 or less), and a min and max number of black cells. * It tries to generate a grid with those constraints. * [Example with required words *PIANO* and *MUSIC*, and minimum 4 black cells.](https://puzzleme.amuselabs.com/pmm/crossword?id=1ab4a8a6&set=007371bb701e26da876928959b282ebca45e38192ae67c9125b0c343e1a5b5b1) (I'm pretty sure I specified minimum 4 black cells. I think it couldn't come up with that, so it only used 2.) * Non-AI crossword creation options: * List entries: * ==**New:** So this is basically the *AI* generation option described above, just without the AI.== * Enter a list of words. PuzzleMe generates a grid with those words. * Grid is asymmetrical. * [Example with random emotions.](https://puzzleme.amuselabs.com/pmm/crossword?id=18e1074c&set=007371bb701e26da876928959b282ebca45e38192ae67c9125b0c343e1a5b5b1) * Empty grid: * Standard manual crossword construction option. * Grid starts off with all black cells. Entering letters creates white cells. This is the opposite of what most crossword editors do. * Doesn't have traditional word suggestions list. It does appear to have an AI word suggestion tool. But I couldn't get it to work. * Transpose grid. * Add/delete row/column ### Review I found it really difficult and unintuitive to use. Which is surprising, because of how many publications use PuzzleMe's player software, for their crosswords. I think the PuzzleMe editor's greatest selling point is the AI crossword generation feature. I don't know of any other software that does that. But for manual construction, PuzzleMe is really bad. ## [Ingrid](https://ingrid.cx/) * Open source core. * Autofill: * Suggested words list for slots is heavily tied to the autofill algorithm. * Each suggested word is associated with an autofill. Selecting a word shows the autofill on the grid, as a preview. * If a word fits a slot but doesn't have a valid autofill, the word will be hidden ("unfillable"). * You can also autofill the grid all at once. * Can approve or reject a suggested word. * If a slot has an approved word, all autofills must use that approved word in that slot. If there are multiple approved words for a slot, all autofills must use one of the approved words. * If a slot has a rejected word, all autofills must not use that word in that slot. * Can set minimum word score for autofill. * Can set maximum duplicate substring length for autofill. * Can choose a subgrid to apply the autofill on. * Ingrid has heatmap for how constrained a cell is. * Uses red warning colour for unfillable cells, unches, and two-cell long slots. * When hovering your mouse over a cell, Ingrid shows the top 10 suggested ACROSS and DOWN words. * Shows ghost letters in cells if there's only one possible letter. * Can right click a word and search for the word on Google. * Can use regex to filter the suggested word list. * Ability to go to recommended slot. (I think it's just most constrained slot.) * Flip grid option. * Ability to quickly add a custom word to the word list. (Personal word list.) ### Review ==**New:** Actually, CrossFire uses their autofill algorithm to generate the word suggestions too. Ingrid and CrossFire feel really similar. CrossFire doesn't have a heat map though. But the two editors are among the best, I think.== Pretty good UI. Feels high quality. The high degree of coupling between the word suggestions and the autofill algorithm is interesting. I don't think any other software does it like this. I'm not sure if it's good or bad or how well it even works. Surely, it's not testing every possible word combination. So then how does it know that it can exclude certain words that fit the slot but lead to an unfillable grid? Maybe it's only checking to see if the intersecting slots can be filled? I'm not sure. There's also a good chance that I'm totally misunderstanding how it works. ## [Crosshare](https://crosshare.org/) * Jump to most constrained. * Use stock clues for words. ### Review It's okay. But definitely rough around the edges. ## [Crossword Weaver](https://www.crosswordweaver.com/index.html) * Option to add word bank of solutions. Useful for crosswords designed for children. ### Review Very, very old. Designed for teachers to make crosswords for their students. ## [Crossworthy](https://www.crossworthy.net/) * Highlights unches and two-letter slots in red. * Highlights unfillable cells in yellow. * Autofiller lets you select a word for the current slot and autofills the rest. ### Review Solid editor. Clean UI. ## [Crossword Studio](https://www.crosswordstudio.app/) * This software is Mac only, so I wasn't able to try it. These notes are based on their [docs](https://crosswordstudio.app/help/). * Create a crossword automatically by giving it a list of words. It creates an asymmetrical grid. * Option to expand and trim grid. * Word suggestions list takes a filter that accepts a `?` wildcard. ### Review Simple crossword editor. ## [Phil](https://www.keiranking.com/apps/phil/) * Generate random grid pattern. (I'm not sure if it's just cycling through pre-made grids.) ### Review Not bad, but not great. ## [Crosswyrd](https://crosswyrd.app/) * Heat map: * Shows how constrained a cell is with shades of blue. * Button to jump to next most constrained slot. * Word bank: * Add words to the word bank to see how they fit into the grid. * The word bank shows you how many different places on the board a word fits. * Hover over a word to see all the possible spots highlighted. * Click on a word and then click on the grid to place it. * Note: This seems like a nice QoL feature, but not something that helps you make better puzzles. ### Review UI on this is really nice. Looks and feels very polished. ## [CrossHatch](https://ben4808.github.io/) * As you fill in cells, the remaining cells darken in shade, as they become more and more constrained. If there are no valid options for them, they turn red. * Autofill: * You can choose a subsection of the grid to run the autofill for. * Gives you a list of autofills it generated, to choose from. ### Review UI is ugly. Doesn't feel great to use. Also need to manually upload word list.