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 #ifdef STANDALONE_SOLVER
  24   char **names;         /* o: names[n-1] gives name of 'digit' n */
  25 #endif
  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
  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,
  85                           int extreme);
  86
  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);
  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 };
  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);
 108
 109 void latin_solver_debug(unsigned char *cube, int o);
 110
 111 /* --- Generation and checking --- */
 112
 113 digit *latin_generate(int o, random_state *rs);
 114
 115 /* The order of the latin rectangle is max(w,h). */
 116 digit *latin_generate_rect(int w, int h, random_state *rs);
 117
 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