tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1#include <assert.h>
2#include <string.h>
3#include <stdarg.h>
4
5#include "puzzles.h"
6#include "tree234.h"
7#include "matching.h"
8
9#ifdef STANDALONE_LATIN_TEST
10#define STANDALONE_SOLVER
11#endif
12
13#include "latin.h"
14
15/* --------------------------------------------------------
16 * Solver.
17 */
18
19static int latin_solver_top(struct latin_solver *solver, int maxdiff,
20 int diff_simple, int diff_set_0, int diff_set_1,
21 int diff_forcing, int diff_recursive,
22 usersolver_t const *usersolvers, validator_t valid,
23 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree);
24
25#ifdef STANDALONE_SOLVER
26int solver_show_working, solver_recurse_depth;
27#endif
28
29/*
30 * Function called when we are certain that a particular square has
31 * a particular number in it. The y-coordinate passed in here is
32 * transformed.
33 */
34void latin_solver_place(struct latin_solver *solver, int x, int y, int n)
35{
36 int i, o = solver->o;
37
38 assert(n <= o);
39 assert(cube(x,y,n));
40
41 /*
42 * Rule out all other numbers in this square.
43 */
44 for (i = 1; i <= o; i++)
45 if (i != n)
46 cube(x,y,i) = false;
47
48 /*
49 * Rule out this number in all other positions in the row.
50 */
51 for (i = 0; i < o; i++)
52 if (i != y)
53 cube(x,i,n) = false;
54
55 /*
56 * Rule out this number in all other positions in the column.
57 */
58 for (i = 0; i < o; i++)
59 if (i != x)
60 cube(i,y,n) = false;
61
62 /*
63 * Enter the number in the result grid.
64 */
65 solver->grid[y*o+x] = n;
66
67 /*
68 * Cross out this number from the list of numbers left to place
69 * in its row, its column and its block.
70 */
71 solver->row[y*o+n-1] = solver->col[x*o+n-1] = true;
72}
73
74int latin_solver_elim(struct latin_solver *solver, int start, int step
75#ifdef STANDALONE_SOLVER
76 , const char *fmt, ...
77#endif
78 )
79{
80 int o = solver->o;
81#ifdef STANDALONE_SOLVER
82 char **names = solver->names;
83#endif
84 int fpos, m, i;
85
86 /*
87 * Count the number of set bits within this section of the
88 * cube.
89 */
90 m = 0;
91 fpos = -1;
92 for (i = 0; i < o; i++)
93 if (solver->cube[start+i*step]) {
94 fpos = start+i*step;
95 m++;
96 }
97
98 if (m == 1) {
99 int x, y, n;
100 assert(fpos >= 0);
101
102 n = 1 + fpos % o;
103 y = fpos / o;
104 x = y / o;
105 y %= o;
106
107 if (!solver->grid[y*o+x]) {
108#ifdef STANDALONE_SOLVER
109 if (solver_show_working) {
110 va_list ap;
111 printf("%*s", solver_recurse_depth*4, "");
112 va_start(ap, fmt);
113 vprintf(fmt, ap);
114 va_end(ap);
115 printf(":\n%*s placing %s at (%d,%d)\n",
116 solver_recurse_depth*4, "", names[n-1],
117 x+1, y+1);
118 }
119#endif
120 latin_solver_place(solver, x, y, n);
121 return +1;
122 }
123 } else if (m == 0) {
124#ifdef STANDALONE_SOLVER
125 if (solver_show_working) {
126 va_list ap;
127 printf("%*s", solver_recurse_depth*4, "");
128 va_start(ap, fmt);
129 vprintf(fmt, ap);
130 va_end(ap);
131 printf(":\n%*s no possibilities available\n",
132 solver_recurse_depth*4, "");
133 }
134#endif
135 return -1;
136 }
137
138 return 0;
139}
140
141struct latin_solver_scratch {
142 unsigned char *grid, *rowidx, *colidx, *set;
143 int *neighbours, *bfsqueue;
144#ifdef STANDALONE_SOLVER
145 int *bfsprev;
146#endif
147};
148
149int latin_solver_set(struct latin_solver *solver,
150 struct latin_solver_scratch *scratch,
151 int start, int step1, int step2
152#ifdef STANDALONE_SOLVER
153 , const char *fmt, ...
154#endif
155 )
156{
157 int o = solver->o;
158#ifdef STANDALONE_SOLVER
159 char **names = solver->names;
160#endif
161 int i, j, n, count;
162 unsigned char *grid = scratch->grid;
163 unsigned char *rowidx = scratch->rowidx;
164 unsigned char *colidx = scratch->colidx;
165 unsigned char *set = scratch->set;
166
167 /*
168 * We are passed a o-by-o matrix of booleans. Our first job
169 * is to winnow it by finding any definite placements - i.e.
170 * any row with a solitary 1 - and discarding that row and the
171 * column containing the 1.
172 */
173 memset(rowidx, true, o);
174 memset(colidx, true, o);
175 for (i = 0; i < o; i++) {
176 int count = 0, first = -1;
177 for (j = 0; j < o; j++)
178 if (solver->cube[start+i*step1+j*step2])
179 first = j, count++;
180
181 if (count == 0) return -1;
182 if (count == 1)
183 rowidx[i] = colidx[first] = false;
184 }
185
186 /*
187 * Convert each of rowidx/colidx from a list of 0s and 1s to a
188 * list of the indices of the 1s.
189 */
190 for (i = j = 0; i < o; i++)
191 if (rowidx[i])
192 rowidx[j++] = i;
193 n = j;
194 for (i = j = 0; i < o; i++)
195 if (colidx[i])
196 colidx[j++] = i;
197 assert(n == j);
198
199 /*
200 * And create the smaller matrix.
201 */
202 for (i = 0; i < n; i++)
203 for (j = 0; j < n; j++)
204 grid[i*o+j] = solver->cube[start+rowidx[i]*step1+colidx[j]*step2];
205
206 /*
207 * Having done that, we now have a matrix in which every row
208 * has at least two 1s in. Now we search to see if we can find
209 * a rectangle of zeroes (in the set-theoretic sense of
210 * `rectangle', i.e. a subset of rows crossed with a subset of
211 * columns) whose width and height add up to n.
212 */
213
214 memset(set, 0, n);
215 count = 0;
216 while (1) {
217 /*
218 * We have a candidate set. If its size is <=1 or >=n-1
219 * then we move on immediately.
220 */
221 if (count > 1 && count < n-1) {
222 /*
223 * The number of rows we need is n-count. See if we can
224 * find that many rows which each have a zero in all
225 * the positions listed in `set'.
226 */
227 int rows = 0;
228 for (i = 0; i < n; i++) {
229 bool ok = true;
230 for (j = 0; j < n; j++)
231 if (set[j] && grid[i*o+j]) {
232 ok = false;
233 break;
234 }
235 if (ok)
236 rows++;
237 }
238
239 /*
240 * We expect never to be able to get _more_ than
241 * n-count suitable rows: this would imply that (for
242 * example) there are four numbers which between them
243 * have at most three possible positions, and hence it
244 * indicates a faulty deduction before this point or
245 * even a bogus clue.
246 */
247 if (rows > n - count) {
248#ifdef STANDALONE_SOLVER
249 if (solver_show_working) {
250 va_list ap;
251 printf("%*s", solver_recurse_depth*4,
252 "");
253 va_start(ap, fmt);
254 vprintf(fmt, ap);
255 va_end(ap);
256 printf(":\n%*s contradiction reached\n",
257 solver_recurse_depth*4, "");
258 }
259#endif
260 return -1;
261 }
262
263 if (rows >= n - count) {
264 bool progress = false;
265
266 /*
267 * We've got one! Now, for each row which _doesn't_
268 * satisfy the criterion, eliminate all its set
269 * bits in the positions _not_ listed in `set'.
270 * Return +1 (meaning progress has been made) if we
271 * successfully eliminated anything at all.
272 *
273 * This involves referring back through
274 * rowidx/colidx in order to work out which actual
275 * positions in the cube to meddle with.
276 */
277 for (i = 0; i < n; i++) {
278 bool ok = true;
279 for (j = 0; j < n; j++)
280 if (set[j] && grid[i*o+j]) {
281 ok = false;
282 break;
283 }
284 if (!ok) {
285 for (j = 0; j < n; j++)
286 if (!set[j] && grid[i*o+j]) {
287 int fpos = (start+rowidx[i]*step1+
288 colidx[j]*step2);
289#ifdef STANDALONE_SOLVER
290 if (solver_show_working) {
291 int px, py, pn;
292
293 if (!progress) {
294 va_list ap;
295 printf("%*s", solver_recurse_depth*4,
296 "");
297 va_start(ap, fmt);
298 vprintf(fmt, ap);
299 va_end(ap);
300 printf(":\n");
301 }
302
303 pn = 1 + fpos % o;
304 py = fpos / o;
305 px = py / o;
306 py %= o;
307
308 printf("%*s ruling out %s at (%d,%d)\n",
309 solver_recurse_depth*4, "",
310 names[pn-1], px+1, py+1);
311 }
312#endif
313 progress = true;
314 solver->cube[fpos] = false;
315 }
316 }
317 }
318
319 if (progress) {
320 return +1;
321 }
322 }
323 }
324
325 /*
326 * Binary increment: change the rightmost 0 to a 1, and
327 * change all 1s to the right of it to 0s.
328 */
329 i = n;
330 while (i > 0 && set[i-1])
331 set[--i] = 0, count--;
332 if (i > 0)
333 set[--i] = 1, count++;
334 else
335 break; /* done */
336 }
337
338 return 0;
339}
340
341/*
342 * Look for forcing chains. A forcing chain is a path of
343 * pairwise-exclusive squares (i.e. each pair of adjacent squares
344 * in the path are in the same row, column or block) with the
345 * following properties:
346 *
347 * (a) Each square on the path has precisely two possible numbers.
348 *
349 * (b) Each pair of squares which are adjacent on the path share
350 * at least one possible number in common.
351 *
352 * (c) Each square in the middle of the path shares _both_ of its
353 * numbers with at least one of its neighbours (not the same
354 * one with both neighbours).
355 *
356 * These together imply that at least one of the possible number
357 * choices at one end of the path forces _all_ the rest of the
358 * numbers along the path. In order to make real use of this, we
359 * need further properties:
360 *
361 * (c) Ruling out some number N from the square at one end
362 * of the path forces the square at the other end to
363 * take number N.
364 *
365 * (d) The two end squares are both in line with some third
366 * square.
367 *
368 * (e) That third square currently has N as a possibility.
369 *
370 * If we can find all of that lot, we can deduce that at least one
371 * of the two ends of the forcing chain has number N, and that
372 * therefore the mutually adjacent third square does not.
373 *
374 * To find forcing chains, we're going to start a bfs at each
375 * suitable square, once for each of its two possible numbers.
376 */
377int latin_solver_forcing(struct latin_solver *solver,
378 struct latin_solver_scratch *scratch)
379{
380 int o = solver->o;
381#ifdef STANDALONE_SOLVER
382 char **names = solver->names;
383#endif
384 int *bfsqueue = scratch->bfsqueue;
385#ifdef STANDALONE_SOLVER
386 int *bfsprev = scratch->bfsprev;
387#endif
388 unsigned char *number = scratch->grid;
389 int *neighbours = scratch->neighbours;
390 int x, y;
391
392 for (y = 0; y < o; y++)
393 for (x = 0; x < o; x++) {
394 int count, t, n;
395
396 /*
397 * If this square doesn't have exactly two candidate
398 * numbers, don't try it.
399 *
400 * In this loop we also sum the candidate numbers,
401 * which is a nasty hack to allow us to quickly find
402 * `the other one' (since we will shortly know there
403 * are exactly two).
404 */
405 for (count = t = 0, n = 1; n <= o; n++)
406 if (cube(x, y, n))
407 count++, t += n;
408 if (count != 2)
409 continue;
410
411 /*
412 * Now attempt a bfs for each candidate.
413 */
414 for (n = 1; n <= o; n++)
415 if (cube(x, y, n)) {
416 int orign, currn, head, tail;
417
418 /*
419 * Begin a bfs.
420 */
421 orign = n;
422
423 memset(number, o+1, o*o);
424 head = tail = 0;
425 bfsqueue[tail++] = y*o+x;
426#ifdef STANDALONE_SOLVER
427 bfsprev[y*o+x] = -1;
428#endif
429 number[y*o+x] = t - n;
430
431 while (head < tail) {
432 int xx, yy, nneighbours, xt, yt, i;
433
434 xx = bfsqueue[head++];
435 yy = xx / o;
436 xx %= o;
437
438 currn = number[yy*o+xx];
439
440 /*
441 * Find neighbours of yy,xx.
442 */
443 nneighbours = 0;
444 for (yt = 0; yt < o; yt++)
445 neighbours[nneighbours++] = yt*o+xx;
446 for (xt = 0; xt < o; xt++)
447 neighbours[nneighbours++] = yy*o+xt;
448
449 /*
450 * Try visiting each of those neighbours.
451 */
452 for (i = 0; i < nneighbours; i++) {
453 int cc, tt, nn;
454
455 xt = neighbours[i] % o;
456 yt = neighbours[i] / o;
457
458 /*
459 * We need this square to not be
460 * already visited, and to include
461 * currn as a possible number.
462 */
463 if (number[yt*o+xt] <= o)
464 continue;
465 if (!cube(xt, yt, currn))
466 continue;
467
468 /*
469 * Don't visit _this_ square a second
470 * time!
471 */
472 if (xt == xx && yt == yy)
473 continue;
474
475 /*
476 * To continue with the bfs, we need
477 * this square to have exactly two
478 * possible numbers.
479 */
480 for (cc = tt = 0, nn = 1; nn <= o; nn++)
481 if (cube(xt, yt, nn))
482 cc++, tt += nn;
483 if (cc == 2) {
484 bfsqueue[tail++] = yt*o+xt;
485#ifdef STANDALONE_SOLVER
486 bfsprev[yt*o+xt] = yy*o+xx;
487#endif
488 number[yt*o+xt] = tt - currn;
489 }
490
491 /*
492 * One other possibility is that this
493 * might be the square in which we can
494 * make a real deduction: if it's
495 * adjacent to x,y, and currn is equal
496 * to the original number we ruled out.
497 */
498 if (currn == orign &&
499 (xt == x || yt == y)) {
500#ifdef STANDALONE_SOLVER
501 if (solver_show_working) {
502 const char *sep = "";
503 int xl, yl;
504 printf("%*sforcing chain, %s at ends of ",
505 solver_recurse_depth*4, "",
506 names[orign-1]);
507 xl = xx;
508 yl = yy;
509 while (1) {
510 printf("%s(%d,%d)", sep, xl+1,
511 yl+1);
512 xl = bfsprev[yl*o+xl];
513 if (xl < 0)
514 break;
515 yl = xl / o;
516 xl %= o;
517 sep = "-";
518 }
519 printf("\n%*s ruling out %s at (%d,%d)\n",
520 solver_recurse_depth*4, "",
521 names[orign-1],
522 xt+1, yt+1);
523 }
524#endif
525 cube(xt, yt, orign) = false;
526 return 1;
527 }
528 }
529 }
530 }
531 }
532
533 return 0;
534}
535
536struct latin_solver_scratch *latin_solver_new_scratch(struct latin_solver *solver)
537{
538 struct latin_solver_scratch *scratch = snew(struct latin_solver_scratch);
539 int o = solver->o;
540 scratch->grid = snewn(o*o, unsigned char);
541 scratch->rowidx = snewn(o, unsigned char);
542 scratch->colidx = snewn(o, unsigned char);
543 scratch->set = snewn(o, unsigned char);
544 scratch->neighbours = snewn(3*o, int);
545 scratch->bfsqueue = snewn(o*o, int);
546#ifdef STANDALONE_SOLVER
547 scratch->bfsprev = snewn(o*o, int);
548#endif
549 return scratch;
550}
551
552void latin_solver_free_scratch(struct latin_solver_scratch *scratch)
553{
554#ifdef STANDALONE_SOLVER
555 sfree(scratch->bfsprev);
556#endif
557 sfree(scratch->bfsqueue);
558 sfree(scratch->neighbours);
559 sfree(scratch->set);
560 sfree(scratch->colidx);
561 sfree(scratch->rowidx);
562 sfree(scratch->grid);
563 sfree(scratch);
564}
565
566bool latin_solver_alloc(struct latin_solver *solver, digit *grid, int o)
567{
568 int x, y;
569
570 solver->o = o;
571 solver->cube = snewn(o*o*o, unsigned char);
572 solver->grid = grid; /* write straight back to the input */
573 memset(solver->cube, 1, o*o*o);
574
575 solver->row = snewn(o*o, unsigned char);
576 solver->col = snewn(o*o, unsigned char);
577 memset(solver->row, 0, o*o);
578 memset(solver->col, 0, o*o);
579
580#ifdef STANDALONE_SOLVER
581 solver->names = NULL;
582#endif
583
584 for (x = 0; x < o; x++) {
585 for (y = 0; y < o; y++) {
586 int n = grid[y*o+x];
587 if (n) {
588 if (cube(x, y, n))
589 latin_solver_place(solver, x, y, n);
590 else
591 return false; /* puzzle is already inconsistent */
592 }
593 }
594 }
595
596 return true;
597}
598
599void latin_solver_free(struct latin_solver *solver)
600{
601 sfree(solver->cube);
602 sfree(solver->row);
603 sfree(solver->col);
604}
605
606int latin_solver_diff_simple(struct latin_solver *solver)
607{
608 int x, y, n, ret, o = solver->o;
609#ifdef STANDALONE_SOLVER
610 char **names = solver->names;
611#endif
612
613 /*
614 * Row-wise positional elimination.
615 */
616 for (y = 0; y < o; y++)
617 for (n = 1; n <= o; n++)
618 if (!solver->row[y*o+n-1]) {
619 ret = latin_solver_elim(solver, cubepos(0,y,n), o*o
620#ifdef STANDALONE_SOLVER
621 , "positional elimination,"
622 " %s in row %d", names[n-1],
623 y+1
624#endif
625 );
626 if (ret != 0) return ret;
627 }
628 /*
629 * Column-wise positional elimination.
630 */
631 for (x = 0; x < o; x++)
632 for (n = 1; n <= o; n++)
633 if (!solver->col[x*o+n-1]) {
634 ret = latin_solver_elim(solver, cubepos(x,0,n), o
635#ifdef STANDALONE_SOLVER
636 , "positional elimination,"
637 " %s in column %d", names[n-1], x+1
638#endif
639 );
640 if (ret != 0) return ret;
641 }
642
643 /*
644 * Numeric elimination.
645 */
646 for (x = 0; x < o; x++)
647 for (y = 0; y < o; y++)
648 if (!solver->grid[y*o+x]) {
649 ret = latin_solver_elim(solver, cubepos(x,y,1), 1
650#ifdef STANDALONE_SOLVER
651 , "numeric elimination at (%d,%d)",
652 x+1, y+1
653#endif
654 );
655 if (ret != 0) return ret;
656 }
657 return 0;
658}
659
660int latin_solver_diff_set(struct latin_solver *solver,
661 struct latin_solver_scratch *scratch,
662 bool extreme)
663{
664 int x, y, n, ret, o = solver->o;
665#ifdef STANDALONE_SOLVER
666 char **names = solver->names;
667#endif
668
669 if (!extreme) {
670 /*
671 * Row-wise set elimination.
672 */
673 for (y = 0; y < o; y++) {
674 ret = latin_solver_set(solver, scratch, cubepos(0,y,1), o*o, 1
675#ifdef STANDALONE_SOLVER
676 , "set elimination, row %d", y+1
677#endif
678 );
679 if (ret != 0) return ret;
680 }
681 /*
682 * Column-wise set elimination.
683 */
684 for (x = 0; x < o; x++) {
685 ret = latin_solver_set(solver, scratch, cubepos(x,0,1), o, 1
686#ifdef STANDALONE_SOLVER
687 , "set elimination, column %d", x+1
688#endif
689 );
690 if (ret != 0) return ret;
691 }
692 } else {
693 /*
694 * Row-vs-column set elimination on a single number
695 * (much tricker for a human to do!)
696 */
697 for (n = 1; n <= o; n++) {
698 ret = latin_solver_set(solver, scratch, cubepos(0,0,n), o*o, o
699#ifdef STANDALONE_SOLVER
700 , "positional set elimination on %s",
701 names[n-1]
702#endif
703 );
704 if (ret != 0) return ret;
705 }
706 }
707 return 0;
708}
709
710/*
711 * Returns:
712 * 0 for 'didn't do anything' implying it was already solved.
713 * -1 for 'impossible' (no solution)
714 * 1 for 'single solution'
715 * >1 for 'multiple solutions' (you don't get to know how many, and
716 * the first such solution found will be set.
717 *
718 * and this function may well assert if given an impossible board.
719 */
720static int latin_solver_recurse
721 (struct latin_solver *solver, int diff_simple, int diff_set_0,
722 int diff_set_1, int diff_forcing, int diff_recursive,
723 usersolver_t const *usersolvers, validator_t valid, void *ctx,
724 ctxnew_t ctxnew, ctxfree_t ctxfree)
725{
726 int best, bestcount;
727 int o = solver->o, x, y, n;
728#ifdef STANDALONE_SOLVER
729 char **names = solver->names;
730#endif
731
732 best = -1;
733 bestcount = o+1;
734
735 for (y = 0; y < o; y++)
736 for (x = 0; x < o; x++)
737 if (!solver->grid[y*o+x]) {
738 int count;
739
740 /*
741 * An unfilled square. Count the number of
742 * possible digits in it.
743 */
744 count = 0;
745 for (n = 1; n <= o; n++)
746 if (cube(x,y,n))
747 count++;
748
749 /*
750 * We should have found any impossibilities
751 * already, so this can safely be an assert.
752 */
753 assert(count > 1);
754
755 if (count < bestcount) {
756 bestcount = count;
757 best = y*o+x;
758 }
759 }
760
761 if (best == -1)
762 /* we were complete already. */
763 return 0;
764 else {
765 int i, j;
766 digit *list, *ingrid, *outgrid;
767 int diff = diff_impossible; /* no solution found yet */
768
769 /*
770 * Attempt recursion.
771 */
772 y = best / o;
773 x = best % o;
774
775 list = snewn(o, digit);
776 ingrid = snewn(o*o, digit);
777 outgrid = snewn(o*o, digit);
778 memcpy(ingrid, solver->grid, o*o);
779
780 /* Make a list of the possible digits. */
781 for (j = 0, n = 1; n <= o; n++)
782 if (cube(x,y,n))
783 list[j++] = n;
784
785#ifdef STANDALONE_SOLVER
786 if (solver_show_working) {
787 const char *sep = "";
788 printf("%*srecursing on (%d,%d) [",
789 solver_recurse_depth*4, "", x+1, y+1);
790 for (i = 0; i < j; i++) {
791 printf("%s%s", sep, names[list[i]-1]);
792 sep = " or ";
793 }
794 printf("]\n");
795 }
796#endif
797
798 /*
799 * And step along the list, recursing back into the
800 * main solver at every stage.
801 */
802 for (i = 0; i < j; i++) {
803 int ret;
804 void *newctx;
805 struct latin_solver subsolver;
806
807 memcpy(outgrid, ingrid, o*o);
808 outgrid[y*o+x] = list[i];
809
810#ifdef STANDALONE_SOLVER
811 if (solver_show_working)
812 printf("%*sguessing %s at (%d,%d)\n",
813 solver_recurse_depth*4, "", names[list[i]-1], x+1, y+1);
814 solver_recurse_depth++;
815#endif
816
817 if (ctxnew) {
818 newctx = ctxnew(ctx);
819 } else {
820 newctx = ctx;
821 }
822 if (latin_solver_alloc(&subsolver, outgrid, o)) {
823#ifdef STANDALONE_SOLVER
824 subsolver.names = solver->names;
825#endif
826 ret = latin_solver_top(&subsolver, diff_recursive,
827 diff_simple, diff_set_0, diff_set_1,
828 diff_forcing, diff_recursive,
829 usersolvers, valid, newctx,
830 ctxnew, ctxfree);
831 } else {
832 ret = diff_impossible;
833 }
834 latin_solver_free(&subsolver);
835 if (ctxnew)
836 ctxfree(newctx);
837
838#ifdef STANDALONE_SOLVER
839 solver_recurse_depth--;
840 if (solver_show_working) {
841 printf("%*sretracting %s at (%d,%d)\n",
842 solver_recurse_depth*4, "", names[list[i]-1], x+1, y+1);
843 }
844#endif
845 /* we recurse as deep as we can, so we should never find
846 * find ourselves giving up on a puzzle without declaring it
847 * impossible. */
848 assert(ret != diff_unfinished);
849
850 /*
851 * If we have our first solution, copy it into the
852 * grid we will return.
853 */
854 if (diff == diff_impossible && ret != diff_impossible)
855 memcpy(solver->grid, outgrid, o*o);
856
857 if (ret == diff_ambiguous)
858 diff = diff_ambiguous;
859 else if (ret == diff_impossible)
860 /* do not change our return value */;
861 else {
862 /* the recursion turned up exactly one solution */
863 if (diff == diff_impossible)
864 diff = diff_recursive;
865 else
866 diff = diff_ambiguous;
867 }
868
869 /*
870 * As soon as we've found more than one solution,
871 * give up immediately.
872 */
873 if (diff == diff_ambiguous)
874 break;
875 }
876
877 sfree(outgrid);
878 sfree(ingrid);
879 sfree(list);
880
881 if (diff == diff_impossible)
882 return -1;
883 else if (diff == diff_ambiguous)
884 return 2;
885 else {
886 assert(diff == diff_recursive);
887 return 1;
888 }
889 }
890}
891
892static int latin_solver_top(struct latin_solver *solver, int maxdiff,
893 int diff_simple, int diff_set_0, int diff_set_1,
894 int diff_forcing, int diff_recursive,
895 usersolver_t const *usersolvers, validator_t valid,
896 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree)
897{
898 struct latin_solver_scratch *scratch = latin_solver_new_scratch(solver);
899 int ret, diff = diff_simple;
900
901 assert(maxdiff <= diff_recursive);
902 /*
903 * Now loop over the grid repeatedly trying all permitted modes
904 * of reasoning. The loop terminates if we complete an
905 * iteration without making any progress; we then return
906 * failure or success depending on whether the grid is full or
907 * not.
908 */
909 while (1) {
910 int i;
911
912 cont:
913
914 latin_solver_debug(solver->cube, solver->o);
915
916 for (i = 0; i <= maxdiff; i++) {
917 if (usersolvers[i])
918 ret = usersolvers[i](solver, ctx);
919 else
920 ret = 0;
921 if (ret == 0 && i == diff_simple)
922 ret = latin_solver_diff_simple(solver);
923 if (ret == 0 && i == diff_set_0)
924 ret = latin_solver_diff_set(solver, scratch, false);
925 if (ret == 0 && i == diff_set_1)
926 ret = latin_solver_diff_set(solver, scratch, true);
927 if (ret == 0 && i == diff_forcing)
928 ret = latin_solver_forcing(solver, scratch);
929
930 if (ret < 0) {
931 diff = diff_impossible;
932 goto got_result;
933 } else if (ret > 0) {
934 diff = max(diff, i);
935 goto cont;
936 }
937 }
938
939 /*
940 * If we reach here, we have made no deductions in this
941 * iteration, so the algorithm terminates.
942 */
943 break;
944 }
945
946 /*
947 * Last chance: if we haven't fully solved the puzzle yet, try
948 * recursing based on guesses for a particular square. We pick
949 * one of the most constrained empty squares we can find, which
950 * has the effect of pruning the search tree as much as
951 * possible.
952 */
953 if (maxdiff == diff_recursive) {
954 int nsol = latin_solver_recurse(solver,
955 diff_simple, diff_set_0, diff_set_1,
956 diff_forcing, diff_recursive,
957 usersolvers, valid, ctx,
958 ctxnew, ctxfree);
959 if (nsol < 0) diff = diff_impossible;
960 else if (nsol == 1) diff = diff_recursive;
961 else if (nsol > 1) diff = diff_ambiguous;
962 /* if nsol == 0 then we were complete anyway
963 * (and thus don't need to change diff) */
964 } else {
965 /*
966 * We're forbidden to use recursion, so we just see whether
967 * our grid is fully solved, and return diff_unfinished
968 * otherwise.
969 */
970 int x, y, o = solver->o;
971
972 for (y = 0; y < o; y++)
973 for (x = 0; x < o; x++)
974 if (!solver->grid[y*o+x])
975 diff = diff_unfinished;
976 }
977
978 got_result:
979
980#ifdef STANDALONE_SOLVER
981 if (solver_show_working) {
982 if (diff != diff_impossible && diff != diff_unfinished &&
983 diff != diff_ambiguous) {
984 int x, y;
985
986 printf("%*sone solution found:\n", solver_recurse_depth*4, "");
987
988 for (y = 0; y < solver->o; y++) {
989 printf("%*s", solver_recurse_depth*4+1, "");
990 for (x = 0; x < solver->o; x++) {
991 int val = solver->grid[y*solver->o+x];
992 assert(val);
993 printf(" %s", solver->names[val-1]);
994 }
995 printf("\n");
996 }
997 } else {
998 printf("%*s%s found\n",
999 solver_recurse_depth*4, "",
1000 diff == diff_impossible ? "no solution (impossible)" :
1001 diff == diff_unfinished ? "no solution (unfinished)" :
1002 "multiple solutions");
1003 }
1004 }
1005#endif
1006
1007 if (diff != diff_impossible && diff != diff_unfinished &&
1008 diff != diff_ambiguous && valid && !valid(solver, ctx)) {
1009#ifdef STANDALONE_SOLVER
1010 if (solver_show_working) {
1011 printf("%*ssolution failed final validation!\n",
1012 solver_recurse_depth*4, "");
1013 }
1014#endif
1015 diff = diff_impossible;
1016 }
1017
1018 latin_solver_free_scratch(scratch);
1019
1020 return diff;
1021}
1022
1023int latin_solver_main(struct latin_solver *solver, int maxdiff,
1024 int diff_simple, int diff_set_0, int diff_set_1,
1025 int diff_forcing, int diff_recursive,
1026 usersolver_t const *usersolvers, validator_t valid,
1027 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree)
1028{
1029 int diff;
1030#ifdef STANDALONE_SOLVER
1031 int o = solver->o;
1032 char *text = NULL, **names = NULL;
1033#endif
1034
1035#ifdef STANDALONE_SOLVER
1036 if (!solver->names) {
1037 char *p;
1038 int i;
1039
1040 text = snewn(40 * o, char);
1041 p = text;
1042
1043 solver->names = snewn(o, char *);
1044
1045 for (i = 0; i < o; i++) {
1046 solver->names[i] = p;
1047 p += 1 + sprintf(p, "%d", i+1);
1048 }
1049 }
1050#endif
1051
1052 diff = latin_solver_top(solver, maxdiff,
1053 diff_simple, diff_set_0, diff_set_1,
1054 diff_forcing, diff_recursive,
1055 usersolvers, valid, ctx, ctxnew, ctxfree);
1056
1057#ifdef STANDALONE_SOLVER
1058 sfree(names);
1059 sfree(text);
1060#endif
1061
1062 return diff;
1063}
1064
1065int latin_solver(digit *grid, int o, int maxdiff,
1066 int diff_simple, int diff_set_0, int diff_set_1,
1067 int diff_forcing, int diff_recursive,
1068 usersolver_t const *usersolvers, validator_t valid,
1069 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree)
1070{
1071 struct latin_solver solver;
1072 int diff;
1073
1074 if (latin_solver_alloc(&solver, grid, o))
1075 diff = latin_solver_main(&solver, maxdiff,
1076 diff_simple, diff_set_0, diff_set_1,
1077 diff_forcing, diff_recursive,
1078 usersolvers, valid, ctx, ctxnew, ctxfree);
1079 else
1080 diff = diff_impossible;
1081 latin_solver_free(&solver);
1082 return diff;
1083}
1084
1085void latin_solver_debug(unsigned char *cube, int o)
1086{
1087#ifdef STANDALONE_SOLVER
1088 if (solver_show_working > 1) {
1089 struct latin_solver ls, *solver = &ls;
1090 char *dbg;
1091 int x, y, i, c = 0;
1092
1093 ls.cube = cube; ls.o = o; /* for cube() to work */
1094
1095 dbg = snewn(3*o*o*o, char);
1096 for (y = 0; y < o; y++) {
1097 for (x = 0; x < o; x++) {
1098 for (i = 1; i <= o; i++) {
1099 if (cube(x,y,i))
1100 dbg[c++] = i + '0';
1101 else
1102 dbg[c++] = '.';
1103 }
1104 dbg[c++] = ' ';
1105 }
1106 dbg[c++] = '\n';
1107 }
1108 dbg[c++] = '\n';
1109 dbg[c++] = '\0';
1110
1111 printf("%s", dbg);
1112 sfree(dbg);
1113 }
1114#endif
1115}
1116
1117void latin_debug(digit *sq, int o)
1118{
1119#ifdef STANDALONE_SOLVER
1120 if (solver_show_working) {
1121 int x, y;
1122
1123 for (y = 0; y < o; y++) {
1124 for (x = 0; x < o; x++) {
1125 printf("%2d ", sq[y*o+x]);
1126 }
1127 printf("\n");
1128 }
1129 printf("\n");
1130 }
1131#endif
1132}
1133
1134/* --------------------------------------------------------
1135 * Generation.
1136 */
1137
1138digit *latin_generate(int o, random_state *rs)
1139{
1140 digit *sq;
1141 int *adjdata, *adjsizes, *matching;
1142 int **adjlists;
1143 void *scratch;
1144 int i, j, k;
1145 digit *row;
1146
1147 /*
1148 * To efficiently generate a latin square in such a way that
1149 * all possible squares are possible outputs from the function,
1150 * we make use of a theorem which states that any r x n latin
1151 * rectangle, with r < n, can be extended into an (r+1) x n
1152 * latin rectangle. In other words, we can reliably generate a
1153 * latin square row by row, by at every stage writing down any
1154 * row at all which doesn't conflict with previous rows, and
1155 * the theorem guarantees that we will never have to backtrack.
1156 *
1157 * To find a viable row at each stage, we can make use of the
1158 * support functions in matching.c.
1159 */
1160
1161 sq = snewn(o*o, digit);
1162
1163 /*
1164 * matching.c will take care of randomising the generation of each
1165 * row of the square, but in case this entire method of generation
1166 * introduces a really subtle top-to-bottom directional bias,
1167 * we'll also generate the rows themselves in random order.
1168 */
1169 row = snewn(o, digit);
1170 for (i = 0; i < o; i++)
1171 row[i] = i;
1172 shuffle(row, i, sizeof(*row), rs);
1173
1174 /*
1175 * Set up the infrastructure for the matching subroutine.
1176 */
1177 scratch = smalloc(matching_scratch_size(o, o));
1178 adjdata = snewn(o*o, int);
1179 adjlists = snewn(o, int *);
1180 adjsizes = snewn(o, int);
1181 matching = snewn(o, int);
1182
1183 /*
1184 * Now generate each row of the latin square.
1185 */
1186 for (i = 0; i < o; i++) {
1187 /*
1188 * Make adjacency lists for a bipartite graph joining each
1189 * column to all the numbers not yet placed in that column.
1190 */
1191 for (j = 0; j < o; j++) {
1192 int *p, *adj = adjdata + j*o;
1193 for (k = 0; k < o; k++)
1194 adj[k] = 1;
1195 for (k = 0; k < i; k++)
1196 adj[sq[row[k]*o + j] - 1] = 0;
1197 adjlists[j] = p = adj;
1198 for (k = 0; k < o; k++)
1199 if (adj[k])
1200 *p++ = k;
1201 adjsizes[j] = p - adjlists[j];
1202 }
1203
1204 /*
1205 * Run the matching algorithm.
1206 */
1207 j = matching_with_scratch(scratch, o, o, adjlists, adjsizes,
1208 rs, matching, NULL);
1209 assert(j == o); /* by the above theorem, this must have succeeded */
1210
1211 /*
1212 * And use the output to set up the new row of the latin
1213 * square.
1214 */
1215 for (j = 0; j < o; j++)
1216 sq[row[i]*o + j] = matching[j] + 1;
1217 }
1218
1219 /*
1220 * Done. Free our internal workspaces...
1221 */
1222 sfree(matching);
1223 sfree(adjlists);
1224 sfree(adjsizes);
1225 sfree(adjdata);
1226 sfree(scratch);
1227 sfree(row);
1228
1229 /*
1230 * ... and return our completed latin square.
1231 */
1232 return sq;
1233}
1234
1235digit *latin_generate_rect(int w, int h, random_state *rs)
1236{
1237 int o = max(w, h), x, y;
1238 digit *latin, *latin_rect;
1239
1240 latin = latin_generate(o, rs);
1241 latin_rect = snewn(w*h, digit);
1242
1243 for (x = 0; x < w; x++) {
1244 for (y = 0; y < h; y++) {
1245 latin_rect[y*w + x] = latin[y*o + x];
1246 }
1247 }
1248
1249 sfree(latin);
1250 return latin_rect;
1251}
1252
1253/* --------------------------------------------------------
1254 * Checking.
1255 */
1256
1257typedef struct lcparams {
1258 digit elt;
1259 int count;
1260} lcparams;
1261
1262static int latin_check_cmp(void *v1, void *v2)
1263{
1264 lcparams *lc1 = (lcparams *)v1;
1265 lcparams *lc2 = (lcparams *)v2;
1266
1267 if (lc1->elt < lc2->elt) return -1;
1268 if (lc1->elt > lc2->elt) return 1;
1269 return 0;
1270}
1271
1272#define ELT(sq,x,y) (sq[((y)*order)+(x)])
1273
1274/* returns true if sq is not a latin square. */
1275bool latin_check(digit *sq, int order)
1276{
1277 tree234 *dict = newtree234(latin_check_cmp);
1278 int c, r;
1279 bool ret = false;
1280 lcparams *lcp, lc, *aret;
1281
1282 /* Use a tree234 as a simple hash table, go through the square
1283 * adding elements as we go or incrementing their counts. */
1284 for (c = 0; c < order; c++) {
1285 for (r = 0; r < order; r++) {
1286 lc.elt = ELT(sq, c, r); lc.count = 0;
1287 lcp = find234(dict, &lc, NULL);
1288 if (!lcp) {
1289 lcp = snew(lcparams);
1290 lcp->elt = ELT(sq, c, r);
1291 lcp->count = 1;
1292 aret = add234(dict, lcp);
1293 assert(aret == lcp);
1294 } else {
1295 lcp->count++;
1296 }
1297 }
1298 }
1299
1300 /* There should be precisely 'order' letters in the alphabet,
1301 * each occurring 'order' times (making the OxO tree) */
1302 if (count234(dict) != order) ret = true;
1303 else {
1304 for (c = 0; (lcp = index234(dict, c)) != NULL; c++) {
1305 if (lcp->count != order) ret = true;
1306 }
1307 }
1308 for (c = 0; (lcp = index234(dict, c)) != NULL; c++)
1309 sfree(lcp);
1310 freetree234(dict);
1311
1312 return ret;
1313}
1314
1315/* vim: set shiftwidth=4 tabstop=8: */