diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/separate.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/separate.c | 861 |
1 files changed, 861 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/separate.c b/apps/plugins/puzzles/src/unfinished/separate.c new file mode 100644 index 0000000000..6ca07252ad --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/separate.c | |||
@@ -0,0 +1,861 @@ | |||
1 | /* | ||
2 | * separate.c: Implementation of `Block Puzzle', a Japanese-only | ||
3 | * Nikoli puzzle seen at | ||
4 | * http://www.nikoli.co.jp/ja/puzzles/block_puzzle/ | ||
5 | * | ||
6 | * It's difficult to be absolutely sure of the rules since online | ||
7 | * Japanese translators are so bad, but looking at the sample | ||
8 | * puzzle it seems fairly clear that the rules of this one are | ||
9 | * very simple. You have an mxn grid in which every square | ||
10 | * contains a letter, there are k distinct letters with k dividing | ||
11 | * mn, and every letter occurs the same number of times; your aim | ||
12 | * is to find a partition of the grid into disjoint k-ominoes such | ||
13 | * that each k-omino contains exactly one of each letter. | ||
14 | * | ||
15 | * (It may be that Nikoli always have m,n,k equal to one another. | ||
16 | * However, I don't see that that's critical to the puzzle; k|mn | ||
17 | * is the only really important constraint, and even that could | ||
18 | * probably be dispensed with if some squares were marked as | ||
19 | * unused.) | ||
20 | */ | ||
21 | |||
22 | /* | ||
23 | * Current status: only the solver/generator is yet written, and | ||
24 | * although working in principle it's _very_ slow. It generates | ||
25 | * 5x5n5 or 6x6n4 readily enough, 6x6n6 with a bit of effort, and | ||
26 | * 7x7n7 only with a serious strain. I haven't dared try it higher | ||
27 | * than that yet. | ||
28 | * | ||
29 | * One idea to speed it up is to implement more of the solver. | ||
30 | * Ideas I've so far had include: | ||
31 | * | ||
32 | * - Generalise the deduction currently expressed as `an | ||
33 | * undersized chain with only one direction to extend must take | ||
34 | * it'. More generally, the deduction should say `if all the | ||
35 | * possible k-ominoes containing a given chain also contain | ||
36 | * square x, then mark square x as part of that k-omino'. | ||
37 | * + For example, consider this case: | ||
38 | * | ||
39 | * a ? b This represents the top left of a board; the letters | ||
40 | * ? ? ? a,b,c do not represent the letters used in the puzzle, | ||
41 | * c ? ? but indicate that those three squares are known to be | ||
42 | * of different ominoes. Now if k >= 4, we can immediately | ||
43 | * deduce that the square midway between b and c belongs to the | ||
44 | * same omino as a, because there is no way we can make a 4-or- | ||
45 | * more-omino containing a which does not also contain that square. | ||
46 | * (Most easily seen by imagining cutting that square out of the | ||
47 | * grid; then, clearly, the omino containing a has only two | ||
48 | * squares to expand into, and needs at least three.) | ||
49 | * | ||
50 | * The key difficulty with this mode of reasoning is | ||
51 | * identifying such squares. I can't immediately think of a | ||
52 | * simple algorithm for finding them on a wholesale basis. | ||
53 | * | ||
54 | * - Bfs out from a chain looking for the letters it lacks. For | ||
55 | * example, in this situation (top three rows of a 7x7n7 grid): | ||
56 | * | ||
57 | * +-----------+-+ | ||
58 | * |E-A-F-B-C D|D| | ||
59 | * +------- || | ||
60 | * |E-C-G-D G|G E| | ||
61 | * +-+--- | | ||
62 | * |E|E G A B F A| | ||
63 | * | ||
64 | * In this situation we can be sure that the top left chain | ||
65 | * E-A-F-B-C does extend rightwards to the D, because there is | ||
66 | * no other D within reach of that chain. Note also that the | ||
67 | * bfs can skip squares which are known to belong to other | ||
68 | * ominoes than this one. | ||
69 | * | ||
70 | * (This deduction, I fear, should only be used in an | ||
71 | * emergency, because it relies on _all_ squares within range | ||
72 | * of the bfs having particular values and so using it during | ||
73 | * incremental generation rather nails down a lot of the grid.) | ||
74 | * | ||
75 | * It's conceivable that another thing we could do would be to | ||
76 | * increase the flexibility in the grid generator: instead of | ||
77 | * nailing down the _value_ of any square depended on, merely nail | ||
78 | * down its equivalence to other squares. Unfortunately this turns | ||
79 | * the letter-selection phase of generation into a general graph | ||
80 | * colouring problem (we must draw a graph with equivalence | ||
81 | * classes of squares as the vertices, and an edge between any two | ||
82 | * vertices representing equivalence classes which contain squares | ||
83 | * that share an omino, and then k-colour the result) and hence | ||
84 | * requires recursion, which bodes ill for something we're doing | ||
85 | * that many times per generation. | ||
86 | * | ||
87 | * I suppose a simple thing I could try would be tuning the retry | ||
88 | * count, just in case it's set too high or too low for efficient | ||
89 | * generation. | ||
90 | */ | ||
91 | |||
92 | #include <stdio.h> | ||
93 | #include <stdlib.h> | ||
94 | #include <string.h> | ||
95 | #include <assert.h> | ||
96 | #include <ctype.h> | ||
97 | #ifdef NO_TGMATH_H | ||
98 | # include <math.h> | ||
99 | #else | ||
100 | # include <tgmath.h> | ||
101 | #endif | ||
102 | |||
103 | #include "puzzles.h" | ||
104 | |||
105 | enum { | ||
106 | COL_BACKGROUND, | ||
107 | NCOLOURS | ||
108 | }; | ||
109 | |||
110 | struct game_params { | ||
111 | int w, h, k; | ||
112 | }; | ||
113 | |||
114 | struct game_state { | ||
115 | int FIXME; | ||
116 | }; | ||
117 | |||
118 | static game_params *default_params(void) | ||
119 | { | ||
120 | game_params *ret = snew(game_params); | ||
121 | |||
122 | ret->w = ret->h = ret->k = 5; /* FIXME: a bit bigger? */ | ||
123 | |||
124 | return ret; | ||
125 | } | ||
126 | |||
127 | static bool game_fetch_preset(int i, char **name, game_params **params) | ||
128 | { | ||
129 | return false; | ||
130 | } | ||
131 | |||
132 | static void free_params(game_params *params) | ||
133 | { | ||
134 | sfree(params); | ||
135 | } | ||
136 | |||
137 | static game_params *dup_params(const game_params *params) | ||
138 | { | ||
139 | game_params *ret = snew(game_params); | ||
140 | *ret = *params; /* structure copy */ | ||
141 | return ret; | ||
142 | } | ||
143 | |||
144 | static void decode_params(game_params *params, char const *string) | ||
145 | { | ||
146 | params->w = params->h = params->k = atoi(string); | ||
147 | while (*string && isdigit((unsigned char)*string)) string++; | ||
148 | if (*string == 'x') { | ||
149 | string++; | ||
150 | params->h = atoi(string); | ||
151 | while (*string && isdigit((unsigned char)*string)) string++; | ||
152 | } | ||
153 | if (*string == 'n') { | ||
154 | string++; | ||
155 | params->k = atoi(string); | ||
156 | while (*string && isdigit((unsigned char)*string)) string++; | ||
157 | } | ||
158 | } | ||
159 | |||
160 | static char *encode_params(const game_params *params, bool full) | ||
161 | { | ||
162 | char buf[256]; | ||
163 | sprintf(buf, "%dx%dn%d", params->w, params->h, params->k); | ||
164 | return dupstr(buf); | ||
165 | } | ||
166 | |||
167 | static config_item *game_configure(const game_params *params) | ||
168 | { | ||
169 | return NULL; | ||
170 | } | ||
171 | |||
172 | static game_params *custom_params(const config_item *cfg) | ||
173 | { | ||
174 | return NULL; | ||
175 | } | ||
176 | |||
177 | static const char *validate_params(const game_params *params, bool full) | ||
178 | { | ||
179 | return NULL; | ||
180 | } | ||
181 | |||
182 | /* ---------------------------------------------------------------------- | ||
183 | * Solver and generator. | ||
184 | */ | ||
185 | |||
186 | struct solver_scratch { | ||
187 | int w, h, k; | ||
188 | |||
189 | /* | ||
190 | * Tracks connectedness between squares. | ||
191 | */ | ||
192 | DSF *dsf; | ||
193 | |||
194 | /* | ||
195 | * size[dsf_canonify(dsf, yx)] tracks the size of the | ||
196 | * connected component containing yx. | ||
197 | */ | ||
198 | int *size; | ||
199 | |||
200 | /* | ||
201 | * contents[dsf_canonify(dsf, yx)*k+i] tracks whether or not | ||
202 | * the connected component containing yx includes letter i. If | ||
203 | * the value is -1, it doesn't; otherwise its value is the | ||
204 | * index in the main grid of the square which contributes that | ||
205 | * letter to the component. | ||
206 | */ | ||
207 | int *contents; | ||
208 | |||
209 | /* | ||
210 | * disconnect[dsf_canonify(dsf, yx1)*w*h + dsf_canonify(dsf, yx2)] | ||
211 | * tracks whether or not the connected components containing | ||
212 | * yx1 and yx2 are known to be distinct. | ||
213 | */ | ||
214 | bool *disconnect; | ||
215 | |||
216 | /* | ||
217 | * Temporary space used only inside particular solver loops. | ||
218 | */ | ||
219 | int *tmp; | ||
220 | }; | ||
221 | |||
222 | static struct solver_scratch *solver_scratch_new(int w, int h, int k) | ||
223 | { | ||
224 | int wh = w*h; | ||
225 | struct solver_scratch *sc = snew(struct solver_scratch); | ||
226 | |||
227 | sc->w = w; | ||
228 | sc->h = h; | ||
229 | sc->k = k; | ||
230 | |||
231 | sc->dsf = dsf_new(wh); | ||
232 | sc->size = snewn(wh, int); | ||
233 | sc->contents = snewn(wh * k, int); | ||
234 | sc->disconnect = snewn(wh*wh, bool); | ||
235 | sc->tmp = snewn(wh, int); | ||
236 | |||
237 | return sc; | ||
238 | } | ||
239 | |||
240 | static void solver_scratch_free(struct solver_scratch *sc) | ||
241 | { | ||
242 | dsf_free(sc->dsf); | ||
243 | sfree(sc->size); | ||
244 | sfree(sc->contents); | ||
245 | sfree(sc->disconnect); | ||
246 | sfree(sc->tmp); | ||
247 | sfree(sc); | ||
248 | } | ||
249 | |||
250 | static void solver_connect(struct solver_scratch *sc, int yx1, int yx2) | ||
251 | { | ||
252 | int w = sc->w, h = sc->h, k = sc->k; | ||
253 | int wh = w*h; | ||
254 | int i, yxnew; | ||
255 | |||
256 | yx1 = dsf_canonify(sc->dsf, yx1); | ||
257 | yx2 = dsf_canonify(sc->dsf, yx2); | ||
258 | assert(yx1 != yx2); | ||
259 | |||
260 | /* | ||
261 | * To connect two components together into a bigger one, we | ||
262 | * start by merging them in the dsf itself. | ||
263 | */ | ||
264 | dsf_merge(sc->dsf, yx1, yx2); | ||
265 | yxnew = dsf_canonify(sc->dsf, yx2); | ||
266 | |||
267 | /* | ||
268 | * The size of the new component is the sum of the sizes of the | ||
269 | * old ones. | ||
270 | */ | ||
271 | sc->size[yxnew] = sc->size[yx1] + sc->size[yx2]; | ||
272 | |||
273 | /* | ||
274 | * The contents bitmap of the new component is the union of the | ||
275 | * contents of the old ones. | ||
276 | * | ||
277 | * Given two numbers at most one of which is not -1, we can | ||
278 | * find the other one by adding the two and adding 1; this | ||
279 | * will yield -1 if both were -1 to begin with, otherwise the | ||
280 | * other. | ||
281 | * | ||
282 | * (A neater approach would be to take their bitwise AND, but | ||
283 | * this is unfortunately not well-defined standard C when done | ||
284 | * to signed integers.) | ||
285 | */ | ||
286 | for (i = 0; i < k; i++) { | ||
287 | assert(sc->contents[yx1*k+i] < 0 || sc->contents[yx2*k+i] < 0); | ||
288 | sc->contents[yxnew*k+i] = (sc->contents[yx1*k+i] + | ||
289 | sc->contents[yx2*k+i] + 1); | ||
290 | } | ||
291 | |||
292 | /* | ||
293 | * We must combine the rows _and_ the columns in the disconnect | ||
294 | * matrix. | ||
295 | */ | ||
296 | for (i = 0; i < wh; i++) | ||
297 | sc->disconnect[yxnew*wh+i] = (sc->disconnect[yx1*wh+i] || | ||
298 | sc->disconnect[yx2*wh+i]); | ||
299 | for (i = 0; i < wh; i++) | ||
300 | sc->disconnect[i*wh+yxnew] = (sc->disconnect[i*wh+yx1] || | ||
301 | sc->disconnect[i*wh+yx2]); | ||
302 | } | ||
303 | |||
304 | static void solver_disconnect(struct solver_scratch *sc, int yx1, int yx2) | ||
305 | { | ||
306 | int w = sc->w, h = sc->h; | ||
307 | int wh = w*h; | ||
308 | |||
309 | yx1 = dsf_canonify(sc->dsf, yx1); | ||
310 | yx2 = dsf_canonify(sc->dsf, yx2); | ||
311 | assert(yx1 != yx2); | ||
312 | assert(!sc->disconnect[yx1*wh+yx2]); | ||
313 | assert(!sc->disconnect[yx2*wh+yx1]); | ||
314 | |||
315 | /* | ||
316 | * Mark the components as disconnected from each other in the | ||
317 | * disconnect matrix. | ||
318 | */ | ||
319 | sc->disconnect[yx1*wh+yx2] = true; | ||
320 | sc->disconnect[yx2*wh+yx1] = true; | ||
321 | } | ||
322 | |||
323 | static void solver_init(struct solver_scratch *sc) | ||
324 | { | ||
325 | int w = sc->w, h = sc->h; | ||
326 | int wh = w*h; | ||
327 | int i; | ||
328 | |||
329 | /* | ||
330 | * Set up most of the scratch space. We don't set up the | ||
331 | * contents array, however, because this will change if we | ||
332 | * adjust the letter arrangement and re-run the solver. | ||
333 | */ | ||
334 | dsf_reinit(sc->dsf); | ||
335 | for (i = 0; i < wh; i++) sc->size[i] = 1; | ||
336 | memset(sc->disconnect, 0, wh*wh * sizeof(bool)); | ||
337 | } | ||
338 | |||
339 | static int solver_attempt(struct solver_scratch *sc, const unsigned char *grid, | ||
340 | bool *gen_lock) | ||
341 | { | ||
342 | int w = sc->w, h = sc->h, k = sc->k; | ||
343 | int wh = w*h; | ||
344 | int i, x, y; | ||
345 | bool done_something_overall = false; | ||
346 | |||
347 | /* | ||
348 | * Set up the contents array from the grid. | ||
349 | */ | ||
350 | for (i = 0; i < wh*k; i++) | ||
351 | sc->contents[i] = -1; | ||
352 | for (i = 0; i < wh; i++) | ||
353 | sc->contents[dsf_canonify(sc->dsf, i)*k+grid[i]] = i; | ||
354 | |||
355 | while (1) { | ||
356 | bool done_something = false; | ||
357 | |||
358 | /* | ||
359 | * Go over the grid looking for reasons to add to the | ||
360 | * disconnect matrix. We're after pairs of squares which: | ||
361 | * | ||
362 | * - are adjacent in the grid | ||
363 | * - belong to distinct dsf components | ||
364 | * - their components are not already marked as | ||
365 | * disconnected | ||
366 | * - their components share a letter in common. | ||
367 | */ | ||
368 | for (y = 0; y < h; y++) { | ||
369 | for (x = 0; x < w; x++) { | ||
370 | int dir; | ||
371 | for (dir = 0; dir < 2; dir++) { | ||
372 | int x2 = x + dir, y2 = y + 1 - dir; | ||
373 | int yx = y*w+x, yx2 = y2*w+x2; | ||
374 | |||
375 | if (x2 >= w || y2 >= h) | ||
376 | continue; /* one square is outside the grid */ | ||
377 | |||
378 | yx = dsf_canonify(sc->dsf, yx); | ||
379 | yx2 = dsf_canonify(sc->dsf, yx2); | ||
380 | if (yx == yx2) | ||
381 | continue; /* same dsf component */ | ||
382 | |||
383 | if (sc->disconnect[yx*wh+yx2]) | ||
384 | continue; /* already known disconnected */ | ||
385 | |||
386 | for (i = 0; i < k; i++) | ||
387 | if (sc->contents[yx*k+i] >= 0 && | ||
388 | sc->contents[yx2*k+i] >= 0) | ||
389 | break; | ||
390 | if (i == k) | ||
391 | continue; /* no letter in common */ | ||
392 | |||
393 | /* | ||
394 | * We've found one. Mark yx and yx2 as | ||
395 | * disconnected from each other. | ||
396 | */ | ||
397 | #ifdef SOLVER_DIAGNOSTICS | ||
398 | printf("Disconnecting %d and %d (%c)\n", yx, yx2, 'A'+i); | ||
399 | #endif | ||
400 | solver_disconnect(sc, yx, yx2); | ||
401 | done_something = done_something_overall = true; | ||
402 | |||
403 | /* | ||
404 | * We have just made a deduction which hinges | ||
405 | * on two particular grid squares being the | ||
406 | * same. If we are feeding back to a generator | ||
407 | * loop, we must therefore mark those squares | ||
408 | * as fixed in the generator, so that future | ||
409 | * rearrangement of the grid will not break | ||
410 | * the information on which we have already | ||
411 | * based deductions. | ||
412 | */ | ||
413 | if (gen_lock) { | ||
414 | gen_lock[sc->contents[yx*k+i]] = true; | ||
415 | gen_lock[sc->contents[yx2*k+i]] = true; | ||
416 | } | ||
417 | } | ||
418 | } | ||
419 | } | ||
420 | |||
421 | /* | ||
422 | * Now go over the grid looking for dsf components which | ||
423 | * are below maximum size and only have one way to extend, | ||
424 | * and extending them. | ||
425 | */ | ||
426 | for (i = 0; i < wh; i++) | ||
427 | sc->tmp[i] = -1; | ||
428 | for (y = 0; y < h; y++) { | ||
429 | for (x = 0; x < w; x++) { | ||
430 | int yx = dsf_canonify(sc->dsf, y*w+x); | ||
431 | int dir; | ||
432 | |||
433 | if (sc->size[yx] == k) | ||
434 | continue; | ||
435 | |||
436 | for (dir = 0; dir < 4; dir++) { | ||
437 | int x2 = x + (dir==0 ? -1 : dir==2 ? 1 : 0); | ||
438 | int y2 = y + (dir==1 ? -1 : dir==3 ? 1 : 0); | ||
439 | int yx2, yx2c; | ||
440 | |||
441 | if (y2 < 0 || y2 >= h || x2 < 0 || x2 >= w) | ||
442 | continue; | ||
443 | yx2 = y2*w+x2; | ||
444 | yx2c = dsf_canonify(sc->dsf, yx2); | ||
445 | |||
446 | if (yx2c != yx && !sc->disconnect[yx2c*wh+yx]) { | ||
447 | /* | ||
448 | * Component yx can be extended into square | ||
449 | * yx2. | ||
450 | */ | ||
451 | if (sc->tmp[yx] == -1) | ||
452 | sc->tmp[yx] = yx2; | ||
453 | else if (sc->tmp[yx] != yx2) | ||
454 | sc->tmp[yx] = -2; /* multiple choices found */ | ||
455 | } | ||
456 | } | ||
457 | } | ||
458 | } | ||
459 | for (i = 0; i < wh; i++) { | ||
460 | if (sc->tmp[i] >= 0) { | ||
461 | /* | ||
462 | * Make sure we haven't connected the two already | ||
463 | * during this loop (which could happen if for | ||
464 | * _both_ components this was the only way to | ||
465 | * extend them). | ||
466 | */ | ||
467 | if (dsf_canonify(sc->dsf, i) == | ||
468 | dsf_canonify(sc->dsf, sc->tmp[i])) | ||
469 | continue; | ||
470 | |||
471 | #ifdef SOLVER_DIAGNOSTICS | ||
472 | printf("Connecting %d and %d\n", i, sc->tmp[i]); | ||
473 | #endif | ||
474 | solver_connect(sc, i, sc->tmp[i]); | ||
475 | done_something = done_something_overall = true; | ||
476 | break; | ||
477 | } | ||
478 | } | ||
479 | |||
480 | if (!done_something) | ||
481 | break; | ||
482 | } | ||
483 | |||
484 | /* | ||
485 | * Return 0 if we haven't made any progress; 1 if we've done | ||
486 | * something but not solved it completely; 2 if we've solved | ||
487 | * it completely. | ||
488 | */ | ||
489 | for (i = 0; i < wh; i++) | ||
490 | if (sc->size[dsf_canonify(sc->dsf, i)] != k) | ||
491 | break; | ||
492 | if (i == wh) | ||
493 | return 2; | ||
494 | if (done_something_overall) | ||
495 | return 1; | ||
496 | return 0; | ||
497 | } | ||
498 | |||
499 | static unsigned char *generate(int w, int h, int k, random_state *rs) | ||
500 | { | ||
501 | int wh = w*h; | ||
502 | int n = wh/k; | ||
503 | struct solver_scratch *sc; | ||
504 | unsigned char *grid; | ||
505 | unsigned char *shuffled; | ||
506 | int i, j, m, retries; | ||
507 | int *permutation; | ||
508 | bool *gen_lock; | ||
509 | |||
510 | sc = solver_scratch_new(w, h, k); | ||
511 | grid = snewn(wh, unsigned char); | ||
512 | shuffled = snewn(k, unsigned char); | ||
513 | permutation = snewn(wh, int); | ||
514 | gen_lock = snewn(wh, bool); | ||
515 | |||
516 | do { | ||
517 | DSF *dsf = divvy_rectangle(w, h, k, rs); | ||
518 | |||
519 | /* | ||
520 | * Go through the dsf and find the indices of all the | ||
521 | * squares involved in each omino, in a manner conducive | ||
522 | * to per-omino indexing. We set permutation[i*k+j] to be | ||
523 | * the index of the jth square (ordered arbitrarily) in | ||
524 | * omino i. | ||
525 | */ | ||
526 | for (i = j = 0; i < wh; i++) | ||
527 | if (dsf_canonify(dsf, i) == i) { | ||
528 | sc->tmp[i] = j; | ||
529 | /* | ||
530 | * During this loop and the following one, we use | ||
531 | * the last element of each row of permutation[] | ||
532 | * as a counter of the number of indices so far | ||
533 | * placed in it. When we place the final index of | ||
534 | * an omino, that counter is overwritten, but that | ||
535 | * doesn't matter because we'll never use it | ||
536 | * again. Of course this depends critically on | ||
537 | * divvy_rectangle() having returned correct | ||
538 | * results, or else chaos would ensue. | ||
539 | */ | ||
540 | permutation[j*k+k-1] = 0; | ||
541 | j++; | ||
542 | } | ||
543 | for (i = 0; i < wh; i++) { | ||
544 | j = sc->tmp[dsf_canonify(dsf, i)]; | ||
545 | m = permutation[j*k+k-1]++; | ||
546 | permutation[j*k+m] = i; | ||
547 | } | ||
548 | |||
549 | /* | ||
550 | * Track which squares' letters we have already depended | ||
551 | * on for deductions. This is gradually updated by | ||
552 | * solver_attempt(). | ||
553 | */ | ||
554 | memset(gen_lock, 0, wh * sizeof(bool)); | ||
555 | |||
556 | /* | ||
557 | * Now repeatedly fill the grid with letters, and attempt | ||
558 | * to solve it. If the solver makes progress but does not | ||
559 | * fail completely, then gen_lock will have been updated | ||
560 | * and we try again. On a complete failure, though, we | ||
561 | * have no option but to give up and abandon this set of | ||
562 | * ominoes. | ||
563 | */ | ||
564 | solver_init(sc); | ||
565 | retries = k*k; | ||
566 | while (1) { | ||
567 | /* | ||
568 | * Fill the grid with letters. We can safely use | ||
569 | * sc->tmp to hold the set of letters required at each | ||
570 | * stage, since it's at least size k and is currently | ||
571 | * unused. | ||
572 | */ | ||
573 | for (i = 0; i < n; i++) { | ||
574 | /* | ||
575 | * First, determine the set of letters already | ||
576 | * placed in this omino by gen_lock. | ||
577 | */ | ||
578 | for (j = 0; j < k; j++) | ||
579 | sc->tmp[j] = j; | ||
580 | for (j = 0; j < k; j++) { | ||
581 | int index = permutation[i*k+j]; | ||
582 | int letter = grid[index]; | ||
583 | if (gen_lock[index]) | ||
584 | sc->tmp[letter] = -1; | ||
585 | } | ||
586 | /* | ||
587 | * Now collect together all the remaining letters | ||
588 | * and randomly shuffle them. | ||
589 | */ | ||
590 | for (j = m = 0; j < k; j++) | ||
591 | if (sc->tmp[j] >= 0) | ||
592 | sc->tmp[m++] = sc->tmp[j]; | ||
593 | shuffle(sc->tmp, m, sizeof(*sc->tmp), rs); | ||
594 | /* | ||
595 | * Finally, write the shuffled letters into the | ||
596 | * grid. | ||
597 | */ | ||
598 | for (j = 0; j < k; j++) { | ||
599 | int index = permutation[i*k+j]; | ||
600 | if (!gen_lock[index]) | ||
601 | grid[index] = sc->tmp[--m]; | ||
602 | } | ||
603 | assert(m == 0); | ||
604 | } | ||
605 | |||
606 | /* | ||
607 | * Now we have a candidate grid. Attempt to progress | ||
608 | * the solution. | ||
609 | */ | ||
610 | m = solver_attempt(sc, grid, gen_lock); | ||
611 | if (m == 2 || /* success */ | ||
612 | (m == 0 && retries-- <= 0)) /* failure */ | ||
613 | break; | ||
614 | if (m == 1) | ||
615 | retries = k*k; /* reset this counter, and continue */ | ||
616 | } | ||
617 | |||
618 | dsf_free(dsf); | ||
619 | } while (m == 0); | ||
620 | |||
621 | sfree(gen_lock); | ||
622 | sfree(permutation); | ||
623 | sfree(shuffled); | ||
624 | solver_scratch_free(sc); | ||
625 | |||
626 | return grid; | ||
627 | } | ||
628 | |||
629 | /* ---------------------------------------------------------------------- | ||
630 | * End of solver/generator code. | ||
631 | */ | ||
632 | |||
633 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
634 | char **aux, bool interactive) | ||
635 | { | ||
636 | int w = params->w, h = params->h, wh = w*h, k = params->k; | ||
637 | unsigned char *grid; | ||
638 | char *desc; | ||
639 | int i; | ||
640 | |||
641 | grid = generate(w, h, k, rs); | ||
642 | |||
643 | desc = snewn(wh+1, char); | ||
644 | for (i = 0; i < wh; i++) | ||
645 | desc[i] = 'A' + grid[i]; | ||
646 | desc[wh] = '\0'; | ||
647 | |||
648 | sfree(grid); | ||
649 | |||
650 | return desc; | ||
651 | } | ||
652 | |||
653 | static const char *validate_desc(const game_params *params, const char *desc) | ||
654 | { | ||
655 | return NULL; | ||
656 | } | ||
657 | |||
658 | static game_state *new_game(midend *me, const game_params *params, | ||
659 | const char *desc) | ||
660 | { | ||
661 | game_state *state = snew(game_state); | ||
662 | |||
663 | state->FIXME = 0; | ||
664 | |||
665 | return state; | ||
666 | } | ||
667 | |||
668 | static game_state *dup_game(const game_state *state) | ||
669 | { | ||
670 | game_state *ret = snew(game_state); | ||
671 | |||
672 | ret->FIXME = state->FIXME; | ||
673 | |||
674 | return ret; | ||
675 | } | ||
676 | |||
677 | static void free_game(game_state *state) | ||
678 | { | ||
679 | sfree(state); | ||
680 | } | ||
681 | |||
682 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
683 | const char *aux, const char **error) | ||
684 | { | ||
685 | return NULL; | ||
686 | } | ||
687 | |||
688 | static bool game_can_format_as_text_now(const game_params *params) | ||
689 | { | ||
690 | return true; | ||
691 | } | ||
692 | |||
693 | static char *game_text_format(const game_state *state) | ||
694 | { | ||
695 | return NULL; | ||
696 | } | ||
697 | |||
698 | static game_ui *new_ui(const game_state *state) | ||
699 | { | ||
700 | return NULL; | ||
701 | } | ||
702 | |||
703 | static void free_ui(game_ui *ui) | ||
704 | { | ||
705 | } | ||
706 | |||
707 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
708 | const game_state *newstate) | ||
709 | { | ||
710 | } | ||
711 | |||
712 | struct game_drawstate { | ||
713 | int tilesize; | ||
714 | int FIXME; | ||
715 | }; | ||
716 | |||
717 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
718 | const game_drawstate *ds, | ||
719 | int x, int y, int button) | ||
720 | { | ||
721 | return NULL; | ||
722 | } | ||
723 | |||
724 | static game_state *execute_move(const game_state *state, const char *move) | ||
725 | { | ||
726 | return NULL; | ||
727 | } | ||
728 | |||
729 | /* ---------------------------------------------------------------------- | ||
730 | * Drawing routines. | ||
731 | */ | ||
732 | |||
733 | static void game_compute_size(const game_params *params, int tilesize, | ||
734 | const game_ui *ui, int *x, int *y) | ||
735 | { | ||
736 | *x = *y = 10 * tilesize; /* FIXME */ | ||
737 | } | ||
738 | |||
739 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
740 | const game_params *params, int tilesize) | ||
741 | { | ||
742 | ds->tilesize = tilesize; | ||
743 | } | ||
744 | |||
745 | static float *game_colours(frontend *fe, int *ncolours) | ||
746 | { | ||
747 | float *ret = snewn(3 * NCOLOURS, float); | ||
748 | |||
749 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
750 | |||
751 | *ncolours = NCOLOURS; | ||
752 | return ret; | ||
753 | } | ||
754 | |||
755 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
756 | { | ||
757 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
758 | |||
759 | ds->tilesize = 0; | ||
760 | ds->FIXME = 0; | ||
761 | |||
762 | return ds; | ||
763 | } | ||
764 | |||
765 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
766 | { | ||
767 | sfree(ds); | ||
768 | } | ||
769 | |||
770 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
771 | const game_state *oldstate, const game_state *state, | ||
772 | int dir, const game_ui *ui, | ||
773 | float animtime, float flashtime) | ||
774 | { | ||
775 | } | ||
776 | |||
777 | static float game_anim_length(const game_state *oldstate, | ||
778 | const game_state *newstate, int dir, game_ui *ui) | ||
779 | { | ||
780 | return 0.0F; | ||
781 | } | ||
782 | |||
783 | static float game_flash_length(const game_state *oldstate, | ||
784 | const game_state *newstate, int dir, game_ui *ui) | ||
785 | { | ||
786 | return 0.0F; | ||
787 | } | ||
788 | |||
789 | static void game_get_cursor_location(const game_ui *ui, | ||
790 | const game_drawstate *ds, | ||
791 | const game_state *state, | ||
792 | const game_params *params, | ||
793 | int *x, int *y, int *w, int *h) | ||
794 | { | ||
795 | } | ||
796 | |||
797 | static int game_status(const game_state *state) | ||
798 | { | ||
799 | return 0; | ||
800 | } | ||
801 | |||
802 | static bool game_timing_state(const game_state *state, game_ui *ui) | ||
803 | { | ||
804 | return true; | ||
805 | } | ||
806 | |||
807 | static void game_print_size(const game_params *params, const game_ui *ui, | ||
808 | float *x, float *y) | ||
809 | { | ||
810 | } | ||
811 | |||
812 | static void game_print(drawing *dr, const game_state *state, const game_ui *ui, | ||
813 | int tilesize) | ||
814 | { | ||
815 | } | ||
816 | |||
817 | #ifdef COMBINED | ||
818 | #define thegame separate | ||
819 | #endif | ||
820 | |||
821 | const struct game thegame = { | ||
822 | "Separate", NULL, NULL, | ||
823 | default_params, | ||
824 | game_fetch_preset, NULL, | ||
825 | decode_params, | ||
826 | encode_params, | ||
827 | free_params, | ||
828 | dup_params, | ||
829 | false, game_configure, custom_params, | ||
830 | validate_params, | ||
831 | new_game_desc, | ||
832 | validate_desc, | ||
833 | new_game, | ||
834 | dup_game, | ||
835 | free_game, | ||
836 | false, solve_game, | ||
837 | false, game_can_format_as_text_now, game_text_format, | ||
838 | NULL, NULL, /* get_prefs, set_prefs */ | ||
839 | new_ui, | ||
840 | free_ui, | ||
841 | NULL, /* encode_ui */ | ||
842 | NULL, /* decode_ui */ | ||
843 | NULL, /* game_request_keys */ | ||
844 | game_changed_state, | ||
845 | NULL, /* current_key_label */ | ||
846 | interpret_move, | ||
847 | execute_move, | ||
848 | 20 /* FIXME */, game_compute_size, game_set_size, | ||
849 | game_colours, | ||
850 | game_new_drawstate, | ||
851 | game_free_drawstate, | ||
852 | game_redraw, | ||
853 | game_anim_length, | ||
854 | game_flash_length, | ||
855 | game_get_cursor_location, | ||
856 | game_status, | ||
857 | false, false, game_print_size, game_print, | ||
858 | false, /* wants_statusbar */ | ||
859 | false, game_timing_state, | ||
860 | 0, /* flags */ | ||
861 | }; | ||