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_string (grid_t *grid)
94 char *s = grid->string;
96 for (y = 0; y < grid->size; y++) {
97 for (x = 0; x < grid->size; x++) {
98 c = grid->letters[y][x];
114 #define SEEN_BIT(x, y) (1 << ((grid->size)*(y)+(x)))
116 grid_enumerate (grid_t *grid,
121 dict_cursor_t dict_cursor)
126 if (dict_cursor == DICT_CURSOR_NIL)
129 if (x < 0 || x >= grid->size ||
130 y < 0 || y >= grid->size ||
131 seen & SEEN_BIT (x, y))
136 seen |= SEEN_BIT (x, y);
138 c = grid->letters[y][x];
139 word[strlen (word)] = c;
140 dict_cursor = dict_cursor_next (dict_cursor, c);
143 word[strlen (word)] = 'u';
144 dict_cursor = dict_cursor_next (dict_cursor, 'u');
147 if (strlen (word) > 2 &&
148 DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
150 dict_add_word (grid->results, word);
153 for (dy = -1; dy <= 1; dy++)
154 for (dx = -1; dx <= 1; dx++)
155 grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
158 word [strlen (word) - 1] = '\0';
159 word [strlen (word) - 1] = '\0';
163 grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
169 grid->results = solution;
171 memset (word, '\0', 18);
173 for (y = 0; y < grid->size; y++)
174 for (x = 0; x < grid->size; x++)
175 grid_enumerate (grid, x, y, seen, word, dict_root (dict));