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#ifndef LATIN_H
2#define LATIN_H
3
4#include "puzzles.h"
5
6typedef unsigned char digit;
7
8/* --- Solver structures, definitions --- */
9
10#ifdef STANDALONE_SOLVER
11extern int solver_show_working, solver_recurse_depth;
12#endif
13
14struct 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#ifdef STANDALONE_SOLVER
24 char **names; /* o: names[n-1] gives name of 'digit' n */
25#endif
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
34/* --- Solver individual strategies --- */
35
36/* Place a value at a specific location. */
37void latin_solver_place(struct latin_solver *solver, int x, int y, int n);
38
39/* Positional elimination. */
40int latin_solver_elim(struct latin_solver *solver, int start, int step
41#ifdef STANDALONE_SOLVER
42 , const char *fmt, ...
43#endif
44 );
45
46struct latin_solver_scratch; /* private to latin.c */
47/* Set elimination */
48int 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 , const char *fmt, ...
53#endif
54 );
55
56/* Forcing chains */
57int 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 solver, but not solver itself
65 * (allowing 'struct latin_solver' to be the first element in a larger
66 * struct, for example).
67 *
68 * latin_solver_alloc returns false if the digits already in the grid
69 * could not be legally placed. */
70bool latin_solver_alloc(struct latin_solver *solver, digit *grid, int o);
71void latin_solver_free(struct latin_solver *solver);
72
73/* Allocates scratch space (for _set and _forcing) */
74struct latin_solver_scratch *
75 latin_solver_new_scratch(struct latin_solver *solver);
76void latin_solver_free_scratch(struct latin_solver_scratch *scratch);
77
78
79/* --- Solver guts --- */
80
81/* Looped positional elimination */
82int latin_solver_diff_simple(struct latin_solver *solver);
83
84/* Looped set elimination; extreme permits use of the more difficult
85 * single-number elimination. */
86int latin_solver_diff_set(struct latin_solver *solver,
87 struct latin_solver_scratch *scratch,
88 bool extreme);
89
90typedef int (*usersolver_t)(struct latin_solver *solver, void *ctx);
91typedef bool (*validator_t)(struct latin_solver *solver, void *ctx);
92typedef void *(*ctxnew_t)(void *ctx);
93typedef void (*ctxfree_t)(void *ctx);
94
95/* Individual puzzles should use their enumerations for their
96 * own difficulty levels, ensuring they don't clash with these. */
97enum { diff_impossible = 10, diff_ambiguous, diff_unfinished };
98
99/* Externally callable function that allocates and frees a latin_solver */
100int 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, validator_t valid,
104 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree);
105
106/* Version you can call if you want to alloc and free latin_solver yourself */
107int 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, validator_t valid,
111 void *ctx, ctxnew_t ctxnew, ctxfree_t ctxfree);
112
113void latin_solver_debug(unsigned char *cube, int o);
114
115/* --- Generation and checking --- */
116
117digit *latin_generate(int o, random_state *rs);
118
119/* The order of the latin rectangle is max(w,h). */
120digit *latin_generate_rect(int w, int h, random_state *rs);
121
122bool latin_check(digit *sq, int order); /* true => not a latin square */
123
124void latin_debug(digit *sq, int order);
125
126#endif