latin.h

   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 #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,
  89                           int extreme);
  90
  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);
  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 };
  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);
 112
 113 void latin_solver_debug(unsigned char *cube, int o);
 114
 115 /* --- Generation and checking --- */
 116
 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