Algorithm to generate a crossword [closed]

by

I came up with a solution which probably isn’t the most efficient, but it works well enough. Basically:

  1. Sort all the words by length, descending.
  2. Take the first word and place it on the board.
  3. Take the next word.
  4. 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.
  5. 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.
  6. 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).
  7. Continue this loop until all the words are either placed or unable to be placed.

This makes a working, yet often quite poor crossword. There were a number of alterations I made to the basic recipe above to come up with a better result.

  • 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 5-6 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 2-3 other words). Keep track of all the positions and their scores and then choose the best one.

More Related Contents:

  1. Custom Weighted Scale [closed]
  2. Finding all possible combinations of numbers to reach a given sum
  3. What is tail call optimization?
  4. How to convert floats to human-readable fractions?
  5. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  6. Why is quicksort better than mergesort?
  7. Data structures for loaded dice?
  8. Pseudorandom Number Generator – Exponential Distribution
  9. Natural Sorting algorithm
  10. What is the fastest integer factorization algorithm?
  11. Is there an algorithm for color mixing that works like mixing real colors?
  12. How to read values from numbers written as words?
  13. Find the missing and duplicate elements in an array in linear time and constant space
  14. Find the first un-repeated character in a string
  15. Function for creating color wheels [closed]
  16. Efficiently reverse the order of the words (not characters) in an array of characters
  17. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  18. What is a bubble sort good for? [closed]
  19. How do I find a factorial? [closed]
  20. Compute rank of a combination?
  21. Efficiently selecting a set of random elements from a linked list
  22. Skip List vs. Binary Search Tree
  23. reconstructing a tree from its preorder and postorder lists
  24. Best way of calculating n choose k?
  25. Generating shuffled range using a PRNG rather than shuffling
  26. Randomly choosing from a list with weighted probabilities
  27. Path generation for non-intersecting disc movement on a plane
  28. Algorithm for permutations of operators and operands
  29. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  30. Tournament bracket placement algorithm

Leave a Comment