This project attempts to enhance the compactness of crossword puzzle arrangements in which each row and column needs to be a valid dictionary word, using a combination of machine learning and heuristic methods. I utilize the back-jumping algorithm to create a tree of possible words generated by a helper function. After obtaining a valid solution state, I query an LLM to generate clues for each row/column. When a solution state and its respective clues are entered as an input, I use the ELMo neural net to score the embeddings of each word to measure semantic similarity thereby eliminating unrelated words passed through the filter.
Introduction
Introduction
From global newspapers to local publications, crossword puzzles have long been a staple of printed entertainment. These problems challenge solvers to decode clues and fill in grids with words that fit both the given hints and the overlapping letters. This project dives into the intricate process of optimizing crossword grid creation using advanced computational tools. By leveraging a variation of the well-known backtracking algorithm, the aim is to automate the construction of crossword grids that not only meet linguistic standards but also provide an engaging solving experience.
First, the user selects a word and generates a solution grid with the first row equal to their input. Then, they can use a large language model to create clues for each word in their custom puzzle. Finally, they can re-solve their puzzle using the same algorithm that generated the original solution state. However, instead of relying on brute force as with the initial solution, they can employ machine learning and the ELMo neural network to select only those words that are similar to a clue, based on a specified threshold.
First, the user selects a word and generates a solution grid with the first row equal to their input. Then, they can use a large language model to create clues for each word in their custom puzzle. Finally, they can re-solve their puzzle using the same algorithm that generated the original solution state. However, instead of relying on brute force as with the initial solution, they can employ machine learning and the ELMo neural network to select only those words that are similar to a clue, based on a specified threshold.
Generating Solution Grid
Generating Solution Grid
Helper Functions
Helper Functions
We begin by defining several helper functions essential for our grid construction algorithm. Each one is used to regulate and control the state during operation. To make them work given various grid sizes as an input, they utilize the in-built Dimensions function to determine the proper bounds when using table and other iterative processes.
Sets the row equal to the inputted word by iterating over the list and indexing into each slot and enter the respective character:
In[]:=
SetAttributes[setRow,HoldAll]setRow[rowIndex_Integer,word_String/;StringLength[word]>=Dimensions[grid][[2]],g_]:=Module[{newGrid}, newGrid=g; Table[newGrid[[rowIndex,n]]=Characters[word][[n]],{n,1,Dimensions[g][[2]]}]; newGrid]
Finds the indexes of valid rows and columns and used to check if a gridState is valid:
In[]:=
indexesOfValidRows[g_]:=Table[If[DictionaryWordQ[StringJoin[g[[i]]]],i],{i,Dimensions[g][[1]]}];indexesOfValidCols[g_]:=Table[If[DictionaryWordQ[StringJoin[g[[All,i]]]],i],{i,Dimensions[g][[2]]}];
Takes word length as an input and gets all words of that length:
In[]:=
getWords[length_]:=Select[DeleteDuplicates[ToLowerCase/@Select[WordList["KnownWords"],StringLength[#]==length&&DictionaryWordQ[#]&]],Not@StringMatchQ[#,NumberString]&&Not@StringContainsQ[#,"-"]&&Not@StringContainsQ[#,DigitCharacter~~("st"|"nd"|"rd"|"th")~~EndOfString]&];
Checks if all columns have the potential to be a valid word:
In[]:=
areColsValid[g_]:=Module[{words=getWords[Dimensions[g][[1]]]},AllTrue[Table[AnyTrue[words,StringMatchQ[#,StringJoin[g[[All,i]]]<>"*"]&],{i,Dimensions[g][[2]]}],TrueQ]];
Determines if a grid state is valid:
In[]:=
isValidGridState[gridState_]:=Length[DeleteCases[indexesOfValidRows[gridState],Null]]==Dimensions[gridState][[1]]&&Length[DeleteCases[indexesOfValidCols[gridState],Null]]==Dimensions[gridState][[2]]&&isGridFull[gridState]
Goes from top to bottom and attempts to find an empty row:
In[]:=
findNextFreeRowIndex[grid_]:=DeleteCases[Table[If[Count[grid[[i]],""]==Dimensions[grid][[2]],i],{i,Dimensions[grid][[1]]}],Null][[1]]
Checks if the grid is completely filled:
In[]:=
isGridFull[grid_]:=AllTrue[Table[!ContainsAny[row,{""}],{row,grid}],TrueQ]
Instantiating global variables
Instantiating global variables
Set the dimensions of the grid and define it:
In[]:=
numRows=7;numCols=7;grid=ConstantArray["",{numRows,numCols}];
Initialize back-jumping state trackers:
In[]:=
prevNodes={};badWords={};done=False;depthList={};
Generate word list once instead of during each step of recursion:
In[]:=
wordList=getWords[numCols];
Set starting word:
In[]:=
grid=setRow[1,Evaluate[InputString["Enter a "<>ToString[numCols]<>" letter word (DO NOT USE SPECIAL CHARACTERS AND LENGTH NEEDS TO BE EXACT): "]],grid];
Given a solved grid, the LLM generates clues for each row which are used in the filtering process:
In[]:=
solvedGrid={{"p","o","p"},{"o","w","l"},{"p","l","y"}};cluesForRows=generateCluesForRows[solvedGrid];rowCluesSimilarWords=generateMostSimiliarWordsFromCluesUsingGroq[cluesForRows];
Back-jumping
Back-jumping
Like any recursive function, this one starts by checking the two base cases: is the grid valid, and is the grid full. If the first condition triggers, the function breaks out of the module and prints the result. Should the other condition be true, the function will jump back to the top of the tree and prevent itself from returning down the path by banning the word (putting it in the badWords list). After checking the base cases, it iterates over a filtered list of words that have the potential to satisfy the column constraint. Then, it checks grid validity, and whether the algorithm has explored this branch of the tree before. If it has not, it runs the function on the updated grid state. In the case that the branch is bad, meaning that no solutions can be found for the given grid, the algorithm returns to the previous decision point.
backjumping[gridState_, currDepth_ : 0, clueGiven_ : False, indexToRunOn_ : 2] := Module[{grids}, $RecursionLimit = 16384; (*Increase of recursion done as preventative measure*) If[done, Return[Module]]; AppendTo[prevNodes, gridState]; AppendTo[depthList, currDepth]; Which[isValidGridState[gridState], Print[gridState]; done = True; Return[Module], isGridFull[gridState], AppendTo[badWords, StringJoin[gridState[[2]]]]; backjumping[DeleteDuplicates[prevNodes][[1]], 0]; Return[]]; grids = Table[setRow[Evaluate[findNextFreeRowIndex[gridState]], Evaluate[w], gridState], {w, getRelevantWords[gridState, clueGiven]}]; Table[Which[areColsValid[grids[[i]]] && ! MemberQ[badWords, StringJoin[grids[[i]][[indexToRunOn]]]], backjumping[grids[[i]], currDepth + 1], Dimensions[gridState][[2]] >= 2 && i == Length[grids], ( AppendTo[badWords, StringJoin[grids[[i]][[indexToRunOn]]]]; backjumping[DeleteDuplicates[prevNodes][[1]], 0] )], {i, Length[grids]}]; ];
Filtering the words
Filtering the words
This function takes a grid state as an input and runs a filter on all words of n length. It looks at each column and generates a list of valid words that start with the column’s already-defined letters. For each word, it then takes the character at the next open row’s index and finds the words with any of those characters at the column’s index.
In[]:=
getRelevantWords[gridState_,clueGiven_:False]:=Module[{firstColumnWords,validWords,validChars,transposeResults,columnWords,firstEmptyRow,colWordList,rowWordList,wordFromClue,letterSortedWords,charsByRow},colWordList=getWords[Dimensions[gridState][[1]]];rowWordList=getWords[Dimensions[gridState][[2]]];firstEmptyRow=findNextFreeRowIndex[gridState];transposeResults=Transpose[DeleteCases[gridState,{___,""..}]];columnWords=Table[DeleteDuplicates[Flatten[DeleteCases[Select[colWordList,StringStartsQ[#,StringJoin[transposeResults[[i]]]]&],{}]]],{i,1,Dimensions[gridState][[2]]}];charsByRow=Table[DeleteDuplicates[Table[StringTake[word,{firstEmptyRow,firstEmptyRow}],{word,colWords}]],{colWords,columnWords}];validWords=Cases[rowWordList,s_String/;MemberQ[charsByRow[[1]],StringTake[s,1]]];Table[validWords=Cases[Evaluate[validWords],s_String/;MemberQ[charsByRow[[i]],StringTake[s,{i,i}]]];,{i,2,Dimensions[gridState][[2]]}];letterSortedWords=ReverseSortBy[validWords,StringTake[#,1]==gridState[[1]][[firstEmptyRow]]&];If[clueGiven&&Length[letterSortedWords]<=12,wordFromClue=rowCluesSimilarWords[[firstEmptyRow]];letterSortedWords=Keys[ReverseSortBy[Thread[letterSortedWords->Map[scoreWordBasedOnSimilarityToClue[#,wordFromClue]&,letterSortedWords]],Last]],letterSortedWords];letterSortedWords];
Run on parallel
Run on parallel
Due to the algorithm’s brute force nature, evaluating the tree of possibilities to search for a solution on a single kernel takes far too long even with the heuristics it utilizes. By using ParallelMap, the efficiency is greatly increased as each branch is evaluated on a separate kernel, with a total of eight being used.
Provide each kernel with its own, local copy of the done variable:
In[]:=
DistributeDefinitions[done];
Provide universal access to state variables so dead ends reached on kernel A are visible to all other kernels:
In[]:=
SetSharedVariable[prevNodes,badWords,depthList];
Obtain list of all possible options for the second row of the grid:
In[]:=
secondRowOptions=getRelevantWords[grid,False];
Evaluate the algorithm on all possible words (NOTE: this code takes a very long time to run):
In[]:=
ParallelMap[backjumping[setRow[1,Evaluate[#],grid],0,False,1]&,wordList]
Run on grid with select starting word:
In[]:=
ParallelMap[backjumping[setRow[2,Evaluate[#],grid]]&,secondRowOptions]
Out[]=
{}
Clue Generation
Clue Generation
Introducing the LLM
Introducing the LLM
For clue generation, we use a large language model and provide it with a carefully engineered prompt.
Interacting with the Groq API
Interacting with the Groq API
Groq is a free version of ChatGPT and uses a similar LLM. Because they are a startup and looking to attract potential customers, they provide access their API for free. An API is a cloud-based external data source that can be queried from a local environment. It sends the response back as a JSON or HTML. Each function below starts by defining the API key, the endpoint, and the headers for the request. Then, it creates the message and sets the model. Finally, it parses the response and returns the result. If you would like to download this notebook, will need to generate your own API key.
Generates an HTTP request to the Groq API and uses an custom prompt to get the clue for an inputted word:
Generates clues for all the rows:
Generates clues for all the columns:
Re-solving the Puzzle
Re-solving the Puzzle
To decode the clues, we used an LLM to reverse the generation process. In doing so, we get a word that is similar to the original clue. After obtaining the results from the API, we input them into the word filtering function defined in the back-jumping section to sort the words based on their cosine similarity.
Takes a list of clues as input and returns the words that the LLM associates with them:
Neural Net
Neural Net
After some experimentation with various models, the ELMo returned the best results in determining semantic similarity between the LLM’s attempt to solve a clue and words in the filtered list.
Import net model from Wolfram Neural Net Repository:
Similarity Scoring
Similarity Scoring
Creates embeddings for a two words (the word and the clue to check it against) and scores them based on their similarity:
Execution Analysis
Execution Analysis
Analyzing the Filter
Analyzing the Filter
Originally, we wanted to understand the effectiveness of the filtering function. To do this, we gathered data on all words in the Wolfram Language dictionary and figured out how many words our function filtered out.
Get the length of all 2-6 letters words:
Retrieve data for each grid solve:
Generate average filter percentage for each word length:
Analyzing Speed on Single Kernel Operation
Analyzing Speed on Single Kernel Operation
We start by gathering data for various words and saving the information in a list of rules. Each item in the list is in the format of the starting word for the grid, which is mapped to the time it took to run.
Initialize and populate arrays with data:
Explaining the Data
Explaining the Data
According to the average crossword generation runtimes bar chart, the algorithm’s durations follow a bimodal distribution (inverse bell curve). This result may appear surprising given we’d expect that a 2x2 would solve quicker than a 4x4, as it has less characters and spaces to fill. But the expense of running the word filtering algorithm is higher when evaluating the two and three letter words than it is when solving for the four letter words. This is supported by the fact that the percentage of words filtered per length chart suggests that the 4x4 filter is almost 50% more effective than the 2x2. As the grid grows, though, the filter becomes more effective thereby justifying its time cost.
Analyzing Depth on Multi-Kernel Operation
Analyzing Depth on Multi-Kernel Operation
What does this mean?
What does this mean?
Each possible branch that is created by the back-jumping algorithm is run on its own kernel.
Instantiate Variables to Track Depth
Instantiate Variables to Track Depth
To generate each list, I ran the algorithm on each grid and copied the results from depthList into each of these variables.
Format the data to prepare for plotting:
Generate function for prediction purposes:
Actual visualization of data:
Overlay actual data with prediction function:
Illustrate recursion depth for each word:
In[]:=
GraphicsRow[(Labeled[ListLinePlot[First[#1], AxesLabel -> {"Step in algorithm", "Recursive depth"}, ImageSize -> Full], Last[#1], Bottom] & ) /@
{popRecursionDepth -> "Word: pop", opalRecursionDepth -> "Word: opal", casedRecursionDepth -> "Word: cased", sisterRecursionDepth -> "Word: sister"},
ImageSize -> 1250]
{popRecursionDepth -> "Word: pop", opalRecursionDepth -> "Word: opal", casedRecursionDepth -> "Word: cased", sisterRecursionDepth -> "Word: sister"},
ImageSize -> 1250]
What Do these Graphs Represent?
What Do these Graphs Represent?
The plots above illustrate the recursive depth of each step the algorithm took to find a solution. Recursive depth refers to the number of times the function called itself within its own execution. Each new call adds a layer to the stack, and recursive depth is a measure of how deep these calls go.
Visualizing Results
Visualizing Results
This function is used to analyze a solve grid alongside the clues for it.
Create UI for user to view clues for each row and column:
Observations
Observations
Define solved grids:
Generate clues for each grid:
Below is a visualization tool to show a solution grid with its clues. If the user click on a letter in any given row, it will give you the respective clue. Should they click it again, it will show the intersecting column’s clue.
Proving the Largest NxN Grid
Proving the Largest NxN Grid
To find the max value of n, the number of words n-letters long must be ≥ the nth dimension of the grid.
Gather string length data:
Given the data presented above, the largest possible grid is a 20x20, as there are only nineteen 21-letter words. However, after running the algorithm on 20x20 it was clear that no solution existed. This pattern persisted until the 13x13 grid. Due to the sheer number of words at this point, though, the algorithm was not able to determine if a valid solution for a 12x12 grid existed.
Conclusion
Conclusion
At the beginning of the project, we struggled to get the algorithm to return to its previous decision point. We tried tracking the depth and then returning one level up from our current position, but in doing so, it kept jumping down the same path. To rectify this issue, we attempted to return to the starting node each time which seemed to solve the issue on smaller grids; however, as the dimensions grew, situations arose in which the algorithm returned to the same branch it had just jumped away from. We realized we could solve this problem by implementing a list, which would hold the beginning words of bad branches and checking that the current grid state is not in that list before back-jumping. Overall, this adjustment saved a lot of time. Although the algorithm is far from perfect, this project provided interesting insights into the generation of crossword grids. For starters, we learned about the importance of heuristics. Without the filtering function, the 6x6 grid would have to analyze more than 7,100 extra branches. We also observed that the filtering function significantly reduced overall memory usage, allowing the algorithm to run more efficiently.
Possible Applications and Surprising Insights
Possible Applications and Surprising Insights
Throughout this project, we were consistently surprised by how much of an impact a small optimization made. After removing one of the redundant column checkers, the algorithm ran approximately 10% faster.
A potential application for this project is in the development of more advanced crossword puzzles. By refining the currently implemented heuristics and incorporating a more effective pruning process, it may be possible create extremely large puzzles. Additionally, the algorithm we used may potentially be applicable to other types of combinatorial problems, such as Sudoku or word searches.
A potential application for this project is in the development of more advanced crossword puzzles. By refining the currently implemented heuristics and incorporating a more effective pruning process, it may be possible create extremely large puzzles. Additionally, the algorithm we used may potentially be applicable to other types of combinatorial problems, such as Sudoku or word searches.
Future Improvements
Future Improvements
In the future, there are quite a few improvements that I would like to make:
◼
Allow for words to extend off of the side of the grid
◼
Incorporate byte tries into the filtering function
◼
Implement an pruning algorithm such as Alpha-Beta to eliminate bad branches earlier on
Acknowledgements
Acknowledgements
I want to thank my mentor CJ and the rest of my mentor group for their support as well as Nicolo for his help with my algorithm.
References
References
◼
Ginsberg, M. L., Frank, M., Halpin, M. P., & Torrance, M. C. (n.d.). Search Lessons Learned for Crossword Puzzles. In Computer Science Department, Stanford University.
◼
Steinhal, R . (n . d .) . Crossword Puzzles as Constraint Satisfaction Problems . cs . columbia . edu . Retrieved July 6, 2024, from https : // www . cs . columbia . edu/%7 Eevs/ais/finalprojs/steinthal/
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Optimize crossword layout grids for density
by Ezra Akresh
Wolfram Community, STAFF PICKS, July 11, 2024
https://community.wolfram.com/groups/-/m/t/3214394
by Ezra Akresh
Wolfram Community, STAFF PICKS, July 11, 2024
https://community.wolfram.com/groups/-/m/t/3214394