crossword puzzle generator

Pages: 12
dutch (2548)
Thanks @mbozzi, I just finished reading this:

https://stackoverflow.com/questions/8016780/undefined-reference-to-static-constexpr-char
See "C++17 introduces inline variables"

So in C++14, even though it's constexpr, it still needs a (empty) definition outside the class.

 
 
constexpr char Grid::Empty;

I've modified the above code to be C++14 compliant. (No need to require C++17 for that one little thing.)
nuderobmonkey (640)
Here is another try, my goal was, to generate a completely closed crossword fields, but at time I fail still in that. My approach is randomly based brute-force. So for getting a resolution like the below, I test for 10.000.000 combinations of words.
 R O T U L A D
     U   A G A
 B O R E D O M
 B A N D A N A
     E   N I G
 A R R O U S E
 C H A R M E D
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <string>
#include <random>
#include <exception>

std::default_random_engine rng( std::random_device{}() );
std::uniform_int_distribution<> dist;
constexpr int GRID_SIZE = 7; // height and width
using Grid = std::array<std::array<char,GRID_SIZE>,GRID_SIZE>;
constexpr char EMPTY = '.';
enum class Direction { Horz, Vert };
struct Pos { int col, row; };

void reset_grid( Grid & grid )
{ for( auto & row : grid ) for( auto & cell : row) cell = EMPTY; }

std::ostream & operator<<( std::ostream & os, const Grid & grid)
{
    for( const auto & row : grid ) {
        for( const auto cell : row)
            os << ' ' << (cell == EMPTY ? ' ' : (char)std::toupper(cell));
        os << '\n';
    }
    return os;
}
bool is_grid_filled( const Grid & grid )
{
    for(const auto& row : grid) for(const char cell : row) if(cell == EMPTY) return false;
    return true;
}
int fill_count( const Grid & grid )
{
    int count = 0;
    for(const auto & row : grid) for(const char cell : row) if(cell != EMPTY) ++count;
    return count;
}

/* Returns the matching position of a word in the grid. If there is no matching position
 * available or if the matching letters within the grid are smaller than
 * needed_matching_letters, the function returns a at pos.col a value of -1.
 */
Pos can_place_word
(
    const std::string & word
  , const int needed_matching_letters
  , const Direction dir
  , const Grid & grid
){
    bool can_place;  // flags whether a word matches the constraints
    int matching_letters = 0;
    Pos pos;

    if( dir == Direction::Horz ){
        for( int offset_row = 0; offset_row < grid.size(); ++offset_row){
            for(
                    int offset_col = 0
                    ; offset_col <= grid[0].size() - word.length()
                    ; ++offset_col
            ){
                // tests for a distinct position
                can_place = true;
                for( int word_idx = 0; word_idx < word.length(); ++word_idx){
                    char letter_in_grid = grid[ offset_row ][ offset_col + word_idx ];
                    if( letter_in_grid != EMPTY && letter_in_grid != word[ word_idx ]){
                        can_place = false;
                        break;   // ends the test for this position
                    }
                    else if( letter_in_grid == word[ word_idx ] )
                        ++matching_letters;
                }
                if( can_place == true ) { // the word fits at grid position
                    pos.col = offset_col;
                    pos.row = offset_row;
                    goto cpw_end;   // a matching position was found and set
                }
            }
        }
    } else { // direction must be vertical
        for( int offset_row = 0; offset_row <= grid.size() - word.length(); ++offset_row) {
            for( int offset_col = 0; offset_col < grid[0].size(); ++offset_col) {
                can_place = true;
                for( int word_idx = 0; word_idx < word.length(); ++word_idx) {
                    char letter_in_grid = grid[ offset_row + word_idx ][ offset_col];
                    if( letter_in_grid != EMPTY && letter_in_grid != word[ word_idx ]){
                        can_place = false;
                        break;
                    }
                    else if( letter_in_grid == word[ word_idx ] )
                        ++matching_letters;
                }
                if( can_place == true ){
                    pos.col = offset_col;
                    pos.row = offset_row;
                    goto cpw_end;
                }
            }
        }
    }
cpw_end:
    if( can_place == false || matching_letters < needed_matching_letters ) pos.col = -1;
    return pos;
}
void place_word
(
    const std::string & word
  , const Pos & pos
  , const Direction dir
  , Grid & grid
){
    if( dir == Direction::Horz )
        for( int i = 0; i < word.length(); ++i )
            grid[ pos.row ][ pos.col + i ] = word[i];
    else
        for( int i = 0; i < word.length(); ++i )
            grid[ pos.row + i ][ pos.col ] = word[i];
}

void read_wordlist
(
    const std::string & file_name
  , const int word_length
  , std::vector<std::string> & word_list
) {
    std::ifstream ifs( file_name );
    if( ! ifs ) throw std::runtime_error(
            "read_wordlist(): Dictionary " + file_name + " couldn't opened!"
        );

    word_list.clear();
    for( std::string word; ifs >> word; )
        if( word.length() == word_length) word_list.push_back( word );
    dist.param( std::uniform_int_distribution<>::param_type( 0, word_list.size() - 1) );
}

void fill_grid(
    const std::vector<std::string> & word_list
  , Grid & grid
  , const int count // no of tries
){
    Direction dir = Direction::Horz;
    constexpr int needed_matching_rows = grid.size() - 1;
    const int needed_matching_cols = grid[0].size() - 1;

    place_word( word_list[dist(rng)], Pos{0,0}, dir, grid );
    dir = Direction::Vert;

    for( int i = 1, rows_to_match = 1, cols_to_match = 0
              ; i < count && (rows_to_match < needed_matching_rows
                    || cols_to_match < needed_matching_cols)
              ; ++i
    ) {
        std::string word = word_list[ dist(rng) ];
        if( dir == Direction::Horz ){
            Pos pos = can_place_word( word, cols_to_match, dir, grid );
            if( pos.col == -1 ) continue;
            ++ rows_to_match;
            place_word( word, pos, dir, grid );
            dir = Direction::Vert;
        } else {
            Pos pos = can_place_word( word, rows_to_match, dir, grid );
            if( pos.col == -1 ) continue;
            ++ cols_to_match;
            place_word( word, pos, dir, grid );
            dir = Direction::Horz;
        }
    }
}

int main( int argc, char * argv[] )
{
    std::string file_name;
    if( argc > 1) file_name = argv[1];
    else file_name = "dictonary.txt";
    std::vector<std::string> word_list;
    read_wordlist( file_name, GRID_SIZE, word_list );
    Grid grid, best;
    int best_fillcount = 0;
    for( int i = 0; i < 10000; ++i ) {
        reset_grid( grid );
        fill_grid( word_list, grid, 1000 );
        int grid_fillcount = fill_count( grid );
        if( grid_fillcount > best_fillcount ) {
            best = grid; best_fillcount = grid_fillcount;
       }
    }
    std::cout << best;
}


My next goal is, coming a little bit off from brute force approach and trying to filter out matching words for narrowing down the choice.
Last edited on
nuderobmonkey (640)
Here a program version that pre-filters matching candidates. But it needs to create much of the time lists of filtered words. This seems to make the code sow.


 A B A T E R S
 M A C O N N E
 O R A N G E R
 E R R A T I C
 B I A L L Y L
 I O R L      
 D S I Y      

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
/* This version of my crossword puzzle generator works by filtering all matching words from
a word list. The crossword field is at time quadratic.
*/
#include <array>
#include <exception>
#include <fstream>
#include <iostream>
#include <random>
#include <string>
#include <vector>

std::default_random_engine rng( std::random_device{}() );
std::uniform_int_distribution<> dist;
constexpr int GRID_SIZE = 7; // height and width
using Grid = std::array<std::array<char,GRID_SIZE>,GRID_SIZE>;
constexpr char EMPTY = '.';  // mark of empty cells
enum class Direction { Horz, Vert };
struct Pos { int col, row; };

void reset_grid( Grid & grid )
{ for( auto & row : grid ) for( auto & cell : row) cell = EMPTY; }

/* Writes the grid. */
std::ostream & operator<<( std::ostream & os, const Grid & grid){
    for( const auto & row : grid ) {
        for( const char cell : row)
            os << ' ' << (cell == EMPTY ? ' ' : static_cast<char>(std::toupper(cell)));
        os << '\n';
    }
    return os;
}
/* Makes a sieve for a distinct row or column of the grid.
If Direction dir == Direction:Horz, 'line' is the distinct row, otherwise the column.
If a sieve could made, it returns true. If no sieve could made, it returns false.
That's the case if there is no free cell in the grid at the distinct row (or colum).
*/
bool make_sieve_line(
    std::string & sieve
  , const int line  // could be a row-no. or column-no.
  , const Direction dir
  , const Grid & grid
){
    sieve.clear();
    bool has_blank = false;

    if ( dir == Direction::Horz ) {
        for( int col = 0; col < grid[0].size(); ++ col ) {
            sieve.push_back( grid[line][col] );
            if( grid[line][col] == EMPTY ) has_blank = true;
        }
    } else {  // dir == Direction::Vert
        for( int row = 0; row < grid.size(); ++ row) {
            sieve.push_back( grid[row][line] );
            if( grid[row][line] == EMPTY ) has_blank = true;
        }
    }
    return has_blank ? true : false;
}
/* Filters all words of word_list by 'sieve'.
The resulting words will stored at 'result_list'.
*/
void do_sieve(
    const std::string & sieve
  , const std::vector<std::string> & word_list
  , std::vector<std::string *> & result_list
) {
    result_list.clear();

    for( const auto & word : word_list ){
        bool word_matches = true;
        for( int idx = 0; idx < word.length(); ++idx ) {
            if( sieve[idx] != EMPTY && word[idx] != sieve[idx] ){
                word_matches = false;
                break;
            }
        }
        if( word_matches ) result_list.push_back( const_cast<std::string *>(& word) );
    }
}
/* Counts how many letters are placed within the grid. */
int fillcount( const Grid & grid ){
    int count = 0;
    for(const auto & row : grid) for(const char cell : row) if(cell != EMPTY) ++count;
    return count;
}
/* Places a word inside of the grid */
void place_word(
    const std::string & word
  , const Pos & pos
  , const Direction dir
  , Grid & grid
){
    if( dir == Direction::Horz )
        for( int i = 0; i < word.length(); ++i )
            grid[ pos.row ][ pos.col + i ] = word[i];
    else
        for( int i = 0; i < word.length(); ++i )
            grid[ pos.row + i ][ pos.col ] = word[i];
}
/* Reads the words from file. */
void read_wordlist(
    const std::string & file_name
  , const int word_length
  , std::vector<std::string> & word_list
) {
    std::ifstream ifs( file_name );
    if( ! ifs ) {
        throw std::runtime_error(
            "read_wordlist(): Dictionary " + file_name + " couldn't opened!"
        );
    }
    word_list.clear();
    for( std::string word; ifs >> word; )
        if( word.length() == word_length) word_list.push_back( word );
    dist.param( std::uniform_int_distribution<>::param_type( 0, word_list.size() - 1) );
}

void fill_grid(
    std::vector<std::string> word_list
  , Grid & grid
){
    Direction dir = Direction::Horz;

    // The 1st word (randomly chosen) gets placed.
    place_word( word_list[ dist(rng) ], Pos{0,0}, dir, grid );

    // rc stands for row_or_column
    for( int rc = 0; rc < GRID_SIZE; )
    {
        dir = (dir == Direction::Vert ? Direction::Horz : Direction::Vert);
        std::string sieve;
        make_sieve_line( sieve, rc, dir, grid);
        std::vector<std::string *> sieved_list_p;
        do_sieve( sieve, word_list, sieved_list_p );
        if( sieved_list_p.size() == 0 )
            break;
        dist.param( std::uniform_int_distribution<int>::param_type(
                    0, sieved_list_p.size() - 1
        ) );
        std::string & word = *sieved_list_p[ dist(rng) ];
        Pos pos;
        if( dir == Direction::Vert ) {
            pos.row = 0; pos.col = rc;
            place_word( word, pos, dir, grid );
            ++ rc;
        } else { // dir == Direction::Horz
            pos.row = rc; pos.col = 0;
            place_word( word, pos, dir, grid );
        }
    }
}

int main( int argc, char * argv[] )
{
    std::string file_name;
    if( argc > 1) file_name = argv[1];
    else file_name = "dictonary.txt";
    std::vector<std::string> word_list;
    read_wordlist( file_name, GRID_SIZE, word_list );

    Grid grid, best;
    int best_fillcount = 0;
    for( int i = 0; i < 1000; ++i ) { // 1000 tries
        reset_grid( grid );
        fill_grid( word_list, grid);
        int grid_fillcount = fillcount( grid );
        if( grid_fillcount > best_fillcount ) {
            best = grid; best_fillcount = grid_fillcount;
       }
    }
    std::cout << best;
}
Topic archived. No new replies allowed.
Pages: 12