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