Java games crossword making

NOTE: if the grid and the database of words are constant the previous steps can just be done once. First step of the algorithm is select an empty wordslot grid word at random and fill it with a candidate word from its associated wordlist randomization enables to produce different solutons in consecutive executions of the algorithm complexity O 1 or O N.

For each still empty word slots that have intersections with already filled wordslots , compute a constraint ratio this can vary, sth simple is the number of available solutions at that step and sort the empty wordslots by this ratio complexity O NlogN or O N. Loop through the empty wordslots computed at previous step and for each one try a number of cancdidate solutions making sure that "arc-consistency is retained", ie grid has a solution after this step if this word is used and sort them according to maximum availability for next step ie next step has a maximum possible solutions if this word is used at that time in that place, etc..

If no word found that satisfies the criteria of step. If backtrack found, use the alternative and optionally reset any already filled words that might need reset mark them as unfilled again complexity O N.

If no backtrack found, the no solution can be found at least with this configuration, initial seed etc.. This algorithm does a random consistent walk of the solution tree of the problem. If at some point there is a dead end, it does a backtrack to a previous node and follow another route. Untill either a solution found or number of candidates for the various nodes are exhausted. The consistency part makes sure that a solution found is indeed a solution and the random part enables to produce different solutions in different executions and also on the average have better performance.

The algorithm can be easily parallelized in order to produce more than one different solution at the same time. Why not just use a random probabilistic approach to start with. Start with a word, and then repeatedly pick a random word and try to fit it into the current state of the puzzle without breaking the constraints on the size etc.. If you fail, just start all over again.

Here is some JavaScript code based on nickf's answer and Bryan's Python code. Just posting it in case someone else needs it in js. I'd generate two numbers: Length and Scrabble score. Sort the list by length descending and Scrabble score ascending. Next, just go down the list. If the word doesn't cross with an existing word check against each word by their length and Scrabble score, respectively , then put it into the queue, and check the next word.

Of course, I'm pretty sure that this is O n! I've been thinking about this problem. My sense is that to create a truly dense crossword, you cannot hope that your limited word list is going to be enough. Therefore, you might want to take a dictionary and place it into a "trie" data structure.

This will allow you to easily find words that fill the left over spaces. In a trie, it is fairly efficient to implement a traversal that, say, gives you all words of the form "c?

So, my general thinking is: create some sort of relatively brute force approach as some described here to create a low-density cross, and fill in the blanks with dictionary words. Loop while all cells are filled OR you run out of words OR by limit of iterations then :.

Make the scoring system by easiness of filling, and some estimation calcs. Give score for the current crossword and narrow later choice by append it into list of made crosswords if the score is satisfied by your scoring system.

The idea is to formulate the crossword generation problem as a constraint satisfaction problem and solve it with backtracking with different heuristics to reduce the search space. The following shows the output that was obtained using an implementation of the CSP solving algorithm:. I would get an index of each letter used by each word to know possible crosses. Then I would choose the largest word and use it as base. Select the next large one and cross it. Rinse and repeat. It's probably an NP problem.

Another idea is creating a genetic algorithm where the strength metric is how many words you can put in the grid. From these groups, build sets of a new data structure "word blocks" , which is a primary word that runs through all other words and then the other words that run through the primary word.

Start out the crossword puzzle with the very first of these word blocks in the very top-left position of the crossword puzzle.

For the rest of the word blocks, starting from the right-bottom most position of the crossword puzzle, move upward and leftward, until there are no more available slots to fill. If there are more empty columns upwards than leftwards, move upwards, and vice versa. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Collectives on Stack Overflow. Learn more. Algorithm to generate a crossword [closed] Ask Question. Asked 12 years, 7 months ago.

Active 1 year, 8 months ago. Viewed 93k times. Active Oldest Votes. Basically: Sort all the words by length, descending. Take the first word and place it on the board. Take the next word. Search through all the words that are already on the board and see if there are any possible intersections any common letters with this word. If there is a possible location for this word, loop through all the words that are on the board and check to see if the new word interferes. If this word doesn't break the board, then place it there and go to step 3, otherwise, continue searching for a place step 4.

Continue this loop until all the words are either placed or unable to be placed. At the end of generating a crossword, give it a score based on how many of the words were placed the more the better , how large the board is the smaller the better , and the ratio between height and width the closer to 1 the better.

Generate a number of crosswords and then compare their scores and choose the best one. Instead of running an arbitrary number of iterations, I've decided to create as many crosswords as possible in an arbitrary amount of time. If you only have a small word list, then you'll get dozens of possible crosswords in 5 seconds.

A larger crossword might only be chosen from possibilities. When placing a new word, instead of placing it immediately upon finding an acceptable location, give that word location a score based on how much it increases the size of the grid and how many intersections there are ideally you'd want each word to be crossed by other words.

Keep track of all the positions and their scores and then choose the best one. I happen to be writing this program as we speak, and this is the identical algorothm I chose also. For small numbers of words 10 or less , the program has no trouble calculated all possible solutions in milliseconds.

The algoritm is exponential though. The easy part is writing the basic algorithm that brute-forces through all possible combinations. The hard part is the dozen or so 'short-cuts' you need to prevent the program from trying all the dead-end solutions.

Kaffeine, yep I know what you mean - I had to throw out these options because even though they could create really good grids, it's too hard to check read: I couldn't be bothered , and chances are it's just interference anyway.

Implemented essentially the same approach here: colab. Add a comment. Here's my process: Create a grid of whatever size and a list of words. Shuffle the word list, and then sort the words by longest to shortest. Place the first and longest word at the upper left most position, 1,1 vertical or horizontal. Move onto next word, loop over each letter in the word and each cell in the grid looking for letter to letter matches. When a match is found, simply add that position to a suggested coordinate list for that word.

Loop over the suggested coordinate list and "score" the word placement based on how many other words it crosses.

Scores of 0 indicate either bad placement adjacent to existing words or that there were no word crosses. Back to step 4 until word list is exhausted. Optional second pass. We should now have a crossword, but the quality can be hit or miss due to some of the random placements. So, we buffer this crossword and go back to step 2. If the next crossword has more words placed on the board, it replaces the crossword in the buffer.

This is time limited find the best crossword in x seconds. Bryan Bryan 8 8 silver badges 13 13 bronze badges. Neil N: Probably a better letter matching possibility for the other words. Would be maybe also an approach to sort by the count of distinct letters contained per word, which will mostly lead to the same result.

NeilN Python's array. Bryan, Your website link doesn't work for me, and the primary domain just redirects to Twitter. Do you have an updated link to your code? Here is apparently a clone of Bryan's generator: github.

This doesn't actually help me in my situation, since I'll have a list of only about words. Mine is more like an learning exercise for the user than a word puzzle. Nice description. I thought about this a few times in the past, but never tried it. Now for the magic question: how well did it work? Just for sparse puzzles, or also for dense ones like in the paper?

And how many clues do you need for dense puzzles? Many were completed without intervention but you'd still get maybe a fifth requiring one or two extra words added. I've planning to create crosswords game for Android platform. Each crossword might be in american style first TextView in every question stores question number, and there's no TextView with clue or swedish first TextView stores arrow indicating question's 'direction', and there is TextView with clue visible.

Clicking on TextField leads to showing question and higlighting all other TextFields inside entry. What do you think about this structure? What if I will find out that I can't use a grid with TextViews and TextFields since bad performance and I will have to switch to ListView and row-based rendering then using CrosswordEntryControllers to find what and in which row should be displayed might be really painful.

How can I try to be prepared for such situation without rebuilding whole app? How should I handle switching from horizontal to vertical entry when users taps on something? What are other drawbacks of proposed solution and what can I do better here? Which design pattern would you use here? You need to have a model of a actual crossword letter grid.

You need to look for mutual position because you do not have the above grid. You will also need to look for mutual position as user enters answers. In the current design, the answers, partial answers or guesses of the user seems to reside in the value of the text fields. The program state should have been encapsulated in the model, that's one of the reasons why changing the user interface implementation details would have such a big impact on the overall software.

Users expect to "write letters to squares" not "enter text". Because they may assume the last letter of a question is "s" if the clue states that the answer is plural. In your examples you can just pass in lists of things you want to add one-by-one to the constructor.

Also note that your crossword is not in a valid state until all the questions are added. And no more questions can be added one the construction is complete. If you plan to user that way of interaction then somewhere in your model classes you should have a current direction property, no. Checking whether user have completed the game. Another important design constraint is where will the crosswords come from. If the puzzle will be designed by humans they will decide what type of puzzle the are preparing at the beginning , since there is not a one to one relationship with swedish and american puzzles.

Moreover, american crosswords are expected to be symmetrical, although they are not required to be so technically, whereas swedish style ones are usually not.

Abstract factory may not be a sensible thing in that case. Instead you would want something like "get me a random puzzle of some certain type".

Sign up to join this community. The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Learn more.

Crossword game - designing class structure Ask Question. Asked 9 years ago.