Click here to Skip to main content
15,172,953 members
Articles / Programming Languages / C#
Article
Posted 19 Jan 2013

Tagged as

Stats

109.9K views
6.3K downloads
118 bookmarked

Creating a Crossword Generator

Rate me:
Please Sign up or sign in to vote.
4.98/5 (70 votes)
11 Apr 2018CPOL2 min read
Creating an application that can generate crosswords from a list of words
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 form these words.

Image 1

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 requirement, words in such language go from right to left, when placed horizontally, and still, from top to bottom when placed vertically. Latin words are placed 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, for each word about to be placed, we check if this place is valid:

C#
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.

C#
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:

C#
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 welcome.

History

  • 19th January, 2013: Initial version

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 Haephrati
CEO Secured Globe, Inc.
United States United States
Michael Haephrati, Musician and CEO and co-founder of Secured Globe, Inc. 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.

You can also Buy me coffee.





Comments and Discussions

 
Questioni need a board of words without crosswords. Pin
Member 1351188320-Jan-19 6:29
MemberMember 1351188320-Jan-19 6:29 
QuestionPuzzle size Pin
Member 802770514-Apr-18 4:47
MemberMember 802770514-Apr-18 4:47 
QuestionVery cool Pin
RickKelleher12-Apr-18 11:31
MemberRickKelleher12-Apr-18 11:31 
QuestionNot where real crossword creators start Pin
coderz212-Apr-18 6:37
Membercoderz212-Apr-18 6:37 
QuestionGrids Pin
PeejayAdams12-Apr-18 4:46
MemberPeejayAdams12-Apr-18 4:46 
Questionnice job Pin
User 418025411-Apr-18 9:58
MemberUser 418025411-Apr-18 9:58 
Question[My vote of 2] Shouldn't all boxes be filled Pin
ovisariesdk29-May-17 5:23
Memberovisariesdk29-May-17 5:23 
AnswerRe: [My vote of 2] Shouldn't all boxes be filled Pin
Michael Haephrati11-Jun-17 10:58
mvaMichael Haephrati11-Jun-17 10:58 
Questionoptimize button Pin
Member 122393382-Jan-16 11:49
MemberMember 122393382-Jan-16 11:49 
AnswerRe: optimize button Pin
Michael Haephrati2-Jan-16 12:29
mvaMichael Haephrati2-Jan-16 12:29 
GeneralI LOVED!! Pin
Member 405343427-Mar-15 12:46
MemberMember 405343427-Mar-15 12:46 
GeneralMy vote of 5 Pin
Joezer BH23-Jul-14 21:24
professionalJoezer BH23-Jul-14 21:24 
GeneralMy vote of 5 Pin
_Vitor Garcia_17-Jul-13 23:03
Member_Vitor Garcia_17-Jul-13 23:03 
GeneralMy vote of 5 Pin
alonbarak14-Jun-13 12:10
Memberalonbarak14-Jun-13 12:10 
GeneralMy vote of 5 Pin
Member 416352421-Feb-13 6:37
MemberMember 416352421-Feb-13 6:37 
GeneralMy vote of 5 Pin
Roberto_4420-Mar-15 12:18
MemberRoberto_4420-Mar-15 12:18 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA16-Feb-13 20:16
professionalȘtefan-Mihai MOGA16-Feb-13 20:16 
GeneralMy vote of 5 Pin
Boipelo16-Feb-13 6:52
MemberBoipelo16-Feb-13 6:52 
QuestionCool Pin
i0015-Feb-13 4:19
Memberi0015-Feb-13 4:19 
AnswerRe: Cool Pin
i0029-Apr-13 19:25
Memberi0029-Apr-13 19:25 
GeneralMy vote of 5 Pin
Savalia Manoj M14-Feb-13 15:44
MemberSavalia Manoj M14-Feb-13 15:44 
GeneralMy vote of 5 Pin
khanhamid92211-Feb-13 5:07
Memberkhanhamid92211-Feb-13 5:07 
Nice article
GeneralMy vote of 5 Pin
rumilal11-Feb-13 4:58
Memberrumilal11-Feb-13 4:58 
GeneralGreat Pin
Anand Gunasekaran8-Feb-13 22:55
professionalAnand Gunasekaran8-Feb-13 22:55 
GeneralMy vote of 5 Pin
Monjurul Habib2-Feb-13 8:04
professionalMonjurul Habib2-Feb-13 8:04 

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

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