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