crossword puzzle generator

[nuderobmonkey]

Yes, there at time still a thread open at this topic, opened by @Merari
http://www.cplusplus.com/forum/general/270089/#msg1163324

But its approach on how to solve placing the words within its grid seemed somewhere wrong. So I decided to wrote my own generator. At the time I have still somewhere an error by detecting which fields in the grid are valid for a new word.

I invite everyone who is interested in this exciting challenge to look at my code and perhaps finds the error(s). And I'm seriously interested in hints, or maybe someone could tell me that I'm on the wrong track.

#include <iostream>
#include <vector>
#include <fstream>
#include <random>
#include <stdexcept>

/* Holds its coordinates and a 'weight'.
 */
struct Weight
{
    int x;
    int y;
    int wt;
    Weight(int xx=0, int yy=0, int ww=0)
    : x{xx}, y{yy}, wt{ww}
    {}
};

/* The crossword puzzle generator class :-)
 * Its grid at each border side is at each one field broader than its 'box' inside. That's for
 * easier testing the borders of the words.
 */
class Cwg
{
public:
    Cwg( int width, int height );
    
    bool emplaceWord( const std::string & word, bool horizontally );

private:
    Weight highestWeight( const std::string & word, bool horizontally ) const;
    Weight doWeight( const std::string & word, int width, int height, bool horizontally ) const;
    
    std::vector<std::vector<char>> m_grid;
    friend std::ostream & operator<<( std::ostream &, const Cwg & );
};

Cwg::Cwg( int width = 16, int height = 16 )
{
    // Consider that the 'effective' room is width-2, height-2.
    for( int h = 0; h < height; ++h )
    {
        std::vector<char> tmp;
        for( int w = 0; w < width; ++w )
        {
            tmp.push_back('.');
        }
        m_grid.push_back( tmp );
    }
}

/* This method emplaces a word on the grid depending on the return value of Cwg::highestWeight().
 * The word will positioned at the coordinates of that Weight object.
 * If no position could found, the method returns false, otherwise true.
 *
 * See also Cwg::doWeight()
 */
bool Cwg::emplaceWord( const std::string & word, bool horizontally = true )
{
    try {
    if( horizontally )
    {
        Weight weight = highestWeight( word, horizontally );
        std::cerr << word << ':' << weight.x << ',' << weight.y << ','
                  << 'h' << weight.wt << '\n';
        if( weight.wt == -1 )
            return false;
        for( int p = 0; p < word.length(); ++p)
        {
            m_grid.at(weight.y).at(weight.x+p) = word[p];
        }
    }    
    else  // word will placed vertically
    {
        Weight weight = highestWeight( word, (! horizontally) );
        std::cerr << word << ':' << weight.x << ',' << weight.y << ','
                  << 'w' << weight.wt << '\n';
        if( weight.wt == -1 )
            return false;
        for( int p = 0; p < word.length(); ++p )
        {
            m_grid.at(weight.y+p).at(weight.x) = word[p];
        }
    }
    } catch (...) { std::cerr << "emplaceWord() e1:\n"; throw; }
    
    std::cerr << *this << '\n';
    return true;
}

/* This method returns the position for a word at the grid with the highest weight.
 * See Cwg::doWeight
 */
Weight Cwg::highestWeight( const std::string & word, bool horizontally = true ) const
{
    Weight weight(1,1,0);
    
    try {
    
    if( horizontally )
    {
        for( int h = 1; h < m_grid.size()-1; ++h )
        {
            for( int w = 1; w < m_grid.at(0).size()-word.length()-1; ++w )
            {
                Weight tmpWeight = doWeight( word, w, h, horizontally );
                if( tmpWeight.wt > weight.wt )
                    weight = tmpWeight;
            }
        }
    }
    else  // bool horizontally is false, so we test for vertically matches
    {
        for( int h = 1; h < m_grid.size()-word.length()-1; ++h )
        {
            for( int w = 1; w < m_grid.at(0).size()-1; ++w )
            {
                Weight tmpWeight = doWeight( word, w, h, ! horizontally );
                if( tmpWeight.wt > weight.wt )
                    weight = tmpWeight;
            }
        }
    }
    
    } catch (...) { std::cerr << "highestWeight() e1:\n"; throw; }
    
    return weight;
}
                

/* This method tests if a word matches within a distinct grid position.
 * If the word fits into the position, it returns by default a weight of 0.
 * For each matching intersection with another word the weight increases by 1.
 * If the word doesn't match at the position, the weight gets -1.
 */
Weight Cwg::doWeight( const std::string & word, int width, int height, bool horizontally = true ) const
{
    // ! The grid has at each side a margin of 1 that must be letten free.
     
    Weight weight(width,height,0);
    
    try {
 
    if( horizontally )
    {
        for( int p = 0; p < word.length(); ++p )
        {
            if( word[p] == m_grid.at(height).at(width+p) ) {
                ++weight.wt;
                continue;
            }
            if( m_grid.at(height-1).at(width+p) != '.' 
                || m_grid.at(height+1).at(width+p) != '.'
            ){   
                weight.wt = -1;
                return weight;
            }
        }
        // test left and right ends of the word position
        if( m_grid.at(height).at(width-1) != '.'
            || m_grid.at(height).at(width+word.size()) != '.'
        ){
            weight.wt = -1;
            return weight;
        }
        return weight;
    }
    else  // bool horizontally is false, so words will get tested vertically
    {
        for( int p = 0; p < word.length(); ++p )
        {
            if( word[p] == m_grid.at(height+p).at(width) ) {
                ++weight.wt;
                continue;
            }
            if( m_grid.at(height+p).at(width-1) != '.'
                || m_grid.at(height+p).at(width+1) != '.'
            ){
                weight.wt = -1;
                return weight;
            }
        }
        if( m_grid.at(height-1).at(width) != '.'
            || m_grid.at(height+word.size()).at(width) != '.'
        ){
            weight.wt = -1;
            return weight;
        }
        return weight;
    }
    } catch (...) { std::cerr << "doWeight() e1:\n"; throw; }
    // this line should never get proceeded
    throw std::logic_error( "e1 in Cwg::doWeight()\n" );
}
 
/* Overloads operator<< at std::ostream for << the grid.
 */
std::ostream & operator<<( std::ostream & os, const Cwg & cwg )
{
    for( const auto & row : cwg.m_grid ) {
        for( const char c : row )
            os << ' ' << c;
        os <<  '\n';
    }
    return os;
}

std::vector<std::string> dictionary = { "apache", "anchor", "banana", "beaver", "bear", "bussard",
"chocolate", "driver", "elephant", "eagle", "fog", "gear", "agony", "host", "harrassment",
"ice", "icebear", "bicycle", "rotten", "dread", "loo", "christmas", "handle", "theatre", "solvent",
"mouse", "rabbit", "dere", "sailor", "craftsman", "hooligan", "ananas", "cherry", "cranberry" };
 
int main( int argc, char * argv[] )
{

/* commented out for testing proposals
    // The file handling:
    
    std::string dictName = "dictionary.txt";
    if( argc > 1 ) dictName = argv[2];
    std::ifstream ifile( dictName );
    if( !ifile ) {
        std::cerr << "File '" << dictName << "'could't opened!\n";
        return 1;
    }
    std::vector<std::string> dictionary;
    std::string tmp;
    while ( ifile >> tmp ) dictionary.push_back( tmp );
*/
    std::default_random_engine eng( std::random_device{}() );
    std::uniform_int_distribution<> dist( 0, dictionary.size()-1 );


    // The crossword puzzle generator in action:

    Cwg cwg;
    
    while( true )
    {
        std::string word = dictionary[ dist(eng) ];
        if( ! cwg.emplaceWord(word,true) ) break;
        word = dictionary[ dist(eng) ];
        if( ! cwg.emplaceWord(word,false) ) break;
    }
    
    std::cout << cwg << '\n';
}

[nuderobmonkey]

Here the finished program.

part 1/2:

#include <iostream>
#include <vector>
#include <fstream>
#include <random>
#include <stdexcept>

/* Holds its coordinates and a 'weight'.
 * If the word doesn't fit in the grid, weight is -1.
 * If the word fit, but there are no intersections with characters of other words, weight is 0.
 * If the word fit, and there are intersections with characters of other words, weight is the
 * sum of all intersected characters.
 */
struct Weight
{
    int x;   // column
    int y;   // row
    int wt;  // weight 
    Weight(int xx=0, int yy=0, int ww=0)
    : x{xx}, y{yy}, wt{ww}
    {}
};

/* The crossword puzzle generator class :-)
 * Its grid at each border side is at each one field broader than its 'box' inside. That's for
 * easier testing the borders of the words.
 */
class Cwg
{
public:
    Cwg( int width, int height );
    Cwg();
    
    bool emplaceWord( const std::string & word, bool horizontally );

private:
    Weight highestWeight( const std::string & word, bool horizontally ) const;
    Weight doWeight( const std::string & word, int width, int height, bool horizontally ) const;
    
    std::vector<std::vector<char>> m_grid;
    friend std::ostream & operator<<( std::ostream &, const Cwg & );
};

Cwg::Cwg( int width, int height )
{
    if( width < 3 ) width = 3;
    if( height < 3 ) height = 3;

    // Consider that the 'effective' room is width x height.
    for( int h = 0; h < height+2; ++h )
    {
        std::vector<char> tmp;
        for( int w = 0; w < width+2; ++w )
        {
            tmp.push_back('.');
        }
        m_grid.push_back( tmp );
    }
}
Cwg::Cwg() : Cwg{16,16} {}

/* This method emplaces a word on the grid depending on the return value of Cwg::highestWeight().
 * The word will positioned at the coordinates of that Weight object.
 * If no position could found, the method returns false, otherwise true.
 *
 * See also Cwg::doWeight()
 */
bool 
Cwg::emplaceWord( const std::string & word, bool horizontally = true )
{
    try {
    
    // check that the word is not too long for the grid
    if( horizontally )
        if( word.length() > m_grid.at(0).size()-2 )
            return false;
    else
        if( word.length() > m_grid.size()-2 )
            return false;
            
    Weight weight = highestWeight( word, horizontally );
    //std::cerr << word << ':' << '(' << weight.x << ',' << weight.y << ','
    //          << weight.wt << ')'<< '\n';
    if( weight.wt == -1 )
        return false;   // word doesn't match within the grid

    if( horizontally )
    {
        for( int p = 0; p < word.length(); ++p)
        {
            m_grid.at(weight.y).at(weight.x+p) = word[p];
        }
    }    
    else  // word will placed vertically
    {
        for( int p = 0; p < word.length(); ++p )
        {
            m_grid.at(weight.y+p).at(weight.x) = word[p];
        }
    }
    } catch (...) { std::cerr << "emplaceWord() e1:\n"; throw; }
    
    //std::cerr << *this << '\n';
    return true;
}

/* This method returns the position for a word at the grid with the highest weight.
 * See Cwg::doWeight()
 *
 * Consider that the the there is a border of 1 field at each side of the grid.
 */
Weight 
Cwg::highestWeight( const std::string & word, bool horizontally = true ) 
const
{
    Weight weight(1,1,-1);
    
    try {
    
    if( horizontally )
    {
        for( int h = 1; h < m_grid.size()-1; ++h )
        {
            for( int w = 1; w < m_grid.at(0).size()-word.length()-1; ++w )
            {
                Weight tmpWeight = doWeight( word, w, h, true );
                if( tmpWeight.wt > weight.wt )
                    weight = tmpWeight;
            }
        }
    }
    else  // bool horizontally is false, so we test for vertically matches
    {
        for( int h = 1; h < m_grid.size()-word.length()-1; ++h )
        {
            for( int w = 1; w < m_grid.at(0).size()-1; ++w )
            {
                try {
                Weight tmpWeight = doWeight( word, w, h, false );
                if( tmpWeight.wt > weight.wt )
                    weight = tmpWeight;
                 } catch (...) { std::cerr<<"highestWeight() e2: w"<<w<<"h"<<h<<"\n"; throw; }
            }
        }
    }
    
    } catch (...) { std::cerr << "highestWeight() e1:\n"; throw; }
    
    //std::cerr << "x("<< weight.x <<','<< weight.y <<','<< weight.wt <<')';
    return weight;
}
                

/* This method tests if a word matches within a distinct grid position.
 * If the word fits into the position, it returns by default a weight of 0.
 * For each matching intersection with another word the weight increases by 1.
 * If the word doesn't match at the position, the weight gets -1.
 */
Weight 
Cwg::doWeight( const std::string & word, int width, int height, bool horizontally = true )
const
{
    // Each word needs at minimum a distance by one field in each direction to its neighbours.
     
    Weight weight(width,height,0);  // Needs to be 0 weighted!
    
    
    try {
 
    if( horizontally )
    {
        try {
        for( int p = 0; p < word.length(); ++p )
        {
            // test the place as such
            if( word[p] == m_grid.at(height).at(width+p) ) {
                ++weight.wt;
                continue;
            } else if( m_grid.at(height).at(width+p) != '.' ) {
                weight.wt = -1;
                break;
            }
            
            // test upper and lower bounds
            if( m_grid.at(height-1).at(width+p) != '.' 
                || m_grid.at(height+1).at(width+p) != '.'
            ){   
                weight.wt = -1;
                break;
            }
        }
        // test left and right neighbours of the word position
        if( m_grid.at(height).at(width-1) != '.'
            || m_grid.at(height).at(width+word.size()) != '.'
        ){
            weight.wt = -1;
        }
        } catch (...) {
            std::cerr<<"doWeight() e5: width"<<width<<"height"<<height
                     <<"horizontally"<<horizontally<<'\n';
            throw;
        }
    }
    else  // bool horizontally is false, so words will get tested vertically
    {
        for( int p = 0; p < word.length(); ++p )
        {
            try {
            // test the place as such
            if( word[p] == m_grid.at(height+p).at(width) ) {
                ++weight.wt;
                continue;
            } else if( m_grid.at(height+p).at(width) != '.' ) {
                weight.wt = -1;
                break;
            }
            } catch (...) { 
                std::cerr << "doWeight() e2: width"<<width<<"height"<<height<<"p"<<p<<'\n';
                throw;
            }
                                
            try {
            // test for left and right bounds     
            if( m_grid.at(height+p).at(width-1) != '.'
                || m_grid.at(height+p).at(width+1) != '.'
            ){
                weight.wt = -1;
                break;
            }
            } catch (...) {
                std::cerr << "doWeight() e3: width"<<width<<"height"<<height<<"p"<<p<<'\n';
                throw;
            }   
        }
        try {
        // test upper and lower neighbours of the word position
        if( m_grid.at(height-1).at(width) != '.'
            || m_grid.at(height+word.size()).at(width) != '.'
        ){
            weight.wt = -1;
        }
        } catch (...) {
            std::cerr<<"doWeight() e4: height"<<height<<"width"<<width<<'\n';
            throw;
        }
    }
    } catch (...) { std::cerr << "doWeight() e1:\n"; throw; }
    
    //std::cerr << '('<<weight.x<<','<<weight.y<<','<<weight.wt<<')';  // correct
    return weight;
}
 
/* Overloads operator<< at std::ostream for << the grid.
 */
std::ostream & operator<<( std::ostream & os, const Cwg & cwg )
{
    for( const auto & row : cwg.m_grid ){
        for( const char c : row )
            os << ' ' << c;
        os <<  '\n';
    }
    return os;
}

[nuderobmonkey]

part 2/2:

// for debugging proposals
std::vector<std::string> dictionary = { "apache", "anchor", "banana", "beaver", "bear", "bussard",
"chocolate", "driver", "elephant", "eagle", "fog", "gear", "agony", "host", "harrassment",
"ice", "icebear", "bicycle", "rotten", "dread", "loo", "christmas", "handle", "theatre", "solvent",
"mouse", "rabbit", "dere", "sailor", "craftsman", "hooligan", "ananas", "cherry", "cranberry" };
 
int main( int argc, char * argv[] )
{   
    // The file handling:
    
    std::string dictName = "dictionary.txt";
    if( argc > 1 ) dictName = argv[2];
    std::ifstream ifile( dictName );
    if( !ifile ) {
        std::cerr << "File '" << dictName << "'could't opened!\n";
        return 1;
    }
    std::vector<std::string> dictionary;
    std::string tmp;
    while ( ifile >> tmp ) dictionary.push_back( tmp );

    std::default_random_engine eng( std::random_device{}() );
    std::uniform_int_distribution<> dist( 0, dictionary.size()-1 );


    // The crossword puzzle generator in action:

    Cwg cwg{20,20};
 
    bool horizontal = true;
    for( int i = 0; i < 100; ++i )
    {
        std::string hor = dictionary[ dist(eng) ];
        std::string vert = dictionary[ dist(eng) ];
        for( auto & c : hor ) { if(!std::isalpha(c)) goto label_end; c = std::tolower(c); }
        for( auto & c : vert ) { if(!std::isalpha(c)) goto label_end; c = std::tolower(c); }
        cwg.emplaceWord(hor,true);
        cwg.emplaceWord(vert,false);
        
label_end: ;
    }

    std::cout << cwg << '\n';
}

 . . . . . . . . . . . . . . . . . . . . . .
 . h u m i l i t i e s . a . . . b . n . u .
 . . . . n . . . . . . . b . . . r . i . n .
 . w . . t . d . o . . d u b b . o . c . p .
 . i e l e n e . l . . . i . . . n . o . a .
 . n . . r . g . e c b o l e . . c . l . s .
 . t . . c . r . i . e . d . . . h . i . t .
 . e . . i . a . f . l o i s e . o . n . e .
 . r . . d . d . e . e . n . . . p . e . d .
 . f . . o . e . r . a . g . m . l . . . . .
 . e . . n . d . o . p . . . a . e . . . . .
 . e . . a . . . u . . . . . r . g . h . . .
 . d . . . . t e s t u d i n a r i o u s . .
 . . . . . . . . . . . . . . t . a . c . l .
 . f r e n e t i c a l l y . t . . . h . y .
 . . . n . . . . . . . . . s i a m . e . e .
 . d o o m s d a y s . . . . a . . . n . r .
 . . . . . . . . . . . . . . l . . . . . y .
 . s o o t p r o o f . . s o e k a r n o . .
 . . . . . . . . . . . . . . s . . . . . . .
 . h a t c h e t l i k e . . . v i n i a . .
 . . . . . . . . . . . . . . . . . . . . . .

[closed account j30o8vqX]

Hello, congratulations on this result, I always torture my mind to come to the end of my idea. I was advised to do a function to place the words: it would help for the recursive side absolutely necessary. But I'm not as fast! :)

[dutch]

#include <iostream>
#include <fstream>
#include <vector>
#include <random>
using namespace std;

const int GridSize = 30;
const int ShortestWord = 4, LongestWord = 7;
const int MaxTries = 10000;
const string WordFile = "wordlist.txt";

// Global Random Engine
default_random_engine RndEngine{ random_device{}() };

enum Dir { DirHorz, DirVert };
Dir operator!(Dir dir) { return dir == DirHorz ? DirVert : DirHorz; }

struct Point {
    int row, col;
    Dir dir;
    Point(int r, int c, Dir d) : row(r), col(c), dir(d) { }
    bool operator==(const Point& p) const {return row == p.row && col == p.col;}
};

using Grid      = char[GridSize][GridSize];
using PointList = vector<Point>;
using Letters   = PointList[26];  // one for each letter (0 is 'A', etc.)
using WordList  = vector<string>;

string pick_rnd_word(const WordList& wordList) {
    uniform_int_distribution<> dist(0, wordList.size() - 1);
    return wordList[dist(RndEngine)];
}

void add_word(Grid grid, Letters& letters, const string& word, Point pnt) {
    auto& line = (pnt.dir == DirHorz ? pnt.col : pnt.row);
    int start = line;
    for (unsigned pos = start, w = 0; pos < start + word.size(); ++pos) {
        char ch = toupper(word[w++]);
        auto& letter = letters[ch - 'A'];
        line = pos;
        letter.push_back(pnt);
        grid[pnt.row][pnt.col] = ch;
    }
}

void place_initial_word(Grid grid, const string& word, Letters& letters) {
    uniform_int_distribution<> distDir(0, 1);
    add_word(grid, letters, word,
             Point(0, 0, distDir(RndEngine) ? DirHorz : DirVert));
}

bool can_place(Grid grid, const string& word, int w, const PointList::iterator p) {
    int r = p->row, c = p->col, dir = !p->dir;
    if (dir == DirHorz) {
        c -= w;
        if (c < 0 || c + word.size() > GridSize
         || (c > 0 && grid[r][c - 1] != '.')
         || (c + word.size() < GridSize && grid[r][c + word.size()] != '.'))
            return false;
        for (int i = 0; i < int(word.size()); ++i, ++c) {
            if (i == w) continue;
            if (                     grid[r    ][c] != '.'
             || (r > 0            && grid[r - 1][c] != '.')
             || (r < GridSize - 1 && grid[r + 1][c] != '.'))
                return false;
        }
    }
    else {
        r -= w;
        if (r < 0 || r + word.size() > GridSize
         || (r > 0 && grid[r - 1][c] != '.')
         || (r + word.size() < GridSize && grid[r + word.size()][c] != '.'))
            return false;
        for (int i = 0; i < int(word.size()); ++i, ++r) {
            if (i == w) continue;
            if (                     grid[r][c    ] != '.'
             || (c > 0            && grid[r][c - 1] != '.')
             || (c < GridSize - 1 && grid[r][c + 1] != '.'))
                return false;
        }
    }
    return true;
}

bool place_crossing_word(Grid grid, const WordList& wordList, Letters& letters) {
    for (int i = 0; i < MaxTries; ++i) { // give up after this many tries
        string word = pick_rnd_word(wordList);
        for (unsigned w = 0; w < word.size(); ++w) {
            auto& points = letters[toupper(word[w]) - 'A'];
            for (auto p = points.begin(); p != points.end(); ++p)
                if (can_place(grid, word, w, p)) {
                    Point pnt(p->row, p->col, !p->dir);
                    if (pnt.dir == DirHorz) pnt.col -= w; else pnt.row -= w;
                    add_word(grid, letters, word, pnt);
                    return true;
                }
        }
    }
    return false;
}

void print_grid(const Grid grid) {
    for (int r = 0; r < GridSize; ++r) {
        for (int c = 0; c < GridSize; ++c)
            cout << (grid[r][c] == '.' ? ' ' : grid[r][c]) << ' ';
        cout << '\n';
    }
}

WordList read_word_list(const string& filename) {
    WordList wordList;
    ifstream in(filename);
    for (string word; in >> word; )
        if (word.size() >= ShortestWord && word.size() <= LongestWord)
            wordList.push_back(word);
    return wordList;
}

int main() {
    Letters letters;
    WordList wordList = read_word_list(WordFile);
    Grid grid;
    fill((char*)grid, (char*)grid + GridSize*GridSize, '.');
    place_initial_word(grid, pick_rnd_word(wordList), letters);
    while (place_crossing_word(grid, wordList, letters)) ;
    print_grid(grid);
}

T W I C E   O W I N G   B E A R D S     Q     B O O S   B   
    M               I   A               U     E         A   
  U P T U R N S     L   T     L     S W A T H E D   P   N   
    E               D U M P I E R   T   L     T     H   K   
R A N K S     M         E     C     A   M     S   S A N E   
E   D     L   O R D A I N     H     L   S   M       S   D   
C   S E X I E R               E     E     P U Z Z L E D   L 
C         N   R E F U G E S   R O A D       T       D     A 
E     D   E   O               Y             A         F   T 
S A G E R     W                   S L A K I N G     M U C H 
      S       S I C K B A Y       H         T     S   T     
  O X I D E         I   B     C L O S E S T   B L I T Z     
J     R             D   O   T     T               M       M 
A   R E C I P E S   D   U   O     G L E A M     S I D E   O 
M                   E   T   A     U           L   L       U 
B I D S             R   S A D D E N S   U N R I P E R     L 
S   W   M I N I B U S       I       T         F     O     T 
    I   E       U     D R I E D   N E G L E C T     B O A S 
    N   T       N           D   D   E               E       
B A D G E R S   C I T I E S     I   L E A F Y   N E S T S   
L   L   S       H         I   W A K E   R     A           W 
A   E       P R E T A X   C     L   D   E     M           A 
Z           O   S         K       Z     S E T U P     C   R 
E       Q   S     L A B E L   G   O           L       Y   D 
S   L   U   T   C         E   R   O       P   E D G I N G S 
    U   A   M   A     R A D I A L S   S H U N T       I     
    B A R B E R S     A       Z           K     T O U C A N 
    I   T   N   T     V   Q U I B B L E   E               U 
    N   E             E       N                           K 
    G   T       S K U L L S   G U N B O A T     S T A N C E 

[nuderobmonkey]

Thank you @dutch, what a nice solution, I enjoyed reading your code. It's a nice Idea saving the points of each letter and testing for a connection to it. This has the advantage in contrast to my own solution that every word is connected to another. The only weak point as far as it is, is that there could be no cross-connections to more than one word. But I'm sure there will be a solution which wipes out that last flaw.

Maybe we could combine both solutions, the connectiveness and the 'weight'.

[dutch]

I'm glad you found it fairly easy to read.
You're right about the potential weakness of connecting all words ultimately to the very first one in the upper left corner.
Surprisingly it seems to work out pretty well most of the time, at least with a good enough word list. It even creates a kind of maze-like pattern!

I used a word list that I found in the code of this program:
http://www.gtoal.com/wordgames/schulte-crossword/crossword.cpp

I didn't use any ideas in that code since it is using a library that I didn't even look at. Also, it's generating a "real" crossword with the words crossing each other on pretty much all of their letters. It would be interesting to see how that works.

But to generate a wordlist from it, just download and save that file, then run this on it to generate a file with just the words (although often more than one per line).

#include <iostream>
#include <fstream>
using namespace std;

int main() {
    ifstream in("crossword.cpp");
    ofstream out("wordlist.txt");

    string line;
    while (getline(in, line) && line != "const char* w_1[] = {") ;

    while (getline(in, line)) {
        if (line == "};") {
            getline(in, line);
            if (line == "// words specification") break;
            getline(in, line);
            getline(in, line);
        }
        for (auto ch: line) if (ch != '"' && ch != ',') out << ch;
        out << '\n';
    }
}

[nuderobmonkey]

Easy to understand was your code not, but I enjoyed thinking me through your code, letting the code speak for itself :-)
But the lack of good and sufficient comments is a habit seen by many (most?) hobby coders.

It's not needed to grab the words from your linked cpp file. I found a pure word list here:
https://github.com/dwyl/english-words

I use the txt file extracted from words_alpha.zip.

I tried to understand the sourcecode from the cpp file, but as you mentioned, this is only an excerpt of the whole. But the good thing is, if that guy was able to solve this issue, then there must exist at least one solution how to solve it. And I'm sure we will find some by our own :-)

[dhayden]

In emplaceWord, lines 73-78: The else matches the wrong if.

You have try/catch blocks all over but I don't see you throwing exceptions anywhere. I guess these are to catch out of bounds exceptions and that's why you're using at() instead of []

You can shorten the code by setting dx=1, dy=0 when moving horizontally, or dx=0, dy=1 when moving vertically.

#include <iostream>
#include <vector>
#include <fstream>
#include <random>
#include <stdexcept>

/* Holds its coordinates and a 'weight'.
 * If the word doesn't fit in the grid, weight is -1.
 * If the word fit, but there are no intersections with characters of other words, weight is 0.
 * If the word fit, and there are intersections with characters of other words, weight is the
 * sum of all intersected characters.
 */
struct Weight
{
    int x;   // column
    int y;   // row
    int wt;  // weight 
    Weight(int xx=0, int yy=0, int ww=0)
    : x{xx}, y{yy}, wt{ww}
    {}
};

/* The crossword puzzle generator class :-)
 * Its grid at each border side is at each one field broader than its 'box' inside. That's for
 * easier testing the borders of the words.
 */
class Cwg
{
public:
    Cwg( int width, int height );
    Cwg();
    
    bool emplaceWord( const std::string & word, bool horizontally );

private:
    Weight highestWeight( const std::string & word, int dx, int dy ) const;
    Weight doWeight( const std::string & word, int width, int height,
		     int dx, int dy ) const;
    
    // short-hand for the width and height
    unsigned width() const {return m_grid[0].size(); }
    unsigned height() const {return m_grid.size(); }
    
    std::vector<std::vector<char>> m_grid;
    friend std::ostream & operator<<( std::ostream &, const Cwg & );
};

Cwg::Cwg( int width, int height )
{
    if( width < 3 ) width = 3;
    if( height < 3) height = 3;

    // Consider that the 'effective' room is width x height.
    std::vector<char> row(width, '.');
    for( int h = 0; h < height; ++h )
    {
        m_grid.push_back(row);
    }
}
Cwg::Cwg() : Cwg{16,16} {}

// Set dx and dy to increment one position horizontally or
// vertically, depending on horizontal
void setDeltas(bool horizontal, int &dx, int &dy)
{
    if (horizontal) {
	dx = 1;
	dy = 0;
    } else {
	dx = 0;
	dy = 1;
    }
}

/* This method emplaces a word on the grid depending on the return value of Cwg::highestWeight().
 * The word will positioned at the coordinates of that Weight object.
 * If no position could found, the method returns false, otherwise true.
 *
 * See also Cwg::doWeight()
 */
bool 
Cwg::emplaceWord( const std::string & word, bool horizontally = true )
{
    int dx, dy;
    setDeltas(horizontally, dx, dy);
    // check that the word is not too long for the grid
    if (word.length()*dx > width()-2 || word.length()*dy > height()-2) {
	return false;
    }
            
    Weight weight = highestWeight( word, dx, dy);
    //std::cerr << word << ':' << '(' << weight.x << ',' << weight.y << ','
    //          << weight.wt << ')'<< '\n';
    if( weight.wt == -1 )
        return false;   // word doesn't match within the grid

    // Place it
    // std::cout << "Emplace " << word << ' '
    // << (horizontally ? "horizontal" : "vertical")
    // << " at " << weight.x+1 << ',' << weight.y+1 << '\n';
    for( unsigned p = 0; p < word.length(); ++p) {
	m_grid[weight.y][weight.x] = word[p];
	weight.x += dx;
	weight.y += dy;
    }
    
    //std::cerr << *this << '\n';
    return true;
}

/* This method returns the position for a word at the grid with the highest weight.
 * See Cwg::doWeight()
 *
 * Consider that the the there is a border of 1 field at each side of the grid.
 */
Weight 
Cwg::highestWeight( const std::string & word, int dx, int dy) const
{
    Weight weight(1,1,-1);

    for( unsigned h = 1; h < height() - dy*word.size() - 1; ++h ) {
	for( unsigned w = 1; w < width() - dx*word.size() - 1; ++w ) {
	    Weight tmpWeight = doWeight( word, w, h, dx, dy);
	    if( tmpWeight.wt > weight.wt ) {
		weight = tmpWeight;
	    }
	}
    }

    //std::cerr << "x("<< weight.x <<','<< weight.y <<','<< weight.wt <<')';
    return weight;
}
                

/* This method tests if a word matches within a distinct grid position.
 * If the word fits into the position, it returns by default a weight of 0.
 * For each matching intersection with another word the weight increases by 1.
 * If the word doesn't match at the position, the weight gets -1.
 */
Weight 
Cwg::doWeight( const std::string & word, int width, int height,
	       int dx, int dy) const
{
    // Each word needs at minimum a distance by one field in each direction to its neighbours.
     
    Weight weight(width,height,0);  // Needs to be 0 weighted!
    
    // Are there blank spaces before and after the word?
    if (m_grid[height-dy][width-dx] != '.' ||
	m_grid[height+dy*word.size()][width+dx*word.size()] != '.') {
	weight.wt = -1;
	//	std::cout << "Can't place at " << width+1 << "," << height+1
	// << ": No blank before or after\n";
	return weight;
    }
	
    int oh=height, ow = width;
    for( unsigned p = 0; p < word.length(); ++p, height += dy, width += dx ) {
            // test the place as such
	char g = m_grid[height][width]; // shorthand
	if( word[p] == g) {
	    // It matches
	    ++weight.wt;
	    continue;
	} else if( g != '.') {
	    // That space is occupied. Technically the
	    // comparison below will catch this case
	    // also, but what the heck.
	    weight.wt = -1;
	    // std::cout << "Can't place " << word << ' ' << p
	    // << " at " << ow+1 << "," << oh+1
	    // << ": " << width+1 << "," << height+1
	    // << " is " << g << " instead of " << word[p] << '\n';
	    break;
	} else if (m_grid[height+dx][width] != '.' ||
		   m_grid[height][width+dy] != '.' ||
		   m_grid[height-dx][width] != '.' ||
		   m_grid[height][width-dy] != '.') {
	    // neighboring cell is occupied
	    // std::cout << "Can't place at " << ow+1 << "," << oh+1
	    // << ": adjacent space is occupied\n";
	    weight.wt = -1;
	    break;
	}
    }
    //std::cerr << '('<<weight.x<<','<<weight.y<<','<<weight.wt<<')';  // correct
    return weight;
}
 
/* Overloads operator<< at std::ostream for << the grid.
 */
std::ostream & operator<<( std::ostream & os, const Cwg & cwg )
{
    for( const auto & row : cwg.m_grid ){
        for( const char c : row )
            os << ' ' << c;
        os <<  '\n';
    }
    return os;
}

// for debugging proposals
std::vector<std::string> dictionary = { "apache", "anchor", "banana", "beaver", "bear", "bussard",
"chocolate", "driver", "elephant", "eagle", "fog", "gear", "agony", "host", "harrassment",
"ice", "icebear", "bicycle", "rotten", "dread", "loo", "christmas", "handle", "theatre", "solvent",
"mouse", "rabbit", "dere", "sailor", "craftsman", "hooligan", "ananas", "cherry", "cranberry" };
 
int main( int argc, char * argv[] )
{   
    // The file handling:
    
    std::string dictName = "dictionary.txt";
    if( argc > 1 ) dictName = argv[2];
    std::ifstream ifile( dictName );
    if( !ifile ) {
        std::cerr << "File '" << dictName << "'could't opened!\n";
        return 1;
    }
    std::vector<std::string> dictionary;
    std::string tmp;
    while ( ifile >> tmp ) {
	for (auto &c : tmp) {
	    c = std::toupper(c);
	}
	dictionary.push_back( tmp );
    }

    std::default_random_engine eng( std::random_device{}() );
    std::uniform_int_distribution<> dist( 0, dictionary.size()-1 );


    // The crossword puzzle generator in action:

    Cwg cwg{20,20};
 
    for( int i = 0; i < 100; ++i )
    {
        std::string hor = dictionary[ dist(eng) ];
        std::string vert = dictionary[ dist(eng) ];
        cwg.emplaceWord(hor,true);
        cwg.emplaceWord(vert,false);
    }

    std::cout << cwg << '\n';
}

(output in next post)

[dhayden]

Output from previous post:

. . . . . . . . . . . . . . . . . . . .
 . F O G . R . C H R I S T M A S . B . .
 . . . . L O O . A . . . . O . . . E . .
 . . H . . T . . N . . . . U . D . A . .
 . . A . . T . . D E R E . S . E . R . .
 . D R I V E R . L . . . G E A R . . B .
 . . R . . N . . E . . . . . . E . . U .
 . . A . B . S . . A N A N A S . . . S .
 . . S . A G O N Y . . . . . . R . . S .
 . . S . N . L . . H O O L I G A N . A .
 . . M . A . V . . . . . . . . B . . R .
 . . E . N . E . R O T T E N . B . . D .
 . . N . A . N . . . . . . . . I . A . .
 . . T . . . T . H O S T . D . T . N . .
 . . . . . . . . . . . . . R . . . C . .
 . H A R R A S S M E N T . E . I . H . .
 . . . . . . . . . . . . . A . C . O . .
 . C R A F T S M A N . . . D . E . R . .
 . . . . . . . . . . I C E . . . . . . .
 . . . . . . . . . . . . . . . . . . . .

[nuderobmonkey]

Thank you Dave for optimizing the code. You're right, I used the try-catch blocks because I had some hard to detect out of range errors when I tested my stuff. That's because I have difficulties in thinking in an arithmetic manner. In the end, I was not sure if I should clean them out or if it would be a good thing letting for others the possibility of getting somehow an insight of my debugging.

[nuderobmonkey]

I opened a github repo for which holds at time Daves and dutchs solutions.

https://github.com/NicoSchumann/crossword_puzzle_generator

[dutch]

Here's a version with classes and a little explication at the top.

/*
The algorithm keeps track of the row/col position (and horz/vert direction) of
the letters on the grid. Knowing the horz/vert direction means we only need to
test the opposite direction when adding a word crossing that letter.

An initial word is placed at position 0,0 (randomly horz or vert).
Then random words are placed, connected to already-placed words, until MaxTries
words cannot be placed, at which point it gives up.

To place a word, it's letters are scanned and looked up in the letter table.
Then those positions are tested to see if the word can be placed there.
When a letter in the letter table is "double-crossed", it is removed from the
table since it can't be used again.

Problems:

This may leave some empty spots, although it seems to work pretty well.
To fill empty spots, the grid could be scanned for them, a new seed word
could be placed and the algorithm restarted.

It might also be good to prune the letter table a little more since even some
letters which obviously can't be crossed (due to close letters on either side)
are in the list.
*/

#include <algorithm>
#include <exception>
#include <fstream>
#include <iostream>
#include <random>
#include <vector>
#include <cctype>
using namespace std;

const int ShortestWord = 3, LongestWord = 8;
const int MaxTries = 10000;
const string WordFile  = "wordlist.txt";
const string WordFile2 = "wordlist2.txt"; // selected with -2 option

// Global Random Engine
default_random_engine RndEngine{ random_device{}() };

class WordList {
    using Dist = uniform_int_distribution<int>;
public:
    WordList(const string& filename) {
        ifstream in(filename);
        if (!in) throw runtime_error("Cannot open " + filename);
        for (string word; in >> word; )
            if (word.size() >= ShortestWord && word.size() <= LongestWord)
                m_words.push_back(word);
        m_dist.param(Dist::param_type(0, m_words.size() - 1));
    }
    string rnd_word() const {
        auto& d = m_dist;
        return m_words[const_cast<Dist&>(d)(RndEngine)];
    }
private:
    vector<string> m_words;
    Dist m_dist;
};

class Dir {
public:
    enum DirT { Horz, Vert };
    static Dir rnd_dir() {
        static uniform_int_distribution<> distDir(0, 1);
        return Dir(distDir(RndEngine) ? Horz : Vert);
    }
    Dir(DirT dir) : m_dir(dir) { }
    bool horz() const { return m_dir == Horz; }
    bool vert() const { return m_dir == Vert; }
    Dir operator!() const { return m_dir == Horz ? Vert : Horz; }
    friend ostream& operator<<(ostream& out, Dir dir) {
        return out << (dir.m_dir == Horz ? 'H' : 'V');
    }
private:
    DirT m_dir;
};

struct Point {
    int row, col;
    Dir dir;
    Point(int r, int c, Dir d) : row(r), col(c), dir(d) { }
    bool operator==(const Point& p) const
         { return row == p.row && col == p.col; }
    bool operator!=(const Point& p) const { return !(*this == p); }
};

class Letter {
public:
    using iterator = vector<Point>::iterator;

    void push_back(Point p) { pos.push_back(p); }
    auto begin() { return pos.begin(); }
    auto begin() const { return pos.begin(); }
    auto end() { return pos.end(); }
    auto end() const { return pos.end(); }
    void erase(iterator p) { pos.erase(p); }
private:
    vector<Point> pos;
};

class Letters {
public:
    Letter& operator[](char ch) {
        int i = toupper(ch) - 'A';
        if (i < 0 || i > 25) throw invalid_argument("Bad index");
        return m_letters[i];
    }
    const Letter& operator[](char ch) const {
        return (*const_cast<Letters*>(this))[ch];
    }
    void dump() const {
        for (char ch = 'A'; ch <= 'Z'; ++ch) {
            cout << ch << ": ";
            const auto& letter = (*this)[ch];
            for (const auto& p: letter)
                cout << p.row << ',' << p.col << ',' << p.dir << "  ";
            cout << '\n';
        }
    }
private:
    Letter m_letters[26];
};

class Grid {
    void add_word(const string& word, int w, Point cross_pnt);
    void place_initial_word(const string& word);
    bool can_place(const string& word, int w, const Letter::iterator p);
    bool place_crossing_word(const string& word);

public:
    static constexpr char Empty = '.';

    Grid(int size) : m_size(size), m_grid(new char[size * size])
        { fill((char*)m_grid, (char*)m_grid + size * size, Empty); }
    Grid(const Grid&) = delete;
    ~Grid() { delete[] m_grid; }

    char* operator[](size_t row) { return &m_grid[row * m_size]; }
    char& operator[](const Point& p) { return m_grid[p.row * m_size + p.col]; }
    int size() const { return m_size; }
    bool empty(int r, int c) const { return m_grid[r * m_size + c] == Empty; }

    void generate(const WordList& wordlist);
    void print() const;
private:
    int   m_size = 0;
    char *m_grid = nullptr;
    Letters m_letters;
};

constexpr char Grid::Empty;

void Grid::print() const {
    for (int r = 0; r < m_size; ++r) {
        for (int c = 0; c < m_size; ++c) {
            char ch = toupper(m_grid[r * m_size + c]);
            cout << (ch == Empty ? ' ' : ch) << ' ';
        }
        cout << '\n';
    }
}

void Grid::add_word(const string& word, int w, Point cross_pnt) {
    Point pnt(cross_pnt);
    pnt.dir = !pnt.dir;
    int& colrow = (pnt.dir.horz() ? pnt.col : pnt.row);
    colrow -= w;
    int start = colrow;
    for (unsigned pos = start, w = 0; pos < start + word.size(); ++pos) {
        char ch = word[w++];
        auto& letter = m_letters[ch];
        colrow = pos; // set pnt.col or pnt.row to pos
        if (pnt != cross_pnt) letter.push_back(pnt);
        (*this)[pnt] = ch;
    }
}

void Grid::place_initial_word(const string& word) {
    uniform_int_distribution<> distDir(0, 1);
    auto& letter = m_letters[word[0]];
    Point cross_pnt(0, 0, Dir::rnd_dir());
    letter.push_back(cross_pnt);
    add_word(word, 0, cross_pnt);
}

bool Grid::can_place(const string& word, int w, const Letter::iterator p) {
    int r = p->row, c = p->col;
    Dir dir = !p->dir;
    const int size = word.size();
    if (dir.horz()) {
        c -= w;
        if (c < 0 || c + size > m_size
         || (c > 0             && !empty(r, c - 1))
         || (c + size < m_size && !empty(r, c + size)))
            return false;
        for (int i = 0; i < size; ++i, ++c) {
            if (i == w) continue;
            if (                   !empty(r    , c)
             || (r > 0          && !empty(r - 1, c))
             || (r < m_size - 1 && !empty(r + 1, c)))
                return false;
        }
    }
    else {
        r -= w;
        if (r < 0 || r + size > m_size
         || (r > 0             && !empty(r - 1,    c))
         || (r + size < m_size && !empty(r + size, c)))
            return false;
        for (int i = 0; i < size; ++i, ++r) {
            if (i == w) continue;
            if (                   !empty(r, c    )
             || (c > 0          && !empty(r, c - 1))
             || (c < m_size - 1 && !empty(r, c + 1)))
                return false;
        }
    }
    return true;
}

bool Grid::place_crossing_word(const string& word) {
    for (unsigned w = 0; w < word.size(); ++w) {
        auto& letter = m_letters[word[w]];
        for (auto p = letter.begin(); p != letter.end(); ++p)
            if (can_place(word, w, p)) {
                Point cross_pnt(*p);
                letter.erase(p); // erase "double-crossed" letters from list
                add_word(word, w, cross_pnt);
                return true;
            }
    }
    return false;
}

void Grid::generate(const WordList& wordlist) {
    place_initial_word(wordlist.rnd_word());
    for (int i = 0; i < MaxTries; ++i) // give up after this many tries
        if (place_crossing_word(wordlist.rnd_word()))
            i = 0; // reset count whenever a word is placed
}

int main(int argc, char **argv) {
    const auto& wordFile =
        (argc == 2 && string(argv[1]) == "-2" ? WordFile2 : WordFile);
    Grid grid(30);
    grid.generate(WordList(wordFile));
    grid.print();
}

[dutch]

Here's that other word list I mentioned.
It's simpler than the one you are using (about 1/4 the size).
It's interesting to go back and forth between them.
https://filebin.net/acnqa52e1hgcjw9a

[nuderobmonkey]

This program adds a header which holds the indices of the start positions of words of a distinct length to a dictionary.

#include <iostream>
#include <fstream>
#include <vector>
#include <utility>

void print_help()
{
    std::cout
    << "The program needs as argument a dictionary with alphabetic words.\n"
    << "The program sorts all words by size and converts all characters to "
    << "uppercase and writes an index header to the begin of the output file:\n"
    << " xx        : header size\n"
    << " xx xx ... : word length and index to the first word of such size.\n"
    << "!The indices don't include the header's size, so it must handled as offset.\n"
    ;
}

int main( int argc, char *argv[] )
{
    std::ifstream ifs;
    std::ofstream ofs;
    std::string filename;

    if( argc <= 1 ) {
        print_help();
        return 1;
    }
    else {
        filename = argv[1];
    }
    ifs.open( filename );
    if( ! ifs ) {
        std::cout << "Dictionary file couldn't opened!\n";
        return 2;
    }
    ofs.open( std::string("idx_") + filename );
    if( ! ofs ) {
        std::cout << "Output file couldn't opened!\n";
        return 3;
    }

    // sort the words by length
    std::vector<std::vector<std::string>> words_table(128);
    for( std::string word; ifs >> word; )
    {
        if( word.size() > 32) continue;
        for( const auto chr : word ) {
            if( ! std::isalpha(chr) ) {
                std::cerr << "The dictionary contains non-alphabetic stuff!\n";
                return 4;
            }
        }
        words_table[word.length() - 1].push_back( word );
    }

    // generate indices for words lengt and start position in output file
    std::vector<std::pair<int,int>> header;
    for( int i = 0, count = 0; i < words_table.size(); ++i )
    {
        if( words_table[i].size() == 0 ) continue;
        header.push_back( std::make_pair( i+1, count ) );
        count += words_table[i].size();
    }
       // write the header
    ofs << header.size()+1 << '\n';
    for( const auto & pair : header ) {
        ofs << pair.first <<' '<< pair.second << '\n';
    }

    // write the words
    for( auto & word_list : words_table) {
        if( word_list.size() == 0 ) continue;
        for( auto & word : word_list) {
            for( auto & chr : word ) {
                chr = std::toupper( chr );
            }
            ofs << word << '\n';
        }
    }
}

And I added your own code to the repo, dutch.

[nuderobmonkey]

At the linking process at your last posted code, I get at building this linker error and don't know how to solve it:

/usr/bin/ld: /tmp/ccp5kUq3.o: in function `Grid::Grid(int)':
crossword_puzzle_generator_2_dutch.cpp:(.text._ZN4GridC2Ei[_ZN4GridC5Ei]+0x67): undefined reference to `Grid::Empty'

[dutch]

You're right. Pre-C++17 has a problem with the code, although I'm not sure what the problem is. To fix it for now just replace all Empty (case-sensitive) with '.'. It's only in a couple of places near it's definition. And remove the line declaring Empty.

I fixed it in the code above.

[nuderobmonkey]

Thanks for that hint, I use now the flag -std=c++17 at compiling.

[dutch]

Here's a minimal example of the problem with C++14 that works in C++17.
It's the std::fill call that doesn't work, but (char)Empty works.
The use of Empty in func() works just fine.
Apparently something was changed from 14 to 17, but constexpr was not added to std::fill until C++20 (according to https://en.cppreference.com/w/cpp/algorithm/fill ), although I don't see why that would be necessary.

#include <iostream>
#include <algorithm>

class Grid {
    char a[10];
public:
    static constexpr char Empty = '.';
    Grid() { std::fill(a, a + 10, Empty); }  // (char)Empty works in C++14 (clang)
    void func() { std::cout << Empty << '\n'; }
};

int main() {
    Grid g;
    g.func();
}

[mbozzi]

The problem is that std::fill's third parameter is a reference. Binding a variable to a reference constitutes a kind of usage (odr-usage) which requires that the variable is defined.

In C++17 static constexpr data members are implicitly inline. An inline variable can be defined in any number of translation units, and therefore a single out-of-class definition isn't needed to satisfy the linker.