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];
106 if (y != (grid->size - 1))
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 /* For the 4x4 grid any word of length 3 or more counts.
148 * For the 5x5 grid any word of length 4 or more counts.
150 if (strlen (word) >= (grid->size - 1) &&
151 DICT_ENTRY_IS_WORD (dict_cursor_resolve (dict_cursor)))
153 dict_add_word (grid->results, word);
156 for (dy = -1; dy <= 1; dy++)
157 for (dx = -1; dx <= 1; dx++)
158 grid_enumerate (grid, x + dx, y + dy, seen, word, dict_cursor);
161 word [strlen (word) - 1] = '\0';
162 word [strlen (word) - 1] = '\0';
166 grid_solve (grid_t *grid, dict_t *dict, dict_t *solution)
172 grid->results = solution;
174 memset (word, '\0', 18);
176 for (y = 0; y < grid->size; y++)
177 for (x = 0; x < grid->size; x++)
178 grid_enumerate (grid, x, y, seen, word, dict_root (dict));