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