Click here to Skip to main content
11,412,516 members (76,438 online)
Click here to Skip to main content

Creating a crossword generator

, 15 Feb 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
Creating an application that can generate crosswords from a list of words

Download source code 

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 :

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.

int CanBePlaced(string word, int x, int y, int dir)
{
            var result = 0;
            if (dir == 0)
            {
                for (var j = 0; j < word.Length; j++)
                {
                    int x1 = x, y1 = y + j;
                    if (!(IsValidPosition(x1, y1) && (_board[x1, y1] == ' ' || _board[x1, y1] =                    = word[j])))
                        return -1;
                    if (IsValidPosition(x1 - 1, y1))
                        if (_hWords[x1 - 1, y1] > 0)
                            return -1;
                    if (IsValidPosition(x1 + 1, y1))
                        if (_hWords[x1 + 1, y1] > 0)
                            return -1;
                    if (_board[x1, y1] == word[j])
                        result++;
                }
            }
            else
            {
                for (var j = 0; j < word.Length; j++)
                {
                    int x1 = x + j, y1 = y;
                    if (!(IsValidPosition(x1, y1) && (_board[x1, y1] == ' ' || _board[x1, y1] =                    = word[j])))
                        return -1;
                    if (IsValidPosition(x1, y1 - 1))
                        if (_vWords[x1, y1 - 1] > 0)
                            return -1;
                    if (IsValidPosition(x1, y1 + 1))
                        if (_vWords[x1, y1 + 1] > 0)
                            return -1;
                    if (_board[x1, y1] == word[j])
                        result++;
                }
            }
            int xStar = x - _dirX[dir], yStar = y - _dirY[dir];
            if (IsValidPosition(xStar, yStar))
                if (!(_board[xStar, yStar] == ' ' || _board[xStar, yStar] == '*'))
                    return -1;
            xStar = x + _dirX[dir]*word.Length;
            yStar = y + _dirY[dir]*word.Length;
            if (IsValidPosition(xStar, yStar))
                if (!(_board[xStar, yStar] == ' ' || _board[xStar, yStar] == '*'))
                    return -1;
            return result == word.Length ? -1 : result;
        }
 

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

void PutWord(string word , int x , int y , int dir, int value)
{
    var mat = dir==0 ? _hWords :_vWords;
    for (var i = 0; i < word.Length; i++)
    {
        int x1 = x + _dirX[dir]*i, y1 = y + _dirY[dir]*i;
        _board[x1, y1] = word[i];
        mat[x1, y1] = value;
    }
    int xStar = x - _dirX[dir], yStar = y - _dirY[dir];
    if (IsValidPosition(xStar, yStar)) _board[xStar, yStar] = '*';
    xStar = x + _dirX[dir]*word.Length;
    yStar = y + _dirY[dir]*word.Length;
    if (IsValidPosition(xStar, yStar)) _board[xStar, yStar] = '*';
}

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. 

 Michael Haephrati CodeProject MVP 2013   

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Michael N Haephrati (האפרתי)
CEO Secured Globe, Inc.
United States United States
Michael Haephrati, is an entrepreneur, inventor and a musician. Haephrati worked on many ventures starting from HarmonySoft, designing Rashumon, the first Graphical Multi-lingual word processor for Amiga computer. During 1995-1996 he worked as a Contractor with Apple at Cupertino. Worked at a research institute made the fist steps developing the credit scoring field in Israel. He founded Target Scoring and developed a credit scoring system named ThiS, based on geographical statistical data, participating VISA CAL, Isracard, Bank Leumi and Bank Discount (Target Scoring, being the VP Business Development of a large Israeli institute).

During 2000, he founded Target Eye, and developed the first remote PC surveillance and monitoring system, named Target Eye.

Other ventures included: Data Cleansing (as part of the DataTune system which was implemented in many organizations.


Follow on   Twitter   Google+   LinkedIn

Comments and Discussions

 
GeneralI LOVED!! Pin
Member 4053434 at 27-Mar-15 12:46
memberMember 405343427-Mar-15 12:46 
GeneralMy vote of 5 Pin
Canny Brisk at 23-Jul-14 21:24
professionalCanny Brisk23-Jul-14 21:24 
GeneralMy vote of 5 Pin
VitorHugoGarcia at 17-Jul-13 23:03
memberVitorHugoGarcia17-Jul-13 23:03 
GeneralMy vote of 5 Pin
alonbarak at 14-Jun-13 12:10
groupalonbarak14-Jun-13 12:10 
GeneralMy vote of 5 Pin
Member 4163524 at 21-Feb-13 6:37
memberMember 416352421-Feb-13 6:37 
GeneralMy vote of 5 Pin
Member 11525325 at 20-Mar-15 12:18
memberMember 1152532520-Mar-15 12:18 
GeneralMy vote of 5 Pin
Mihai MOGA at 16-Feb-13 20:16
memberMihai MOGA16-Feb-13 20:16 
GeneralMy vote of 5 Pin
Boipelo at 16-Feb-13 6:52
memberBoipelo16-Feb-13 6:52 
QuestionCool Pin
i00 at 15-Feb-13 4:19
member i0015-Feb-13 4:19 
AnswerRe: Cool Pin
i00 at 29-Apr-13 19:25
member i0029-Apr-13 19:25 
GeneralMy vote of 5 Pin
Savalia Manoj M at 14-Feb-13 15:44
memberSavalia Manoj M14-Feb-13 15:44 
GeneralMy vote of 5 Pin
khanhamid922 at 11-Feb-13 5:07
memberkhanhamid92211-Feb-13 5:07 
Nice article
GeneralMy vote of 5 Pin
rumilal at 11-Feb-13 4:58
memberrumilal11-Feb-13 4:58 
GeneralGreat Pin
Anand Gunasekaran at 8-Feb-13 22:55
memberAnand Gunasekaran8-Feb-13 22:55 
GeneralMy vote of 5 Pin
Monjurul Habib at 2-Feb-13 8:04
memberMonjurul Habib2-Feb-13 8:04 
GeneralMy vote of 5 Pin
balam1988 at 24-Jan-13 23:25
groupbalam198824-Jan-13 23:25 
GeneralRe: My vote of 5 Pin
Michael Haephrati מיכאל האפרתי at 24-Jan-13 23:41
mvpMichael Haephrati מיכאל האפרתי24-Jan-13 23:41 
GeneralMy vote of 5 Pin
evan897 at 24-Jan-13 22:46
groupevan89724-Jan-13 22:46 
GeneralMy vote of 5 Pin
Rutuanie at 24-Jan-13 20:32
memberRutuanie24-Jan-13 20:32 
GeneralMy vote of 5 Pin
Edo Tzumer at 23-Jan-13 3:14
memberEdo Tzumer23-Jan-13 3:14 
GeneralGood Article Pin
Azziet at 23-Jan-13 2:21
memberAzziet23-Jan-13 2:21 
GeneralMy vote of 3 Pin
Azziet at 23-Jan-13 2:20
memberAzziet23-Jan-13 2:20 
GeneralMy vote of 5 Pin
Sanjay_007 at 22-Jan-13 23:52
memberSanjay_00722-Jan-13 23:52 
QuestionVery cool! Pin
Frosty7 at 21-Jan-13 10:29
memberFrosty721-Jan-13 10:29 
GeneralMy vote of 5 Pin
kentclark519 at 20-Jan-13 5:54
memberkentclark51920-Jan-13 5:54 
GeneralRe: My vote of 5 Pin
Michael Haephrati מיכאל האפרתי at 20-Jan-13 6:13
mvpMichael Haephrati מיכאל האפרתי20-Jan-13 6:13 
GeneralMy vote of 5 Pin
faruk196830 at 20-Jan-13 2:59
memberfaruk19683020-Jan-13 2:59 
GeneralMy vote of 5 Pin
srinivasreddypg at 19-Jan-13 23:04
membersrinivasreddypg19-Jan-13 23:04 
GeneralMy vote of 5 Pin
nayeemsazzad at 19-Jan-13 22:52
groupnayeemsazzad19-Jan-13 22:52 
GeneralMy vote of 5 Pin
arif1111142 at 19-Jan-13 22:41
grouparif111114219-Jan-13 22:41 
GeneralMy vote of 5 Pin
John Klinner at 19-Jan-13 22:13
memberJohn Klinner19-Jan-13 22:13 
GeneralMy vote of 5 Pin
evan897 at 19-Jan-13 11:39
groupevan89719-Jan-13 11:39 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.150427.1 | Last Updated 16 Feb 2013
Article Copyright 2013 by Michael N Haephrati (האפרתי)
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid