149255d7 |
1 | #ifndef LATIN_H |
2 | #define LATIN_H |
3 | |
4 | #include "puzzles.h" |
5 | |
6 | typedef unsigned char digit; |
7 | |
8 | /* --- Solver structures, definitions --- */ |
9 | |
10 | #ifdef STANDALONE_SOLVER |
62f8425e |
11 | extern int solver_show_working, solver_recurse_depth; |
149255d7 |
12 | #endif |
13 | |
14 | struct latin_solver { |
15 | int o; /* order of latin square */ |
16 | unsigned char *cube; /* o^3, indexed by x, y, and digit: |
17 | TRUE in that position indicates a possibility */ |
18 | digit *grid; /* o^2, indexed by x and y: for final deductions */ |
19 | |
20 | unsigned char *row; /* o^2: row[y*cr+n-1] TRUE if n is in row y */ |
21 | unsigned char *col; /* o^2: col[x*cr+n-1] TRUE if n is in col x */ |
22 | }; |
23 | #define cubepos(x,y,n) (((x)*solver->o+(y))*solver->o+(n)-1) |
24 | #define cube(x,y,n) (solver->cube[cubepos(x,y,n)]) |
25 | |
26 | #define gridpos(x,y) ((y)*solver->o+(x)) |
27 | #define grid(x,y) (solver->grid[gridpos(x,y)]) |
28 | |
29 | /* A solo solver using this code would need these defined. See solo.c. */ |
30 | #ifndef YTRANS |
31 | #define YTRANS(y) (y) |
32 | #endif |
33 | #ifndef YUNTRANS |
34 | #define YUNTRANS(y) (y) |
35 | #endif |
36 | |
37 | |
38 | /* --- Solver individual strategies --- */ |
39 | |
40 | /* Place a value at a specific location. */ |
41 | void latin_solver_place(struct latin_solver *solver, int x, int y, int n); |
42 | |
43 | /* Positional elimination. */ |
44 | int latin_solver_elim(struct latin_solver *solver, int start, int step |
45 | #ifdef STANDALONE_SOLVER |
46 | , char *fmt, ... |
47 | #endif |
48 | ); |
49 | |
50 | struct latin_solver_scratch; /* private to latin.c */ |
51 | /* Set elimination */ |
52 | int latin_solver_set(struct latin_solver *solver, |
53 | struct latin_solver_scratch *scratch, |
54 | int start, int step1, int step2 |
55 | #ifdef STANDALONE_SOLVER |
56 | , char *fmt, ... |
57 | #endif |
58 | ); |
59 | |
60 | /* Forcing chains */ |
61 | int latin_solver_forcing(struct latin_solver *solver, |
62 | struct latin_solver_scratch *scratch); |
63 | |
64 | |
65 | /* --- Solver allocation --- */ |
66 | |
67 | /* Fills in (and allocates members for) a latin_solver struct. |
68 | * Will allocate members of snew, but not snew itself |
69 | * (allowing 'struct latin_solver' to be the first element in a larger |
70 | * struct, for example). */ |
71 | void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o); |
72 | void latin_solver_free(struct latin_solver *solver); |
73 | |
74 | /* Allocates scratch space (for _set and _forcing) */ |
75 | struct latin_solver_scratch * |
76 | latin_solver_new_scratch(struct latin_solver *solver); |
77 | void latin_solver_free_scratch(struct latin_solver_scratch *scratch); |
78 | |
79 | |
80 | /* --- Solver guts --- */ |
81 | |
82 | /* Looped positional elimination */ |
83 | int latin_solver_diff_simple(struct latin_solver *solver); |
84 | |
85 | /* Looped set elimination; *extreme is set if it used |
86 | * the more difficult single-number elimination. */ |
87 | int latin_solver_diff_set(struct latin_solver *solver, |
88 | struct latin_solver_scratch *scratch, |
481628b3 |
89 | int extreme); |
149255d7 |
90 | |
388b2f00 |
91 | typedef int (*usersolver_t)(struct latin_solver *solver, void *ctx); |
92 | typedef void *(*ctxnew_t)(void *ctx); |
93 | typedef void (*ctxfree_t)(void *ctx); |
149255d7 |
94 | |
95 | /* Individual puzzles should use their enumerations for their |
96 | * own difficulty levels, ensuring they don't clash with these. */ |
97 | enum { diff_impossible = 10, diff_ambiguous, diff_unfinished }; |
388b2f00 |
98 | |
99 | /* Externally callable function that allocates and frees a latin_solver */ |
100 | int latin_solver(digit *grid, int o, int maxdiff, |
101 | int diff_simple, int diff_set_0, int diff_set_1, |
102 | int diff_forcing, int diff_recursive, |
103 | usersolver_t const *usersolvers, void *ctx, |
104 | ctxnew_t ctxnew, ctxfree_t ctxfree); |
105 | |
106 | /* Version you can call if you want to alloc and free latin_solver yourself */ |
107 | int latin_solver_main(struct latin_solver *solver, int maxdiff, |
108 | int diff_simple, int diff_set_0, int diff_set_1, |
109 | int diff_forcing, int diff_recursive, |
110 | usersolver_t const *usersolvers, void *ctx, |
111 | ctxnew_t ctxnew, ctxfree_t ctxfree); |
149255d7 |
112 | |
113 | void latin_solver_debug(unsigned char *cube, int o); |
114 | |
115 | /* --- Generation and checking --- */ |
116 | |
149255d7 |
117 | digit *latin_generate(int o, random_state *rs); |
118 | |
119 | int latin_check(digit *sq, int order); /* !0 => not a latin square */ |
120 | |
121 | void latin_debug(digit *sq, int order); |
122 | |
123 | #endif |