[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)])

/* A solo solver using this code would need these defined. See solo.c. */
#ifndef YTRANS
#define YTRANS(y) (y)
#endif
#ifndef YUNTRANS
#define YUNTRANS(y) (y)
#endif


/* --- 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);

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