diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/latin.h | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/latin.h')
-rw-r--r-- | apps/plugins/puzzles/latin.h | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/latin.h b/apps/plugins/puzzles/latin.h new file mode 100644 index 0000000000..4b09f16ce1 --- /dev/null +++ b/apps/plugins/puzzles/latin.h | |||
@@ -0,0 +1,122 @@ | |||
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 | ||
11 | extern int solver_show_working, solver_recurse_depth; | ||
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 | #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. */ | ||
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, | ||
85 | int extreme); | ||
86 | |||
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); | ||
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 }; | ||
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); | ||
108 | |||
109 | void latin_solver_debug(unsigned char *cube, int o); | ||
110 | |||
111 | /* --- Generation and checking --- */ | ||
112 | |||
113 | digit *latin_generate(int o, random_state *rs); | ||
114 | |||
115 | /* The order of the latin rectangle is max(w,h). */ | ||
116 | digit *latin_generate_rect(int w, int h, random_state *rs); | ||
117 | |||
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 | ||