2 * Copyright © 2006 Carl Worth
4 * This program is free software; you can redistribute it and\/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2, or (at your option)
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software Foundation,
16 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
25 #define GRID_CUBES_MAX (GRID_SIZE_MAX * GRID_SIZE_MAX)
28 "aaeeng", "abbjoo", "achops", "affkps",
29 "aoottw", "cimotu", "deilrx", "delrvy",
30 "distty", "eeghnw", "eeinsu", "ehrtvw",
31 "eiosst", "elrtty", "himnqu", "hlnnrz"
35 "aaafrs", "aaeeee", "aafirs", "adennn", "aeeeem",
36 "aeegmu", "aegmnn", "afirsy", "bjkqxz", "ccnstw",
37 "ceiilt", "ceilpt", "ceipst", "ddlnor", "dhhlor",
38 "dhhnot", "dhlnor", "eiiitt", "emottt", "ensssu",
39 "fiprsy", "gorrvw", "hiprry", "nootuw", "ooottu"
43 rand_within (int num_values)
45 return (int) ((double) num_values * (rand() / (RAND_MAX + 1.0)));
49 shuffle (int *array, int length)
53 for (i = 0; i < length; i++)
55 r = i + rand_within (length - i);
63 grid_init (grid_t *grid, int size)
66 int cubes[GRID_CUBES_MAX];
70 assert (size == 4 || size == 5);
73 num_cubes = size * size;
76 cubes_source = cubes4;
78 cubes_source = cubes5;
80 for (i = 0; i < num_cubes; i++)
82 shuffle (cubes, num_cubes);
84 for (i = 0; i < num_cubes; i++)
85 grid->letters[i / grid->size][i % grid->size] =
86 cubes_source[cubes[i]][rand_within(6)];
90 grid_set_letters (grid_t *grid,
94 int num_cubes = grid->size * grid->size;
97 if (strlen (letters) != num_cubes) {
98 fprintf (stderr, "Error: Invalid string for %dx%d grid. Expected %d letters: %s\n",
99 grid->size, grid->size, num_cubes, letters);
103 for (i = 0; i < num_cubes; i++) {
104 letter = tolower (letters[i]);
105 if (letter < 'a' || letter > 'z') {
106 fprintf (stderr, "Error: Invalid character '%c' in letters: %s\n",
107 letters[i], letters);
110 grid->letters[i / grid->size][i % grid->size] = letter;
115 grid_string (grid_t *grid)
119 char *s = grid->string;
121 for (y = 0; y < grid->size; y++) {
122 for (x = 0; x < grid->size; x++) {
123 c = grid->letters[y][x];
131 if (y != (grid->size - 1))
139 #define SEEN_BIT(x, y) (1 << ((grid->size)*(y)+(x)))
141 grid_enumerate (grid_t *grid,
146 dict_cursor_t dict_cursor)
151 if (dict_cursor == DICT_CURSOR_NIL)
154 if (x < 0 || x >= grid->size ||
155 y < 0 || y >= grid->size ||
156 seen & SEEN_BIT (x, y))
161 seen |= SEEN_BIT (x, y);
163 c = grid->letters[y][x];
164 word[strlen (word)] = c;
165 dict_cursor = dict_cursor_next (dict_cursor, c);
168 word[strlen (word)] = 'u';
169 dict_cursor = dict_cursor_next (dict_cursor, 'u');
172 /* For the 4x4 grid any word of length 3 or more counts.
173 * For the 5x5 grid any word of length 4 or more counts.
175 if (strlen (word) >= (grid->size - 1) &&
176 DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
178 dict_add_word (grid->results, word);
181 for (dy = -1; dy <= 1; dy++)
182 for (dx = -1; dx <= 1; dx++)
183 grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
186 word [strlen (word) - 1] = '\0';
187 word [strlen (word) - 1] = '\0';
191 grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
197 grid->results = solution;
199 memset (word, '\0', 18);
201 for (y = 0; y < grid->size; y++)
202 for (x = 0; x < grid->size; x++)
203 grid_enumerate (grid, x, y, seen, word, dict_root (dict));