{'fraction_non_alphanumeric': 0.025716787043116657, 'fraction_numerical': 0.009958415408185598, 'mean_word_length': 4.474464579901153, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Automation Strategies for Unconstrained Crossword Puzzle Generation

An unconstrained crossword puzzle is a generalization of the constrained crossword problem. In this problem, only the word vocabulary, and optionally the grid dimensions are known. Hence, it not only requires the algorithm to determine the word locations, but it also needs to come up with the grid geometry. This paper discusses algorithmic strategies for automatic crossword puzzle generation in such an unconstrained setting. The strategies proposed cover the tasks of selection of words from a given vocabulary, selection of grid sizes, grid resizing and adjustments, metrics for word fitting, back-tracking techniques, and also clue generation. The strategies have been formulated based on a study of the effect of word sequence permutation order on grid fitting. An end-to-end algorithm that combines these strategies is presented, and its performance is analyzed. The techniques have been found to be successful in quickly producing well-packed puzzles of even large sizes. Finally, a few example puzzles generated by our algorithm are also provided.


Introduction
Since their introduction in 1913 by Wynne [23], crossword puzzles have maintained their popularity, and are a major linguistic game, as they are available in many languages. The puzzle consists of a grid of black and white squares. The objective of the puzzle is to fill the white squares with letters forming words or phrases, that are separated by black squares, by solving clues.
Crossword puzzle presents two basic problems: (1) crossword generation, (2) crossword solving. Several effective solutions have been developed for crossword solving [7,11,19,27] where given a crossword grid and a set of clues, the task is to generate the solution to the puzzle. Crossword construction is a difficult and complex art, and the puzzles are mainly constructed by human experts called crossword constructors. As noted by Steinberg and Last [29], crossword construction typically starts with experts selecting a few theme words and designing the grid. Next, softwares such as Crossword Compiler [5], Crossfire [3] or Phil [16] are frequently used to speed up the task by filling up the rest of the grid with words from a database.
The problem of crossword puzzle construction involves two main steps: (1) selecting a set of words and clues, (2) given a set of words, fitting the words in a grid while respecting the constraints of the crossword. The first problem has been the focus of various studies, where efforts have been made to generate cohesive and thematic grids by using NLP based techniques [26] or using lexical relations encoded in databases [1]. The problem of grid filling has been posed as a constraint satisfaction problem [2] and also as a heuristic-based search problem [12]. Since crossword construction has been shown to be an NP-complete problem [10], there is a need for effective heuristics/strategies to prune the search space. A few domain-independent crossword generation heuristics such as the cheapest-first heuristic, connectivity, and Smiths adjacency restrictions have been discussed in the report on lessons learned by M. L. Ginsberg et al. [12].

Approaches to the UCPG problem
There is little work in the area of automation of UCPG that we are aware of. An algorithm that uses recursion with backtracking has been discussed by Harris [13]. However, their puzzle size and input vocabulary size was small. An automated generation of a variant of the unconstrained crossword puzzle called Crozzle, has been formulated in terms of basic blocks by Harris et al. [14]. A basic block is a geometric combination of words into a block, such that the removal of any word from the vocabulary corresponding to the grid produces an invalid crossword. Construction of basic blocks has been proposed as part of the strategies for automated solution of unconstrained crosswords. It must be noted that though a basic block is a valid crossword, not all unconstrained solutions are basic blocks.
Another variant of the UCPG problem, called finding the diagram of diagramless crossword puzzles has been considered by Pershits and Stansifer [25]. They note that since the UCPG problem is "hopelessly intractable" to solve even for average-sized puzzles, they create a "manageable" variant, in which, the words across and down, the size of the puzzle, and the order in which the answers appear in the grid are taken as input from which the puzzle is constructed. While the results show that the approach proposed is practical in finding the puzzle diagram, it does not solve the UCPG problem which needs to generate puzzles directly from hand-picked words.

Our contribution
As observed by crossword constructors [8,18], even today, human constructors are seen doing better than automated constructors, which keeps the problem open. The aim of our work is to introduce a set of new techniques to automate the process of crossword puzzle generation from a selected set of words keeping the grid geometry open to accomodate "good" choices that are already picked up in the selected set. We come up with general-purpose strategies that help in improving grid placements to generate good quality grids. Once the grid is generated, the work of refining and twisting the clues can be done by the human crossword constructor. We show that several algorithmic strategies can be combined to achieve a significant improvement in generation, and in a much fewer iterations.
Summarily, in this paper, we propose a set of techniques for automatic solutions to the UCPG problem. A combination of strategies developed in this paper has been demonstrated to be successful in generating well-packed, unconstrained crossword puzzles, and our solution is also scalable w.r.t. the count of words that need to be fitted, wherein we observe a linear increase in computation. We also automate the process of clue generation, leading to end-to-end automation with a reduced intervention of human experts. We demonstrate the utility of the strategies devised through several examples and empirical analysis.
The paper is organized as follows. In the next section, we begin with an example puzzle generated by our approach. Next, in Section 3, we discuss the strategic functions used for the automated puzzle generation, which are referred to in the rest of the paper. Section 4 outlines the end-to-end algorithm which combines the strategies. In Section 5, we outline the main strategies. We describe them subsequently in detail and also talk about the effect of word sequence permutation order on grid fitting in Sections 6 -10. Finally, in Section 11 we discuss the overall performance of the strategies, and also add a few crossword examples of various sizes that were generated from the algorithm.

An Example Puzzle Generation
Crossword puzzle generation involves several optimizations including word selection, grid generation, alignment, movements, and fitting the boundaries. We formulate various strategies for automating these tasks. In addition, we also generate the clues automatically through a clue generation strategy.
Consider for example the puzzle given in Fig 1. It uses 13 words all in all, out of which 6 are aligned horizontally and 7 are aligned vertically in a 13 x 13 grid. This puzzle, including its clues, has been generated by our algorithm using the strategies developed in this paper. The solution for this puzzle is given in the appendix.

Strategic Functions
In this section, basic strategic functions that we use throughout the paper as part of the proposed strategies are described.
G: Grid of words L: Sorted list of words ranked with some ranking strategy. The list does not have duplicates.
1. Obtain the next fitting word pickWord (G, L): Returns w, the first word in L, of which, the letters intersect with one or more words contained in G. First word in the list is a "good" pick if L is sorted on ranks by a ranking function suitable for grid fitting. If the list is unranked, the best ranked word needs to be returned by applying ranking at the time of the next pick.

Insert at intersection
place (w, G): selects an orientation and places w in G, provided that placeable(w, G) is true, which makes sure that the new word w stays connected to at least one word in G. The new grid after this placement is returned. For example, place (red, [two (horizontal at 1,1 in grid), three (vertical at 1,1 in grid)]) places red at 3, 1 horizontally in G and returns the modified grid 4. Greedy removal strategy victim (G, L): returns a word u from G such that placeable(w, G \u) is true for some w in L. If no such word exists, it returns null. Essentially, this function returns a word that can be deleted from the grid, and due to which, one or more words from L can be accommodated in G. This function is used when there is no placeable word from the list for a given grid arrangement. The function then finds a victim word in the grid which if removed, allows the grid to accommodate at least one other word from the remaining list. This is used as a backtracking strategy, which may make it possible to grow the grid again after a word deletion. returns new grid [four (horizontal at 1,1 in grid)], and new list [one, two, three, five] assuming that five was the last word added to G. This is another backtracking strategic function besides victim(). While victim() is a more intelligent backtracking strategy, it may not always be able to find a victim satisfying our condition. To handle such cases, the LIFO wraparound strategy can be used repetitively till progress can be made.

Algorithm CrosswordGenerator
The algorithm moves through the following stages: 1. Seed and Initialization: The algorithm begins with picking a set of seed words (S) that are to be fit in the grid. The grid size is initialized to dimension N X N such that N is the length of the largest word in the list, since we need at least a grid that is at least large enough to fit each word in the list. The grid that starts eventually changes and adjusts its dimensions as more words get placed one by one. Thus, the initial grid dimension is a function of the seed words.
2. Ranking: It generates a distance matrix for a given word list, by computing the distance of every word with every other word in the list, and then uses it to rank words based on the number of intersections that they have with other words. Once the seed words are ranked and the list is sorted according to the ranks in ascending order, we begin with placement. We discuss the effect of ascending-first and descending-first choices later in Section 6 when we discuss the behavior of the distance used in ranking.

Placement:
The placement begins with placing the first word at the center of the grid. Then, we repeatedly call pickWord (G, L) to find the next word which can be placed. If a word can be placed in the grid, we place it using place (w, G). If no such word exists, we invoke strategic function victim (G, L) to remove a word from the grid which allows the addition of more words. If no victim can be found, then we call strategic function wraparound (G, L) to remove the most recently added word. The process is repeated until no more words can be added to the grid.
Algorithm 1: Algorithm to automatically generate a crossword. Data: S: List of words G: Grid N: Grid size (N X N grid) R: The Rank vector for words which stores the ranks of words corresponding to order given in S. The words are ranked based on commonalities with other words L: sorted list of ranked words, a temporary variable T: upper bound on the number of iterations for refinement i: Iteration count G best : best grid found so far in terms of count of the number of words inserted n best : no. of words in G best 1 Initialize: 2 vocabulary S to the list of seed words (about a couple of dozens) 3 Initialize N, the grid size as the size of the largest word in S 4 Initialize n best to 0 5 Initialize i, iteration count to 0 6 Initialize G to the empty grid. 7 Initialize n words to 0. 8 Initialize grid epoch GE M AX = 500. We reset a grid if it cannot be handled in GE M AX iterations. 9 Ranking: 10 Compute R, the rank vector assigning rank to every word 11 Find the distance of each word with every other word 12 Rank of a word is the sum of its distances 13 L ← sort S, based on ranks in R 14 Placement and Termination: 15    Given an input set of words, the order in which they are placed into the grid matters. We have found that certain sequences work much better than others. This subsection explores how the sequence ordering of words affects the performance of the grid. In this subsection, we do not use any backtracking or heuristic to improve the performance, but primarily bring out the problem, and then go on to describe strategies to improve the performance of grid creation. Plots in Fig. 2 show the number of words fitted for a randomly chosen set of permutations without backtracking as per the following brute force strategy: for every permutation of the word list: try placing words one by one till no word fits store the grid when no more word can be fitted From Fig. 2 (a)-(d), we can see that as we increase size of the set of permutations, the curve becomes a single bell curve showing normal distribution of permutations over no. of words that can be fitted without backtracking. From Fig 2e we can observe that approximately 80% of the permutations were stuck below 12 words, and 60% were stuck below 11 words, as compared to the best we found in this test (17 words). This indicates that a heuristic based on word selection can be useful to reorder the words through back tracking strategies to increase the capacity of the grid, and in fewer iterations avoiding brute force search through permutations. Next, we develop ranking strategies analyzing their impact on grid performance, starting with an intersection based ranking strategy.

Intersection based Ranking
Let us consider a list of seeds words, {WROTE, BREAD, LOBBY, HELLO}. Table 1 shows the intersection matrix (shown full) for the list. Each entry in the table represents the count of the number of letters common to the corresponding words. The last column shows the total number of intersections that each word has with other words in the entire list.
From this matrix, we can generate the ranking as a sequence (WROTE, HELLO, BREAD, LOBBY) with ties resolved arbitrarily. The selection of words during insertion into the grid is carried out in the order of the ranking. There can be other variants to rank the words, e.g., ranking based on the number of words intersected.

Effectiveness of Intersection based Ranking
To start with, Figures 3 and 4 show the effect of selection done on the basis of the number of intersections discussed above. Backtracking step is taken whenever no more words can be added using this ranking. For these figures, the grid size is kept constant. As the number of iterations increase, more and more words get added, till the grid is saturated. Backtracking changes the puzzle by swapping words. In this test, last in first out backtracking was adopted. In this particular example, we can observe that at about 50,000 iterations, the grid gets saturated. The figures also explore if there is any effect of ranking order on grid saturation. Figure 3 chooses words in ascending order of ranking, and Figure 4 chooses words in descending order of ranking. One can observe that the saturation point does not depend on the ranking order when the ranking is a function of the number of intersections. Thus we can conclude that in this case, the ranking function is not very effective since changing the order of ranking has not had much effect on the grid saturation point. We significantly improve this saturation point in the following subsection, which introduces a strategy based on a new ranking metric called pebble and sand metric.

Pebble and sand strategy for Ranking
A change in this ranking function improves the above result considerably. In the pebble and sand strategy, the following pebble and sand ranking function R is formulated. Here, instead of considering letter level intersection, word level intersections are used. As we shall see through our analysis, this choice significantly improves the performance. Given word w in word list l, R(w, l) = no. of words in l having intersection with w total no. of words in l Here, the ranking is independent of grid content and it represents a futuristic choice. At a given point of insertion, it can be noted that the content of the grid is already chosen as per their ranks. So, it makes sense to consider this option of ignoring the content of the grid while ranking words for the next choice, since the words were already chosen as per their ranks in the list.
We can observe through Fig. 5 and 6 that when the ranking is thus based on the number of words intersected and when the words are ordered in ascending order, the grid saturates at much fewer iterations. It saturates much faster at about 18000 iterations in ascending order and about 24000 iterations in descending order, as compared to about 50000 in the letters based intersection based strategy. Also, the saturation point is 17 words and 16 words for ascending and descending orders respectively.
The descending order does not beat the ascending order as shown in Fig. 6. This indicates that it is better to place the words that are apart from each other first. This strategy can be compared with strategy used for physically filling pebbles and sands in a jar. In our case, sand represents words that have more intersections with other words, and pebbles are words that have fewer. By following the ascending order the pebbles are filled first, whereas, the descending order fills the sand first limiting future choices considerably. So, filling pebbles first opens up more future choices allowing the grid to grow.
To see the effect of vocabulary size and average word rank on the pebble and sand strategy, we considered 100 randomly chosen vocabulary sets of varying sizes from size 1 to 100, with one dataset per vocabulary size. The grid size was constant. Fig. 7 shows the results. We observe that when the vocabulary size is small, the ranking order does not matter (circle points). However, when the vocabulary size increases, the pebble and sand strategy works better (triangle-up points) than descending order. The triangle-down points indicate where the descending order works better. Out of 100 data sets, 4 triangle-down points, 54 triangle-up points and 42 circle points were obtained. This establishes the effectiveness of ascending order, i.e. the pebble and sand strategy.

Towards Word Placement Strategies
Pebble and sand ranking metric rates a word in terms of what it shares with the rest of the words in the input vocabulary. Based on the pebble and sand idea, now we define a distance between a permutation and the best ranked (pebble and sand strategy order) permutation. This pebble and sand distance of a permutation is computed as follows: Given best ranked permutation P best and the worst ranked permutation is P worst (flipped order of P best ), the distance a permutation P is defined as: where pos(w, p) gives position of word w in permutation p, N is the no. of words in P , which is same as no. of words in P best .
For  Figure 8 shows the distribution of the pebble and sand distance over a total of 69,082 permutations. The dataset consists of 26 words and permutation sequences over those words have been randomly sampled from the possible 26! (4.03e26) possible permutations. It can be observed that the distance is normally distributed The combined effect is shown in the contour plot given in Fig. 9, which shows a hill like behavior. The peak in Figure 9 shows the distance at which the highest number of permutations occur, which is close to 0.6. The goal of our algorithm is not to achieve this peak, but to shift it, which is rather to shift the whole contour towards the upward area and make it steeper. This is so that no matter how far away a given permutation is from the best permutation, we can show that one can still have a good strategy that can quickly place a higher number of words in a given grid. The contours are revisited and the improvement is shown when we discuss the performance of our word placement strategies.

Word Placement Strategies
We now illustrate the strategies for placing words. To initialize, the chosen word is placed at the center. Next, from the list, we iteratively choose further words that have at least one intersection with words already in the grid. Fig. 10 given below shows the step by step process of building up the grid. We start with the best-ranked word, GRENADINE. Next, GLADIOLUS intersects with GRENADINE at A, and hence it can be placed top down. Next, the word EFFERVESCENCE gets placed across. In this manner, the grid gets built up piecewise till this process gets interuppted. We now discuss two placement strategies to handle a situation when no word from the input list can be added to the grid.

Last In First Out
In this strategy, we remove the most recently added words one by one till another word can be added to the grid. Removed words are pushed back into the input vocabulary list at the end. It can be observed that in the left image in Fig. 11, no more words can be added. Hence, we remove the last added word, POMEGRANATE from the grid. This strategy is helpful as it can avoid deadends through backtracking.  As shown in Figure 12, the LIFO strategy reaches ten words in about 25 iterations exploring all words in the wordset chosen (26 words in this case). In the graph, every downward edge shows a backtracking step using the LIFO strategy. Over 250 iterations, the graph shows that a maximum of 13 words were reached with this strategy. Each point in this graph is a valid crossword. We improve the result further through the greedy removal strategy explained below.

Greedy Removal Strategy
In this strategy, using the function victim (G, L) described in Section 3, we find a word, such that removing the word allows new words to be placed in the grid. For example, in the first image in Fig. 13, no new words can be added. Hence, we choose to remove the word MADRIGAL as a search over the input list finds the word JOCULAR that can fit in. The second figure shows the grid after removing the victim word. The third figure shows the grid with one new word JOCULAR added.
Post-processing for Disconnections: Note that this strategy can result in the grid being disconnected, and post processing may be needed to reconnect the components of the grid if disconnected words are not desired. This post-processing consists of connecting the disconnected components by finding connecting words through strategies such as pattern search used by Meehan and Gray [24]. In their approach, the grid layout is fixed and regex-based pattern matching is used to find words fitting in a fixed layout. Our set of strategies allow us to proceed with grid construction without fixing the layout. However, for post-processing, when the layout is more or less stabilized, the regex-based strategy can be used for connecting disconnected components. Fig. 14 shows the result of the greedy removal strategy that is implemented without using the LIFO word placement strategy explained in the section above. The saturation point is achieved much quicker, here, in less than 50 iterations. The saturation capacity is also higher than the one achieved with LIFO in the same number of iterations.
Preventing Cyclic Removals: We can also observe that greedy removal has eventually saturated in a cycle of two words causing cyclic removal and addition showing flicker around 12 and 11 words. In some 15 Figure 13: Illustration of victim Figure 14: Greedy Removal Strategy (Victim) saturated in a cycle cases, the cycle length in terms of no. of words may be bigger. In such cases, greedy removal finds a victim word from the grid for replacement, and in a cyclic removal, the same set of words get chosen. Suitable cycle prevention strategies may be used. If datasets are small, cycles are more probable, especially when many of the words in the dataset are already in the grid, leaving a much smaller set of words for replacement. Cyclic replacements can be handled by reducing priorities to words once backtracked, and bringing them back eventually if needed. Similar strategy is used in tabu search [17], in which, a finite list of most recent nodes (tabu words, in our case) is maintained. The tabu tenure count (tt) is defined as the size of the tabu list. Similarly, once a word has been deleted from the grid, it can only be added back after tt other moves are completed, meaning all other words have been given a chance. Fig. 15 shows the distribution of the permutations with the number of words fitted using the two word placement strategies presented above, but without using ranking and grid resizing. For the sake of comparison, the grid size is kept constant (same as the grid size considered in Fig 2e). As we can observe, about 90% of the permutations are able to fit 14 words within just double the number of iterations in brute force word placement. Fig. 15 represents the performance with our word placement backtracking strategies without using ranking. When the figure is compared with Fig. 2e, which represents the brute force placement without ranking or backtracking, we can observe that the distribution has now shifted significantly towards the right side, indicating that with our strategies, most of the permutations (over 90%) were able to fit 14 words. Also, this result was achieved within 50 iterations, which is double the number as compared to 26 iterations taken in Fig. 2e. The reader is reminded that the input data size in terms of no. of words is 26. Fig 16b shows the 3-d surface for the number of permutations fitted for a given number of words fitted vs. its pebble and sand distance, when our backtracking strategies were used. For comparison, similar surface is plotted for the above brute force strategy, which is shown in Fig. 16a. We can observe that with backtracking, the peak has not only become sharper, but it also gets shifted towards a higher number of words to be fitted. It may be noted that the contour plot in Fig. 9 and Fig. 16a are for the same data.

Grid resizing and reshaping
In this section, we discuss strategies for changing the high-level structure of the grid for a better placement. We start with a grid of the size of the largest word and try new placements. Next, we iteratively increase the size of the grid, towards achieving the desired utilization of the grid space. One way to define a desired utilization is to go for the size of the grid that allows maximum placement of words. Figure 17 shows the placement of a given set of words on different grid sizes. The smallest grid in the figure is of size 9 x 9, which allows 9 words to be fitted from the given vocabulary following the ranking order, and within some time limit. In the same conditions, the largest grid of size 13 x 13 allows 17 words to be placed.
Another strategy is to repack the grid. This allows redistributing the mass of the grid equally. For example, if one part of the grid is mostly sparse, while the other side of the grid is densely filled, we can rebalance the grid by removing an empty row (or column) from one side and adding the row (or column) to the other side. The left image in Fig. 18 shows the grid with the left side being sparse, and the right image shows the grid after the first column is removed from the left side and added to the right side. As we can see, one new word (CAVALRY) can be placed after this rebalancing.
Thus, the placements are heuristics-based in terms of our ranking, placement and grid resizing strategies, and a solution acceptable to human expert can be chosen as the algorithm continues to generate a sequence of solutions by applying the placement strategies. At any point of time the algorithm can be terminated and the best solution found till then can be accessed.

Clue Generation
For clue generation, we refer to an English dictionary to look up word definitions. The definitions and meanings of words can be used to generate the clues. For example, the dictionary definition [6] of ABYSMAL Figure 15: Effect of number of words fitted in a 13x13 grid based on the order of the words using backtracking strategies. The grid size is kept constant (13 x 13) and each permutation is used to fit the words over 50 iterations. is immeasurably low or wretched : extremely poor or bad. This is a simple and useful approach as word definitions do not contain the target word, nevertheless, conveying the meaning of the word. Once we have the clues, they can be manually altered. Similarly, word usages may also be used after removing the word and filling it with blanks. For example, for the same word, a clue [6] can be "They were living in . . . . . . . . . . ignorance.

Overall Performance
Further to the results on effectiveness of the strategies in their respective sections, in this section, we now discuss the overall performance of the algorithm, and provide empirical results and also a few example puzzles generated through our implementation of the algorithm. First the scalability of the algorithm w.r.t. the number of words to be fitted is demonstrated. Next, we discuss the quality of packing of the grids in terms of the share of the number of black squares. Finally, we provide a few example crossword puzzles generated using our algorithm.

Scalability of the algorithm
Combining the above strategies (ranking, victim words, LIFO backtracking, grid resizing) as per the algorithm outlined in Section 4, we obtain the results as shown in Fig 19. It shows the maximum, minimum, and the average number of iterations taken to fill the grid in the range 5 -50 words, where the vocabulary size is chosen to be 100. A back-tracking or a word fitting step is counted as a single iteration. As the grid size gets initialized to the size of the largest word in the vocabulary, we can see from the figure that fitting upto 15 words takes much fewer no. of iterations, since there are not many conflicts as the grid can accommodate those many words. The selection of words is based on order defined by the pebble and sand ranking strategy. Initial grids are sparse grids. However, as more words need to be fitted, more iterations are needed, and word placement backtracking strategies are put to use. As shown in the figure, with added iterations, the no. of words fitted increased following a near linear rise. The results are averaged over 100 datasets consisting of 100 words each, chosen randomly from the English dictionary. The grid has been reset on increasing the grid size after every round (epoch) of 500 iterations. When the grid resizing (expansion) step takes place, the grid is first reset to initialization. For example, if 6000 iterations are taken, then the grid undergoes a dozen resets, and it is also expanded that many times by one column and one row each time. This is an iterative refinement strategy. The refinement can be terminated when a desired result is obtained as discussed earlier.
Grid continuation is another possibility to explore when a grid expansion takes place. However, grid continuation was not found to be improving results. In fact, the results with the iterative refinement by grid reset on expansion were a bit better in the average sense as shown by the green line in Fig. 19, when compared to Fig. 20, which shows the results with grid continuation on expansion. Also, the band between the max and the mean is smaller for grid continuation as compared to grid reset. This behavior indicates that grid reset brings more freedom right from the beginning as compared to grid continuation, which ties the grid to an already chosen grid that is settled for a smaller size. Figures 21a and 21b show the utilization of the grid w.r.t. the number of words fitted with and without using the grid reset strategy. As we can observe, for a need of a smaller number of words, the utilization is low, since the grid size is initially set to the largest word in the vocabulary, due to which, the grid was left sparse. However, as we increase the number of words that we want to be fitted in, the grid utilization, on an average, rises to around 45% -55% leaving black squares to occupy 55% -45% of the grid. The utilization is a little higher in the grid resetting strategy as compared to grid continuation, since every time a grid expansion takes place, the grid is started afresh using the iterative refinement technique opening up more options. The utilization results are comparable to those reported in [13], which achieved 43.75% of black squares with grid sizes 8 X 8 with a small vocabulary size. We achieved with the new techniques comparable numbers with much larger grids and on much larger input vocabularies in a limited number of iterations. Figures 22a and 22b show the utilization of the grid w.r.t. grid size for the same data. As we can observe,   the best utilization is achieved in the range 24 x 24 to 28 x 28. Again, we find that grid resetting strategy results in better grids. The no. of iterations taken before freezing a puzzle ranged from 5 to 8000, depending on the number of words that were required to be fitted. A rise at the end of the graphs is observed for higher grid sizes, since the maximum number of iterations was kept limited.  Figure 26 gives a complete crossword puzzle with clues which was automatically generated using our algorithm. The clues were generated using definitions in the Python-based TextBlob library [21] and usages in the WordNet lexical database [9] supported in Python-based NLTK library [20]. The solution to the puzzle in Figure 26 can be found in the appendix.

Conclusion
We developed and demonstrated a new algorithm for end-to-end unconstrained crossword puzzle generation as a combination of several strategies. The algorithm works on a given set of words and dynamically constructs a grid from it by expanding and adjusting it as and when needed. It combines several strategies covering word selection, word placement, grid design. It also includes clue generation stage using a resource such as a dictionary. An important advantage of our algorithm is that it can work with a considerably small set of vocabulary, and our experiments show that the algorithm is able to fit a significant subset of the words from a small set in a well-packed grid. This was revealed through empirical analysis over 100 data sets of size 100 words each. In each data set, words were randomly selected from a dictionary. In all cases, we were able to generate puzzles of sizes up to 50 words iterating under 7000 to 8000 iterations. The algorithm therefore can be used in applications where words need to be handpicked, such as in thematic puzzles. We explored the effect of reordering of vocabulary word sequences and found that certain sequences work better than others. To reach closer to better performing sequences, we developed (i) a ranking metric for efficient selection of words and (ii) a couple of backtracking strategies. The pebble and sand strategy has been found to perform well in most cases. It significantly brings down the grid saturation point in terms of the number of iterations, at the same time increasing the number of words fitted. A combination of LIFO and greedy removal strategies makes the word placement less sensitive to the ordering, and as observed in the empirical results, it significantly increases the number of words fitted within much fewer iterations. We have shown that our algorithm also works well with a large number of words, with only a linear rise in the number of iterations. Further, we have observed that it is better to reset a grid when doing grid expansion than to continue with the same grid, as the same grid constrains the new search space. The clue generation strategy provides a basic clue set for the crossword, which can be altered manually to make them more interesting.
These strategies are tunable, and hence they can be modified and adapted for use in other word games. Future work areas include ranking functions, victim selection, grid packing strategies, and explorations into properties of vocabularies in terms of their abilities to generate better quality puzzles. 28