From 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sun, 20 Nov 2016 15:16:41 -0500 Subject: 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 --- apps/plugins/puzzles/latin.h | 122 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 122 insertions(+) create mode 100644 apps/plugins/puzzles/latin.h (limited to 'apps/plugins/puzzles/latin.h') 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 @@ +#ifndef LATIN_H +#define LATIN_H + +#include "puzzles.h" + +typedef unsigned char digit; + +/* --- Solver structures, definitions --- */ + +#ifdef STANDALONE_SOLVER +extern int solver_show_working, solver_recurse_depth; +#endif + +struct latin_solver { + int o; /* order of latin square */ + unsigned char *cube; /* o^3, indexed by x, y, and digit: + TRUE in that position indicates a possibility */ + digit *grid; /* o^2, indexed by x and y: for final deductions */ + + unsigned char *row; /* o^2: row[y*cr+n-1] TRUE if n is in row y */ + unsigned char *col; /* o^2: col[x*cr+n-1] TRUE if n is in col x */ + +#ifdef STANDALONE_SOLVER + char **names; /* o: names[n-1] gives name of 'digit' n */ +#endif +}; +#define cubepos(x,y,n) (((x)*solver->o+(y))*solver->o+(n)-1) +#define cube(x,y,n) (solver->cube[cubepos(x,y,n)]) + +#define gridpos(x,y) ((y)*solver->o+(x)) +#define grid(x,y) (solver->grid[gridpos(x,y)]) + + +/* --- Solver individual strategies --- */ + +/* Place a value at a specific location. */ +void latin_solver_place(struct latin_solver *solver, int x, int y, int n); + +/* Positional elimination. */ +int latin_solver_elim(struct latin_solver *solver, int start, int step +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ); + +struct latin_solver_scratch; /* private to latin.c */ +/* Set elimination */ +int latin_solver_set(struct latin_solver *solver, + struct latin_solver_scratch *scratch, + int start, int step1, int step2 +#ifdef STANDALONE_SOLVER + , char *fmt, ... +#endif + ); + +/* Forcing chains */ +int latin_solver_forcing(struct latin_solver *solver, + struct latin_solver_scratch *scratch); + + +/* --- Solver allocation --- */ + +/* Fills in (and allocates members for) a latin_solver struct. + * Will allocate members of snew, but not snew itself + * (allowing 'struct latin_solver' to be the first element in a larger + * struct, for example). */ +void latin_solver_alloc(struct latin_solver *solver, digit *grid, int o); +void latin_solver_free(struct latin_solver *solver); + +/* Allocates scratch space (for _set and _forcing) */ +struct latin_solver_scratch * + latin_solver_new_scratch(struct latin_solver *solver); +void latin_solver_free_scratch(struct latin_solver_scratch *scratch); + + +/* --- Solver guts --- */ + +/* Looped positional elimination */ +int latin_solver_diff_simple(struct latin_solver *solver); + +/* Looped set elimination; *extreme is set if it used + * the more difficult single-number elimination. */ +int latin_solver_diff_set(struct latin_solver *solver, + struct latin_solver_scratch *scratch, + int extreme); + +typedef int (*usersolver_t)(struct latin_solver *solver, void *ctx); +typedef void *(*ctxnew_t)(void *ctx); +typedef void (*ctxfree_t)(void *ctx); + +/* Individual puzzles should use their enumerations for their + * own difficulty levels, ensuring they don't clash with these. */ +enum { diff_impossible = 10, diff_ambiguous, diff_unfinished }; + +/* Externally callable function that allocates and frees a latin_solver */ +int latin_solver(digit *grid, int o, int maxdiff, + int diff_simple, int diff_set_0, int diff_set_1, + int diff_forcing, int diff_recursive, + usersolver_t const *usersolvers, void *ctx, + ctxnew_t ctxnew, ctxfree_t ctxfree); + +/* Version you can call if you want to alloc and free latin_solver yourself */ +int latin_solver_main(struct latin_solver *solver, int maxdiff, + int diff_simple, int diff_set_0, int diff_set_1, + int diff_forcing, int diff_recursive, + usersolver_t const *usersolvers, void *ctx, + ctxnew_t ctxnew, ctxfree_t ctxfree); + +void latin_solver_debug(unsigned char *cube, int o); + +/* --- Generation and checking --- */ + +digit *latin_generate(int o, random_state *rs); + +/* The order of the latin rectangle is max(w,h). */ +digit *latin_generate_rect(int w, int h, random_state *rs); + +int latin_check(digit *sq, int order); /* !0 => not a latin square */ + +void latin_debug(digit *sq, int order); + +#endif -- cgit v1.2.3