Crossword Puzzle Dynamic Generation Algorithm [Ideas]

[System123]

Hi

I need some help with algorithm ideas for generating a crossword puzzle from an array of words. The puzzle size is 25 x 25 and the word list contains any amount of words. I have tried some ideas but they not working out to well, I am coding in JAVA but C or Pascal code could be helpful too.

Thanks

[gravaera]

All good systems start off with a good design stage:

1. Create a specification for yourself: "Create a program which is able to spawn a matrix of characters and insert certain words from a list into the matrix contiguously."

2. Reason it out: Try highlighting the nouns in the specification to understand what constructs you need to build:
PROGRAM, CHARACTER MATRIX, WORD, WORD LIST. This identifies the problem domain. Now cross off those items which are outside of your problem domain, and concentrate on building a module/set of functions/whatever that would provide the relevant abstractions. From the above, since PROGRAM is more or less going to be created as a result of you creating constructs from the other problem keywords, you can afford to cross it out. That leaves you having to implement a CHARACTER MATRIX, WORD ABSTRACTION, WORDS LIST ABSTRACTION.

In C++, this would be simple, since it means that you've now identified all of the necessary classes to build the system, but in C, you should now break it down a bit more:

To abstract a CHARACTER MATRIX, you need to define functions to manipulate a two dimensional array of (depending on whether the user gets to choose the size of the crossword or not) unknown or known size. Get to it

To implement a WORD abstraction, you should first concentrate on the WORD LIST abstraction, since the final implementation of the WORD LIST will determine how you will include the WORDs from the WORD LIST into the CHARACTER MATRIX.

A WORD LIST can be implemented as a simple linked list of char pointers, read from a file at startup of the program/module. From here, we can decide on how a WORD can be implemented: It already is implemented in the WORD LIST linked list.

To fill up the matrix with contiguous words, use an algorithm that first fills up the matrix with random characters. Then, after that, it goes through the linked list of words form the file, and inserts them at random offsets in a random direction. Keep a second matrix as a bitmap, and for every word you insert into the real crossword, insert it there, too. Using the bitmap matrix, you can do checks on each index as you insert a new word to see if that space already has a word from the list. In that case, you need to place the word somewhere else.

A smart algorithm would pre-check the crossword matrix for enough space contiguously in a particular direction (to the right, or upwards, or downward, or to the left, or if you have the time to implement diagonal insertion, then diagonal-upwards-right, diagonal upward-left, etc), and if enough free space is found, then it inserts it. Otherwise it generates another random insertion point.

The bitmap matrix also serves a double purpose: you would no doubt need to know when the user has found a word, right? You can't use the real Matrix for that, since it's kind of cluttered with random characters all around. So to check to see if the user has found a word, just look for the specified index and the number of characters he checked off as an offset from there, and see if the bitmap indicates that range is used.

-All the best
gravaera.

[Combuster]

Constraint Satisfaction Problem

[AndrewAPrice]

Try Googling "crossword generation algorithm" - 52,100 results.