[sgt/puzzles] / latin.h

#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
Commit	Line	Data
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[ycr+n-1] TRUE if n is in row y /
	21	unsigned char col; / o^2: col[xcr+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);
149255d7	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