diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/separate.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/separate.c | 859 |
1 files changed, 859 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..a7b4fc96e1 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/separate.c | |||
@@ -0,0 +1,859 @@ | |||
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 | #include <math.h> | ||
98 | |||
99 | #include "puzzles.h" | ||
100 | |||
101 | enum { | ||
102 | COL_BACKGROUND, | ||
103 | NCOLOURS | ||
104 | }; | ||
105 | |||
106 | struct game_params { | ||
107 | int w, h, k; | ||
108 | }; | ||
109 | |||
110 | struct game_state { | ||
111 | int FIXME; | ||
112 | }; | ||
113 | |||
114 | static game_params *default_params(void) | ||
115 | { | ||
116 | game_params *ret = snew(game_params); | ||
117 | |||
118 | ret->w = ret->h = ret->k = 5; /* FIXME: a bit bigger? */ | ||
119 | |||
120 | return ret; | ||
121 | } | ||
122 | |||
123 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
124 | { | ||
125 | return FALSE; | ||
126 | } | ||
127 | |||
128 | static void free_params(game_params *params) | ||
129 | { | ||
130 | sfree(params); | ||
131 | } | ||
132 | |||
133 | static game_params *dup_params(const game_params *params) | ||
134 | { | ||
135 | game_params *ret = snew(game_params); | ||
136 | *ret = *params; /* structure copy */ | ||
137 | return ret; | ||
138 | } | ||
139 | |||
140 | static void decode_params(game_params *params, char const *string) | ||
141 | { | ||
142 | params->w = params->h = params->k = atoi(string); | ||
143 | while (*string && isdigit((unsigned char)*string)) string++; | ||
144 | if (*string == 'x') { | ||
145 | string++; | ||
146 | params->h = atoi(string); | ||
147 | while (*string && isdigit((unsigned char)*string)) string++; | ||
148 | } | ||
149 | if (*string == 'n') { | ||
150 | string++; | ||
151 | params->k = atoi(string); | ||
152 | while (*string && isdigit((unsigned char)*string)) string++; | ||
153 | } | ||
154 | } | ||
155 | |||
156 | static char *encode_params(const game_params *params, int full) | ||
157 | { | ||
158 | char buf[256]; | ||
159 | sprintf(buf, "%dx%dn%d", params->w, params->h, params->k); | ||
160 | return dupstr(buf); | ||
161 | } | ||
162 | |||
163 | static config_item *game_configure(const game_params *params) | ||
164 | { | ||
165 | return NULL; | ||
166 | } | ||
167 | |||
168 | static game_params *custom_params(const config_item *cfg) | ||
169 | { | ||
170 | return NULL; | ||
171 | } | ||
172 | |||
173 | static char *validate_params(const game_params *params, int full) | ||
174 | { | ||
175 | return NULL; | ||
176 | } | ||
177 | |||
178 | /* ---------------------------------------------------------------------- | ||
179 | * Solver and generator. | ||
180 | */ | ||
181 | |||
182 | struct solver_scratch { | ||
183 | int w, h, k; | ||
184 | |||
185 | /* | ||
186 | * Tracks connectedness between squares. | ||
187 | */ | ||
188 | int *dsf; | ||
189 | |||
190 | /* | ||
191 | * size[dsf_canonify(dsf, yx)] tracks the size of the | ||
192 | * connected component containing yx. | ||
193 | */ | ||
194 | int *size; | ||
195 | |||
196 | /* | ||
197 | * contents[dsf_canonify(dsf, yx)*k+i] tracks whether or not | ||
198 | * the connected component containing yx includes letter i. If | ||
199 | * the value is -1, it doesn't; otherwise its value is the | ||
200 | * index in the main grid of the square which contributes that | ||
201 | * letter to the component. | ||
202 | */ | ||
203 | int *contents; | ||
204 | |||
205 | /* | ||
206 | * disconnect[dsf_canonify(dsf, yx1)*w*h + dsf_canonify(dsf, yx2)] | ||
207 | * tracks whether or not the connected components containing | ||
208 | * yx1 and yx2 are known to be distinct. | ||
209 | */ | ||
210 | unsigned char *disconnect; | ||
211 | |||
212 | /* | ||
213 | * Temporary space used only inside particular solver loops. | ||
214 | */ | ||
215 | int *tmp; | ||
216 | }; | ||
217 | |||
218 | struct solver_scratch *solver_scratch_new(int w, int h, int k) | ||
219 | { | ||
220 | int wh = w*h; | ||
221 | struct solver_scratch *sc = snew(struct solver_scratch); | ||
222 | |||
223 | sc->w = w; | ||
224 | sc->h = h; | ||
225 | sc->k = k; | ||
226 | |||
227 | sc->dsf = snew_dsf(wh); | ||
228 | sc->size = snewn(wh, int); | ||
229 | sc->contents = snewn(wh * k, int); | ||
230 | sc->disconnect = snewn(wh*wh, unsigned char); | ||
231 | sc->tmp = snewn(wh, int); | ||
232 | |||
233 | return sc; | ||
234 | } | ||
235 | |||
236 | void solver_scratch_free(struct solver_scratch *sc) | ||
237 | { | ||
238 | sfree(sc->dsf); | ||
239 | sfree(sc->size); | ||
240 | sfree(sc->contents); | ||
241 | sfree(sc->disconnect); | ||
242 | sfree(sc->tmp); | ||
243 | sfree(sc); | ||
244 | } | ||
245 | |||
246 | void solver_connect(struct solver_scratch *sc, int yx1, int yx2) | ||
247 | { | ||
248 | int w = sc->w, h = sc->h, k = sc->k; | ||
249 | int wh = w*h; | ||
250 | int i, yxnew; | ||
251 | |||
252 | yx1 = dsf_canonify(sc->dsf, yx1); | ||
253 | yx2 = dsf_canonify(sc->dsf, yx2); | ||
254 | assert(yx1 != yx2); | ||
255 | |||
256 | /* | ||
257 | * To connect two components together into a bigger one, we | ||
258 | * start by merging them in the dsf itself. | ||
259 | */ | ||
260 | dsf_merge(sc->dsf, yx1, yx2); | ||
261 | yxnew = dsf_canonify(sc->dsf, yx2); | ||
262 | |||
263 | /* | ||
264 | * The size of the new component is the sum of the sizes of the | ||
265 | * old ones. | ||
266 | */ | ||
267 | sc->size[yxnew] = sc->size[yx1] + sc->size[yx2]; | ||
268 | |||
269 | /* | ||
270 | * The contents bitmap of the new component is the union of the | ||
271 | * contents of the old ones. | ||
272 | * | ||
273 | * Given two numbers at most one of which is not -1, we can | ||
274 | * find the other one by adding the two and adding 1; this | ||
275 | * will yield -1 if both were -1 to begin with, otherwise the | ||
276 | * other. | ||
277 | * | ||
278 | * (A neater approach would be to take their bitwise AND, but | ||
279 | * this is unfortunately not well-defined standard C when done | ||
280 | * to signed integers.) | ||
281 | */ | ||
282 | for (i = 0; i < k; i++) { | ||
283 | assert(sc->contents[yx1*k+i] < 0 || sc->contents[yx2*k+i] < 0); | ||
284 | sc->contents[yxnew*k+i] = (sc->contents[yx1*k+i] + | ||
285 | sc->contents[yx2*k+i] + 1); | ||
286 | } | ||
287 | |||
288 | /* | ||
289 | * We must combine the rows _and_ the columns in the disconnect | ||
290 | * matrix. | ||
291 | */ | ||
292 | for (i = 0; i < wh; i++) | ||
293 | sc->disconnect[yxnew*wh+i] = (sc->disconnect[yx1*wh+i] || | ||
294 | sc->disconnect[yx2*wh+i]); | ||
295 | for (i = 0; i < wh; i++) | ||
296 | sc->disconnect[i*wh+yxnew] = (sc->disconnect[i*wh+yx1] || | ||
297 | sc->disconnect[i*wh+yx2]); | ||
298 | } | ||
299 | |||
300 | void solver_disconnect(struct solver_scratch *sc, int yx1, int yx2) | ||
301 | { | ||
302 | int w = sc->w, h = sc->h; | ||
303 | int wh = w*h; | ||
304 | |||
305 | yx1 = dsf_canonify(sc->dsf, yx1); | ||
306 | yx2 = dsf_canonify(sc->dsf, yx2); | ||
307 | assert(yx1 != yx2); | ||
308 | assert(!sc->disconnect[yx1*wh+yx2]); | ||
309 | assert(!sc->disconnect[yx2*wh+yx1]); | ||
310 | |||
311 | /* | ||
312 | * Mark the components as disconnected from each other in the | ||
313 | * disconnect matrix. | ||
314 | */ | ||
315 | sc->disconnect[yx1*wh+yx2] = sc->disconnect[yx2*wh+yx1] = 1; | ||
316 | } | ||
317 | |||
318 | void solver_init(struct solver_scratch *sc) | ||
319 | { | ||
320 | int w = sc->w, h = sc->h; | ||
321 | int wh = w*h; | ||
322 | int i; | ||
323 | |||
324 | /* | ||
325 | * Set up most of the scratch space. We don't set up the | ||
326 | * contents array, however, because this will change if we | ||
327 | * adjust the letter arrangement and re-run the solver. | ||
328 | */ | ||
329 | dsf_init(sc->dsf, wh); | ||
330 | for (i = 0; i < wh; i++) sc->size[i] = 1; | ||
331 | memset(sc->disconnect, 0, wh*wh); | ||
332 | } | ||
333 | |||
334 | int solver_attempt(struct solver_scratch *sc, const unsigned char *grid, | ||
335 | unsigned char *gen_lock) | ||
336 | { | ||
337 | int w = sc->w, h = sc->h, k = sc->k; | ||
338 | int wh = w*h; | ||
339 | int i, x, y; | ||
340 | int done_something_overall = FALSE; | ||
341 | |||
342 | /* | ||
343 | * Set up the contents array from the grid. | ||
344 | */ | ||
345 | for (i = 0; i < wh*k; i++) | ||
346 | sc->contents[i] = -1; | ||
347 | for (i = 0; i < wh; i++) | ||
348 | sc->contents[dsf_canonify(sc->dsf, i)*k+grid[i]] = i; | ||
349 | |||
350 | while (1) { | ||
351 | int done_something = FALSE; | ||
352 | |||
353 | /* | ||
354 | * Go over the grid looking for reasons to add to the | ||
355 | * disconnect matrix. We're after pairs of squares which: | ||
356 | * | ||
357 | * - are adjacent in the grid | ||
358 | * - belong to distinct dsf components | ||
359 | * - their components are not already marked as | ||
360 | * disconnected | ||
361 | * - their components share a letter in common. | ||
362 | */ | ||
363 | for (y = 0; y < h; y++) { | ||
364 | for (x = 0; x < w; x++) { | ||
365 | int dir; | ||
366 | for (dir = 0; dir < 2; dir++) { | ||
367 | int x2 = x + dir, y2 = y + 1 - dir; | ||
368 | int yx = y*w+x, yx2 = y2*w+x2; | ||
369 | |||
370 | if (x2 >= w || y2 >= h) | ||
371 | continue; /* one square is outside the grid */ | ||
372 | |||
373 | yx = dsf_canonify(sc->dsf, yx); | ||
374 | yx2 = dsf_canonify(sc->dsf, yx2); | ||
375 | if (yx == yx2) | ||
376 | continue; /* same dsf component */ | ||
377 | |||
378 | if (sc->disconnect[yx*wh+yx2]) | ||
379 | continue; /* already known disconnected */ | ||
380 | |||
381 | for (i = 0; i < k; i++) | ||
382 | if (sc->contents[yx*k+i] >= 0 && | ||
383 | sc->contents[yx2*k+i] >= 0) | ||
384 | break; | ||
385 | if (i == k) | ||
386 | continue; /* no letter in common */ | ||
387 | |||
388 | /* | ||
389 | * We've found one. Mark yx and yx2 as | ||
390 | * disconnected from each other. | ||
391 | */ | ||
392 | #ifdef SOLVER_DIAGNOSTICS | ||
393 | printf("Disconnecting %d and %d (%c)\n", yx, yx2, 'A'+i); | ||
394 | #endif | ||
395 | solver_disconnect(sc, yx, yx2); | ||
396 | done_something = done_something_overall = TRUE; | ||
397 | |||
398 | /* | ||
399 | * We have just made a deduction which hinges | ||
400 | * on two particular grid squares being the | ||
401 | * same. If we are feeding back to a generator | ||
402 | * loop, we must therefore mark those squares | ||
403 | * as fixed in the generator, so that future | ||
404 | * rearrangement of the grid will not break | ||
405 | * the information on which we have already | ||
406 | * based deductions. | ||
407 | */ | ||
408 | if (gen_lock) { | ||
409 | gen_lock[sc->contents[yx*k+i]] = 1; | ||
410 | gen_lock[sc->contents[yx2*k+i]] = 1; | ||
411 | } | ||
412 | } | ||
413 | } | ||
414 | } | ||
415 | |||
416 | /* | ||
417 | * Now go over the grid looking for dsf components which | ||
418 | * are below maximum size and only have one way to extend, | ||
419 | * and extending them. | ||
420 | */ | ||
421 | for (i = 0; i < wh; i++) | ||
422 | sc->tmp[i] = -1; | ||
423 | for (y = 0; y < h; y++) { | ||
424 | for (x = 0; x < w; x++) { | ||
425 | int yx = dsf_canonify(sc->dsf, y*w+x); | ||
426 | int dir; | ||
427 | |||
428 | if (sc->size[yx] == k) | ||
429 | continue; | ||
430 | |||
431 | for (dir = 0; dir < 4; dir++) { | ||
432 | int x2 = x + (dir==0 ? -1 : dir==2 ? 1 : 0); | ||
433 | int y2 = y + (dir==1 ? -1 : dir==3 ? 1 : 0); | ||
434 | int yx2, yx2c; | ||
435 | |||
436 | if (y2 < 0 || y2 >= h || x2 < 0 || x2 >= w) | ||
437 | continue; | ||
438 | yx2 = y2*w+x2; | ||
439 | yx2c = dsf_canonify(sc->dsf, yx2); | ||
440 | |||
441 | if (yx2c != yx && !sc->disconnect[yx2c*wh+yx]) { | ||
442 | /* | ||
443 | * Component yx can be extended into square | ||
444 | * yx2. | ||
445 | */ | ||
446 | if (sc->tmp[yx] == -1) | ||
447 | sc->tmp[yx] = yx2; | ||
448 | else if (sc->tmp[yx] != yx2) | ||
449 | sc->tmp[yx] = -2; /* multiple choices found */ | ||
450 | } | ||
451 | } | ||
452 | } | ||
453 | } | ||
454 | for (i = 0; i < wh; i++) { | ||
455 | if (sc->tmp[i] >= 0) { | ||
456 | /* | ||
457 | * Make sure we haven't connected the two already | ||
458 | * during this loop (which could happen if for | ||
459 | * _both_ components this was the only way to | ||
460 | * extend them). | ||
461 | */ | ||
462 | if (dsf_canonify(sc->dsf, i) == | ||
463 | dsf_canonify(sc->dsf, sc->tmp[i])) | ||
464 | continue; | ||
465 | |||
466 | #ifdef SOLVER_DIAGNOSTICS | ||
467 | printf("Connecting %d and %d\n", i, sc->tmp[i]); | ||
468 | #endif | ||
469 | solver_connect(sc, i, sc->tmp[i]); | ||
470 | done_something = done_something_overall = TRUE; | ||
471 | break; | ||
472 | } | ||
473 | } | ||
474 | |||
475 | if (!done_something) | ||
476 | break; | ||
477 | } | ||
478 | |||
479 | /* | ||
480 | * Return 0 if we haven't made any progress; 1 if we've done | ||
481 | * something but not solved it completely; 2 if we've solved | ||
482 | * it completely. | ||
483 | */ | ||
484 | for (i = 0; i < wh; i++) | ||
485 | if (sc->size[dsf_canonify(sc->dsf, i)] != k) | ||
486 | break; | ||
487 | if (i == wh) | ||
488 | return 2; | ||
489 | if (done_something_overall) | ||
490 | return 1; | ||
491 | return 0; | ||
492 | } | ||
493 | |||
494 | unsigned char *generate(int w, int h, int k, random_state *rs) | ||
495 | { | ||
496 | int wh = w*h; | ||
497 | int n = wh/k; | ||
498 | struct solver_scratch *sc; | ||
499 | unsigned char *grid; | ||
500 | unsigned char *shuffled; | ||
501 | int i, j, m, retries; | ||
502 | int *permutation; | ||
503 | unsigned char *gen_lock; | ||
504 | extern int *divvy_rectangle(int w, int h, int k, random_state *rs); | ||
505 | |||
506 | sc = solver_scratch_new(w, h, k); | ||
507 | grid = snewn(wh, unsigned char); | ||
508 | shuffled = snewn(k, unsigned char); | ||
509 | permutation = snewn(wh, int); | ||
510 | gen_lock = snewn(wh, unsigned char); | ||
511 | |||
512 | do { | ||
513 | int *dsf = divvy_rectangle(w, h, k, rs); | ||
514 | |||
515 | /* | ||
516 | * Go through the dsf and find the indices of all the | ||
517 | * squares involved in each omino, in a manner conducive | ||
518 | * to per-omino indexing. We set permutation[i*k+j] to be | ||
519 | * the index of the jth square (ordered arbitrarily) in | ||
520 | * omino i. | ||
521 | */ | ||
522 | for (i = j = 0; i < wh; i++) | ||
523 | if (dsf_canonify(dsf, i) == i) { | ||
524 | sc->tmp[i] = j; | ||
525 | /* | ||
526 | * During this loop and the following one, we use | ||
527 | * the last element of each row of permutation[] | ||
528 | * as a counter of the number of indices so far | ||
529 | * placed in it. When we place the final index of | ||
530 | * an omino, that counter is overwritten, but that | ||
531 | * doesn't matter because we'll never use it | ||
532 | * again. Of course this depends critically on | ||
533 | * divvy_rectangle() having returned correct | ||
534 | * results, or else chaos would ensue. | ||
535 | */ | ||
536 | permutation[j*k+k-1] = 0; | ||
537 | j++; | ||
538 | } | ||
539 | for (i = 0; i < wh; i++) { | ||
540 | j = sc->tmp[dsf_canonify(dsf, i)]; | ||
541 | m = permutation[j*k+k-1]++; | ||
542 | permutation[j*k+m] = i; | ||
543 | } | ||
544 | |||
545 | /* | ||
546 | * Track which squares' letters we have already depended | ||
547 | * on for deductions. This is gradually updated by | ||
548 | * solver_attempt(). | ||
549 | */ | ||
550 | memset(gen_lock, 0, wh); | ||
551 | |||
552 | /* | ||
553 | * Now repeatedly fill the grid with letters, and attempt | ||
554 | * to solve it. If the solver makes progress but does not | ||
555 | * fail completely, then gen_lock will have been updated | ||
556 | * and we try again. On a complete failure, though, we | ||
557 | * have no option but to give up and abandon this set of | ||
558 | * ominoes. | ||
559 | */ | ||
560 | solver_init(sc); | ||
561 | retries = k*k; | ||
562 | while (1) { | ||
563 | /* | ||
564 | * Fill the grid with letters. We can safely use | ||
565 | * sc->tmp to hold the set of letters required at each | ||
566 | * stage, since it's at least size k and is currently | ||
567 | * unused. | ||
568 | */ | ||
569 | for (i = 0; i < n; i++) { | ||
570 | /* | ||
571 | * First, determine the set of letters already | ||
572 | * placed in this omino by gen_lock. | ||
573 | */ | ||
574 | for (j = 0; j < k; j++) | ||
575 | sc->tmp[j] = j; | ||
576 | for (j = 0; j < k; j++) { | ||
577 | int index = permutation[i*k+j]; | ||
578 | int letter = grid[index]; | ||
579 | if (gen_lock[index]) | ||
580 | sc->tmp[letter] = -1; | ||
581 | } | ||
582 | /* | ||
583 | * Now collect together all the remaining letters | ||
584 | * and randomly shuffle them. | ||
585 | */ | ||
586 | for (j = m = 0; j < k; j++) | ||
587 | if (sc->tmp[j] >= 0) | ||
588 | sc->tmp[m++] = sc->tmp[j]; | ||
589 | shuffle(sc->tmp, m, sizeof(*sc->tmp), rs); | ||
590 | /* | ||
591 | * Finally, write the shuffled letters into the | ||
592 | * grid. | ||
593 | */ | ||
594 | for (j = 0; j < k; j++) { | ||
595 | int index = permutation[i*k+j]; | ||
596 | if (!gen_lock[index]) | ||
597 | grid[index] = sc->tmp[--m]; | ||
598 | } | ||
599 | assert(m == 0); | ||
600 | } | ||
601 | |||
602 | /* | ||
603 | * Now we have a candidate grid. Attempt to progress | ||
604 | * the solution. | ||
605 | */ | ||
606 | m = solver_attempt(sc, grid, gen_lock); | ||
607 | if (m == 2 || /* success */ | ||
608 | (m == 0 && retries-- <= 0)) /* failure */ | ||
609 | break; | ||
610 | if (m == 1) | ||
611 | retries = k*k; /* reset this counter, and continue */ | ||
612 | } | ||
613 | |||
614 | sfree(dsf); | ||
615 | } while (m == 0); | ||
616 | |||
617 | sfree(gen_lock); | ||
618 | sfree(permutation); | ||
619 | sfree(shuffled); | ||
620 | solver_scratch_free(sc); | ||
621 | |||
622 | return grid; | ||
623 | } | ||
624 | |||
625 | /* ---------------------------------------------------------------------- | ||
626 | * End of solver/generator code. | ||
627 | */ | ||
628 | |||
629 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
630 | char **aux, int interactive) | ||
631 | { | ||
632 | int w = params->w, h = params->h, wh = w*h, k = params->k; | ||
633 | unsigned char *grid; | ||
634 | char *desc; | ||
635 | int i; | ||
636 | |||
637 | grid = generate(w, h, k, rs); | ||
638 | |||
639 | desc = snewn(wh+1, char); | ||
640 | for (i = 0; i < wh; i++) | ||
641 | desc[i] = 'A' + grid[i]; | ||
642 | desc[wh] = '\0'; | ||
643 | |||
644 | sfree(grid); | ||
645 | |||
646 | return desc; | ||
647 | } | ||
648 | |||
649 | static char *validate_desc(const game_params *params, const char *desc) | ||
650 | { | ||
651 | return NULL; | ||
652 | } | ||
653 | |||
654 | static game_state *new_game(midend *me, const game_params *params, | ||
655 | const char *desc) | ||
656 | { | ||
657 | game_state *state = snew(game_state); | ||
658 | |||
659 | state->FIXME = 0; | ||
660 | |||
661 | return state; | ||
662 | } | ||
663 | |||
664 | static game_state *dup_game(const game_state *state) | ||
665 | { | ||
666 | game_state *ret = snew(game_state); | ||
667 | |||
668 | ret->FIXME = state->FIXME; | ||
669 | |||
670 | return ret; | ||
671 | } | ||
672 | |||
673 | static void free_game(game_state *state) | ||
674 | { | ||
675 | sfree(state); | ||
676 | } | ||
677 | |||
678 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
679 | const char *aux, char **error) | ||
680 | { | ||
681 | return NULL; | ||
682 | } | ||
683 | |||
684 | static int game_can_format_as_text_now(const game_params *params) | ||
685 | { | ||
686 | return TRUE; | ||
687 | } | ||
688 | |||
689 | static char *game_text_format(const game_state *state) | ||
690 | { | ||
691 | return NULL; | ||
692 | } | ||
693 | |||
694 | static game_ui *new_ui(const game_state *state) | ||
695 | { | ||
696 | return NULL; | ||
697 | } | ||
698 | |||
699 | static void free_ui(game_ui *ui) | ||
700 | { | ||
701 | } | ||
702 | |||
703 | static char *encode_ui(const game_ui *ui) | ||
704 | { | ||
705 | return NULL; | ||
706 | } | ||
707 | |||
708 | static void decode_ui(game_ui *ui, const char *encoding) | ||
709 | { | ||
710 | } | ||
711 | |||
712 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
713 | const game_state *newstate) | ||
714 | { | ||
715 | } | ||
716 | |||
717 | struct game_drawstate { | ||
718 | int tilesize; | ||
719 | int FIXME; | ||
720 | }; | ||
721 | |||
722 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
723 | const game_drawstate *ds, | ||
724 | int x, int y, int button) | ||
725 | { | ||
726 | return NULL; | ||
727 | } | ||
728 | |||
729 | static game_state *execute_move(const game_state *state, const char *move) | ||
730 | { | ||
731 | return NULL; | ||
732 | } | ||
733 | |||
734 | /* ---------------------------------------------------------------------- | ||
735 | * Drawing routines. | ||
736 | */ | ||
737 | |||
738 | static void game_compute_size(const game_params *params, int tilesize, | ||
739 | int *x, int *y) | ||
740 | { | ||
741 | *x = *y = 10 * tilesize; /* FIXME */ | ||
742 | } | ||
743 | |||
744 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
745 | const game_params *params, int tilesize) | ||
746 | { | ||
747 | ds->tilesize = tilesize; | ||
748 | } | ||
749 | |||
750 | static float *game_colours(frontend *fe, int *ncolours) | ||
751 | { | ||
752 | float *ret = snewn(3 * NCOLOURS, float); | ||
753 | |||
754 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
755 | |||
756 | *ncolours = NCOLOURS; | ||
757 | return ret; | ||
758 | } | ||
759 | |||
760 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
761 | { | ||
762 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
763 | |||
764 | ds->tilesize = 0; | ||
765 | ds->FIXME = 0; | ||
766 | |||
767 | return ds; | ||
768 | } | ||
769 | |||
770 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
771 | { | ||
772 | sfree(ds); | ||
773 | } | ||
774 | |||
775 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
776 | const game_state *oldstate, const game_state *state, | ||
777 | int dir, const game_ui *ui, | ||
778 | float animtime, float flashtime) | ||
779 | { | ||
780 | /* | ||
781 | * The initial contents of the window are not guaranteed and | ||
782 | * can vary with front ends. To be on the safe side, all games | ||
783 | * should start by drawing a big background-colour rectangle | ||
784 | * covering the whole window. | ||
785 | */ | ||
786 | draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND); | ||
787 | } | ||
788 | |||
789 | static float game_anim_length(const game_state *oldstate, | ||
790 | const game_state *newstate, int dir, game_ui *ui) | ||
791 | { | ||
792 | return 0.0F; | ||
793 | } | ||
794 | |||
795 | static float game_flash_length(const game_state *oldstate, | ||
796 | const game_state *newstate, int dir, game_ui *ui) | ||
797 | { | ||
798 | return 0.0F; | ||
799 | } | ||
800 | |||
801 | static int game_status(const game_state *state) | ||
802 | { | ||
803 | return 0; | ||
804 | } | ||
805 | |||
806 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
807 | { | ||
808 | return TRUE; | ||
809 | } | ||
810 | |||
811 | static void game_print_size(const game_params *params, float *x, float *y) | ||
812 | { | ||
813 | } | ||
814 | |||
815 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
816 | { | ||
817 | } | ||
818 | |||
819 | #ifdef COMBINED | ||
820 | #define thegame separate | ||
821 | #endif | ||
822 | |||
823 | const struct game thegame = { | ||
824 | "Separate", NULL, NULL, | ||
825 | default_params, | ||
826 | game_fetch_preset, NULL, | ||
827 | decode_params, | ||
828 | encode_params, | ||
829 | free_params, | ||
830 | dup_params, | ||
831 | FALSE, game_configure, custom_params, | ||
832 | validate_params, | ||
833 | new_game_desc, | ||
834 | validate_desc, | ||
835 | new_game, | ||
836 | dup_game, | ||
837 | free_game, | ||
838 | FALSE, solve_game, | ||
839 | FALSE, game_can_format_as_text_now, game_text_format, | ||
840 | new_ui, | ||
841 | free_ui, | ||
842 | encode_ui, | ||
843 | decode_ui, | ||
844 | game_changed_state, | ||
845 | interpret_move, | ||
846 | execute_move, | ||
847 | 20 /* FIXME */, game_compute_size, game_set_size, | ||
848 | game_colours, | ||
849 | game_new_drawstate, | ||
850 | game_free_drawstate, | ||
851 | game_redraw, | ||
852 | game_anim_length, | ||
853 | game_flash_length, | ||
854 | game_status, | ||
855 | FALSE, FALSE, game_print_size, game_print, | ||
856 | FALSE, /* wants_statusbar */ | ||
857 | FALSE, game_timing_state, | ||
858 | 0, /* flags */ | ||
859 | }; | ||