Creating a crossword generator

Introduction

This article describes a simple application that can place a list of words, in either right-to-left or left-to-right language in a matrix, as a crossword.

Background

A crossword is a word puzzle created from a grid of white and black squares, placing words horizontally and vertically on these squares while each two words which cross each other require having an identical letter at the place they are crossed.

The application described and included in this article is useful whenever there is a need to create a mechanism which will place words as a crossword, which would be the first step before composing clues and questions in which their answers will forms these words.

The Application

While designing this application, there were several guidelines to comply with:

Supporting right-to-left languages, such as Hebrew. To comply with this requirements words in such language goes from right to left, when placed horizontally, and still, from top to bottom when placed vertically. Latin words are place left to right, and from top to bottom.

Minimal distance between words placed at the same dimension. Two words placed horizontally or vertically one after the other will have at least one black square separating between the two.

An optimization process, used to find the optimal arrangement of any given set of words, which leave a minimum number of black square.

Loading words from a file, or placing them manually. The file should be an ASCII one, with one word per line.

The Code

The demo source code was created using c# and Visual Studio 2010.

There are several building blocks:

First, per each word about to be placed, we check if this place is valid :

Hide Copy Code

bool IsValidPosition(int x , int y) { return x >= 0 && y >= 0 && x < _n && y < _m; }

Even if the position is valid, we also check if there is no other word crossing the word we are about to place, and if there is, the crossing point must have the same letter, both for the word placed horizontally and the word placed vertically.

Then, when we actually place the word, we call:

This application is meant only for demonstration purposes. It creates a matrix of 13 X 17. The "Optimize" button, tries to place the list of given words randomly while seeking for the optimal result for up to 1 minute. Obviously, this is not optimizing, and there can be many improvements, which will be more than welcomed.