/************************************************************************************/ /* */ /* Author: Bill DuPree */ /* Name: sudoku_solver.c */ /* Language: C */ /* Date: Feb. 25, 2006 */ /* Copyright (C) Feb. 25, 2006, All rights reserved. */ /* */ /* This is a program that solves Su Doku (aka Sudoku, Number Place, etc.) puzzles */ /* primarily using deductive logic. It will only resort to trial-and-error and */ /* backtracking approaches upon exhausting all of its deductive moves. */ /* */ /* Puzzles must be of the standard 9x9 variety using the (ASCII) characters '1' */ /* through '9' for the puzzle solution set. Puzzles should be submitted as 81 */ /* character strings which, when read left-to-right will fill a 9x9 Sudoku grid */ /* from left-to-right and top-to-bottom. In the puzzle specification, the */ /* characters 1 - 9 represent the puzzle "givens" or clues. Any other non-blank */ /* character represents an unsolved cell. */ /* */ /* The puzzle solving algorithm is "home grown." I did not borrow any of the usual */ /* techniques from the literature, e.g. Donald Knuth's "Dancing Links." Instead */ /* I "rolled my own" from scratch. As such, its performance can only be blamed */ /* on yours truly. Still, I feel it is quite fast. On a 333 MHz Pentium II Linux */ /* box it solves typical medium force puzzles in approximately 800 microseconds or */ /* about 1,200 puzzles per second, give or take. On an Athlon XP 3000 (Barton core) */ /* it solves about 6,600 puzzles per sec. */ /* */ /* DESCRIPTION OF ALGORITHM: */ /* */ /* The puzzle algorithm initially assumes every unsolved cell can assume every */ /* possible value. It then uses the placement of the givens to refine the choices */ /* available to each cell. I call this the markup phase. */ /* */ /* After markup completes, the algorithm then looks for "singleton" cells with */ /* values that, due to constraints imposed by the row, column, or 3x3 region, may */ /* only assume one possible value. Once these cells are assigned values, the */ /* algorithm returns to the markup phase to apply these changes to the remaining */ /* candidate solutions. The markup/singleton phases alternate until either no more */ /* changes occur, or the puzzle is solved. I call the markup/singleton elimination */ /* loop the "Simple Solver" because in a large percentage of cases it solves the */ /* puzzle. */ /* */ /* If the simple solver portion of the algorithm doesn't produce a solution, then */ /* more advanced deductive rules are applied. I've implemented two additional rules */ /* as part of the deductive puzzle solver. The first is subset elimination wherein */ /* a row/column/region is scanned for X number of cells with X number of matching */ /* candidate solutions. If such subsets are found in the row, column, or region, */ /* then the candidates values from the subset may be eliminated from all other */ /* unsolved cells within the row, column, or region, respectively. */ /* */ /* The second advanced deductive rule examines each region looking for candidate */ /* values that exclusively align themselves along a single row or column, i.e. a */ /* a vector. If such candidate values are found, then they may be eliminated from */ /* the cells outside of the region that are part of the aligned row or column. */ /* */ /* Note that each of the advanced deductive rules calls all preceeding rules, in */ /* order, if that advanced rule has effected a change in puzzle markup. */ /* */ /* Finally, if no solution is found after iteratively applying all deductive rules, */ /* then we begin trial-and-error using recursion for backtracking. A working copy */ /* is created from our puzzle, and using this copy the first cell with the */ /* smallest number of candidate solutions is chosen. One of the solutions values is */ /* assigned to that cell, and the solver algorithm is called using this working */ /* copy as its starting point. Eventually, either a solution, or an impasse is */ /* reached. */ /* */ /* If we reach an impasse, the recursion unwinds and the next trial solution is */ /* attempted. If a solution is found (at any point) the values for the solution are */ /* added to a list. Again, so long as we are examining all possibilities, the */ /* recursion unwinds so that the next trial may be attempted. It is in this manner */ /* that we enumerate puzzles with multiple solutions. */ /* */ /* Note that it is certainly possible to add to the list of applied deductive */ /* rules. The techniques known as "X-Wing" and "Swordfish" come to mind. On the */ /* other hand, adding these additional rules will, in all likelihood, slow the */ /* solver down by adding to the computational burden while producing very few */ /* results. I've seen the law of diminishing returns even in some of the existing */ /* rules, e.g. in subset elimination I only look at two and three valued subsets */ /* because taking it any further than that degraded performance. */ /* */ /* PROGRAM INVOCATION: */ /* */ /* This program is a console (or command line) based utility and has the following */ /* usage: */ /* */ /* sudoku_solver {-p puzzle | -f } [-o ] */ /* [-r ] [-1][-a][-c][-g][-l][-m][-n][-s] */ /* */ /* where: */ /* */ /* -1 Search for first solution, otherwise all solutions are returned */ /* -a Requests that the answer (solution) be printed */ /* -c Print a count of solutions for each puzzle */ /* -d Print the recursive trial depth required to solve the puzzle */ /* -e Print a step-by-step explanation of the solution(s) */ /* -f Takes an argument which specifes an input file */ /* containing one or more unsolved puzzles (default: stdin) */ /* -G Print the puzzle solution(s) in a 9x9 grid format */ /* -g Print the number of given clues */ /* -l Print the recursive trial depth required to solve the puzzle */ /* -m Print an octal mask for the puzzle givens */ /* -n Number each result */ /* -o Specifies an output file for the solutions (default: stdout) */ /* -p Takes an argument giving a single inline puzzle to be solved */ /* -r Specifies an output file for unsolvable puzzles */ /* (default: stderr) */ /* -s Print the puzzle's score or difficulty rating */ /* -? Print usage information */ /* */ /* The return code is zero if all puzzles had unique solutions, */ /* (or have one or more solutions when -1 is specified) and non-zero */ /* when no unique solution exists. */ /* */ /* PUZZLE SCORING */ /* */ /* A word about puzzle scoring, i.e. rating a puzzle's difficulty, is in order. */ /* Rating Sudoku puzzles is a rather subjective thing, and thus it is difficult to */ /* really develop an objective puzzle rating system. I, however, have attempted */ /* this feat (several times with varying degrees of success ;-) and I think the */ /* heuristics I'm currently applying aren't too bad for rating the relative */ /* difficulty of solving a puzzle. */ /* */ /* The following is a brief rundown of how it works. The initial puzzle markup is */ /* a "free" operation, i.e. no points are scored for the first markup pass. I feel */ /* this is appropriate because a person solving a puzzle will always have to do */ /* their own eyeballing and scanning of the puzzle. Subsequent passes are */ /* scored at one point per candidate eliminated because these passes indicate */ /* that more deductive work is required. Secondly, the "reward" for solving a cell */ /* is set to one point, and as long as the solution only requires simple markup */ /* and elimination of singletons, this level of reward remains unchanged. */ /* */ /* This reward changes, however, when advanced solving rules are required. Puzzles */ /* that remain unsolved after the first pass through the simple solver phase have */ /* a higher "reward", i.e. it is incremented by two. Thus, if subset or vector */ /* elimination is required, all subsequently solved cells score higher bounties. */ /* In addition, the successful application of these deductive techniques score */ /* their own penalties. */ /* */ /* Finally, if a trial-and-error approach is called for, then the "reward" is */ /* incremented by another five points. Thus, the total penalty for each level of */ /* recursion is an additional seven points per solved cell, i.e. */ /* (recursive_depth * 7) + 1 points per solved cell. Trial solutions are also */ /* penalized by a weighting factor that is based upon the number of unsolved cells */ /* that remain upon reentry to the solver and the depth of recursion. (I've seen a */ /* pathological puzzle from the "Minimum Sudoku" web site require 16 levels of */ /* recursion and score a whopping 228,642 points using this scoring system!) */ /* */ /* And that brings me to this topic: What do all these points mean? */ /* */ /* Well, who knows? This is still subjective, and the weighting system I've chosen */ /* for point scoring is is largely arbitrary. But based upon feedback from a number */ /* of individuals, a rough scale of difficulty plays out as follows: */ /* */ /* DEGREE OF DIFFICULTY | SCORE */ /* -------------------------+------------------------------------------ */ /* TRIVIAL | 80 points or less */ /* EASY | 81 - 150 points */ /* MEDIUM | 151 - 250 points */ /* HARD | 251 - 400 points */ /* VERY HARD | 401 - 900 points */ /* DIABOLICAL | 901 and up */ /* */ /* Experience shows that puzzles in the HARD category, in a few cases, will */ /* require a small amount of trial-and-error. The VERY HARD puzzles will likely */ /* require trial-and-error, and in some cases more than one level of trial-and- */ /* error. As for the DIABOLICAL puzzles--why waste your time? These are best left */ /* to masochists, savants and automated solvers. YMMV. */ /* */ /* LICENSE: */ /* */ /* This program is free software; you can redistribute it and/or modify */ /* it under the terms of the GNU General Public License as published by */ /* the Free Software Foundation; either version 2 of the License, or */ /* (at your option) any later version. */ /* */ /* This program is distributed in the hope that it will be useful, */ /* but WITHOUT ANY WARRANTY; without even the implied warranty of */ /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */ /* GNU General Public License for more details. */ /* */ /* You should have received a copy of the GNU General Public License */ /* along with this program; if not, write to the Free Software */ /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ /* */ /* CONTACT: */ /* */ /* Email: bdupree@techfinesse.com */ /* Post: Bill DuPree, 609 Wenonah Ave, Oak Park, IL 60304 USA */ /* */ /************************************************************************************/ /* */ /* CHANGE LOG: */ /* */ /* Rev. Date Init. Description */ /* -------------------------------------------------------------------------------- */ /* 1.00 2006-02-25 WD Initial version. */ /* 1.01 2006-03-13 WD Fixed return code calc. Added signon message. */ /* 1.10 2006-03-20 WD Added explain option, add'l speed optimizations */ /* 1.11 2006-03-23 WD More simple speed optimizations, cleanup, bug fixes */ /* */ /************************************************************************************/ #include #include #include #include #include #include #define VERSION "1.11" #define PUZZLE_ORDER 3 #define PUZZLE_DIM (PUZZLE_ORDER*PUZZLE_ORDER) #define PUZZLE_CELLS (PUZZLE_DIM*PUZZLE_DIM) /* Command line options */ #ifdef EXPLAIN #define OPTIONS "?1acdef:Ggmno:p:r:s" #else #define OPTIONS "?1acdf:Ggmno:p:r:s" #endif extern char *optarg; extern int optind, opterr, optopt; static char *myname; /* Name that we were invoked under */ static FILE *solnfile, *rejects; /* This is the list of cell coordinates specified on a row basis */ static int const row[PUZZLE_DIM][PUZZLE_DIM] = { { 0, 1, 2, 3, 4, 5, 6, 7, 8 }, { 9, 10, 11, 12, 13, 14, 15, 16, 17 }, { 18, 19, 20, 21, 22, 23, 24, 25, 26 }, { 27, 28, 29, 30, 31, 32, 33, 34, 35 }, { 36, 37, 38, 39, 40, 41, 42, 43, 44 }, { 45, 46, 47, 48, 49, 50, 51, 52, 53 }, { 54, 55, 56, 57, 58, 59, 60, 61, 62 }, { 63, 64, 65, 66, 67, 68, 69, 70, 71 }, { 72, 73, 74, 75, 76, 77, 78, 79, 80 }}; /* This is the list of cell coordinates specified on a column basis */ static int const col[PUZZLE_DIM][PUZZLE_DIM] = { { 0, 9, 18, 27, 36, 45, 54, 63, 72 }, { 1, 10, 19, 28, 37, 46, 55, 64, 73 }, { 2, 11, 20, 29, 38, 47, 56, 65, 74 }, { 3, 12, 21, 30, 39, 48, 57, 66, 75 }, { 4, 13, 22, 31, 40, 49, 58, 67, 76 }, { 5, 14, 23, 32, 41, 50, 59, 68, 77 }, { 6, 15, 24, 33, 42, 51, 60, 69, 78 }, { 7, 16, 25, 34, 43, 52, 61, 70, 79 }, { 8, 17, 26, 35, 44, 53, 62, 71, 80 }}; /* This is the list of cell coordinates specified on a 3x3 region basis */ static int const region[PUZZLE_DIM][PUZZLE_DIM] = { { 0, 1, 2, 9, 10, 11, 18, 19, 20 }, { 3, 4, 5, 12, 13, 14, 21, 22, 23 }, { 6, 7, 8, 15, 16, 17, 24, 25, 26 }, { 27, 28, 29, 36, 37, 38, 45, 46, 47 }, { 30, 31, 32, 39, 40, 41, 48, 49, 50 }, { 33, 34, 35, 42, 43, 44, 51, 52, 53 }, { 54, 55, 56, 63, 64, 65, 72, 73, 74 }, { 57, 58, 59, 66, 67, 68, 75, 76, 77 }, { 60, 61, 62, 69, 70, 71, 78, 79, 80 }}; /* Flags for cellflags member */ #define GIVEN 1 #define FOUND 2 #define STUCK 3 /* Return codes for funcs that modify puzzle markup */ #define NOCHANGE 0 #define CHANGE 1 typedef struct grd { short cellflags[PUZZLE_CELLS]; short solved[PUZZLE_CELLS]; short cell[PUZZLE_CELLS]; short tail, givens, exposed, maxlvl, inc, reward; unsigned int score, solncount; struct grd *next; } grid; typedef int (*return_soln)(grid *g); static grid *soln_list = NULL; typedef struct { short row, col, region; } cellmap; /* Array structure to help map cell index back to row, column, and region */ static cellmap const map[PUZZLE_CELLS] = { { 0, 0, 0 }, { 0, 1, 0 }, { 0, 2, 0 }, { 0, 3, 1 }, { 0, 4, 1 }, { 0, 5, 1 }, { 0, 6, 2 }, { 0, 7, 2 }, { 0, 8, 2 }, { 1, 0, 0 }, { 1, 1, 0 }, { 1, 2, 0 }, { 1, 3, 1 }, { 1, 4, 1 }, { 1, 5, 1 }, { 1, 6, 2 }, { 1, 7, 2 }, { 1, 8, 2 }, { 2, 0, 0 }, { 2, 1, 0 }, { 2, 2, 0 }, { 2, 3, 1 }, { 2, 4, 1 }, { 2, 5, 1 }, { 2, 6, 2 }, { 2, 7, 2 }, { 2, 8, 2 }, { 3, 0, 3 }, { 3, 1, 3 }, { 3, 2, 3 }, { 3, 3, 4 }, { 3, 4, 4 }, { 3, 5, 4 }, { 3, 6, 5 }, { 3, 7, 5 }, { 3, 8, 5 }, { 4, 0, 3 }, { 4, 1, 3 }, { 4, 2, 3 }, { 4, 3, 4 }, { 4, 4, 4 }, { 4, 5, 4 }, { 4, 6, 5 }, { 4, 7, 5 }, { 4, 8, 5 }, { 5, 0, 3 }, { 5, 1, 3 }, { 5, 2, 3 }, { 5, 3, 4 }, { 5, 4, 4 }, { 5, 5, 4 }, { 5, 6, 5 }, { 5, 7, 5 }, { 5, 8, 5 }, { 6, 0, 6 }, { 6, 1, 6 }, { 6, 2, 6 }, { 6, 3, 7 }, { 6, 4, 7 }, { 6, 5, 7 }, { 6, 6, 8 }, { 6, 7, 8 }, { 6, 8, 8 }, { 7, 0, 6 }, { 7, 1, 6 }, { 7, 2, 6 }, { 7, 3, 7 }, { 7, 4, 7 }, { 7, 5, 7 }, { 7, 6, 8 }, { 7, 7, 8 }, { 7, 8, 8 }, { 8, 0, 6 }, { 8, 1, 6 }, { 8, 2, 6 }, { 8, 3, 7 }, { 8, 4, 7 }, { 8, 5, 7 }, { 8, 6, 8 }, { 8, 7, 8 }, { 8, 8, 8 } }; static const short symtab[1<= '1') && (c <= '9'); } #if defined(DEBUG) static void mypause() { char buf[8]; printf("\tPress enter -> "); fgets(buf, 8, stdin); } #endif #if 0 /* Generic (and slow) bitcount function */ static int bitcount(short cell) { int i, count, mask; mask = 1; for (i = count = 0; i < 16; i++) { if (mask & cell) count++; mask <<= 1; } return count; } #endif /*****************************************************/ /* Return the number of '1' bits in a cell. */ /* Rather than count bits, do a quick table lookup. */ /* Warning: Only valid for 9 low order bits. */ /*****************************************************/ static inline short bitcount(short cell) { static const short bcounts[512] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9}; return bcounts[cell]; } #ifdef EXPLAIN /**************************************************/ /* Indent two spaces for each level of recursion. */ /**************************************************/ static inline void explain_indent(FILE *h) { int i; for (i = 0; i < lvl-1; i++) fprintf(h, " "); } /******************************************************************/ /* Construct a string representing the possible values a cell may */ /* contain according to current markup. */ /******************************************************************/ static char *clues(short cell) { int i, m, multi, mask; static char buf[64], *p; multi = m = bitcount(cell); if (!multi) return "NULL"; if (multi > 1) { strcpy(buf, "tuple ("); } else { strcpy(buf, "value "); } p = buf + strlen(buf); for (mask = i = 1; i <= PUZZLE_DIM; i++) { if (mask & cell) { *p++ = symtab[mask]; multi -= 1; if (multi) { *p++ = ','; *p++ = ' '; } } mask <<= 1; } if (m > 1) *p++ = ')'; *p = 0; return buf; } /*************************************************************/ /* Explain removal of a candidate value from a changed cell. */ /*************************************************************/ static void explain_markup_elim(grid *g, int chgd, int clue) { int chgd_row, chgd_col, clue_row, clue_col; chgd_row = map[chgd].row+1; chgd_col = map[chgd].col+1; clue_row = map[clue].row+1; clue_col = map[clue].col+1; explain_indent(solnfile); fprintf(solnfile, "Candidate %s removed from row %d, col %d because of cell at row %d, col %d\n", clues(g->cell[clue]), chgd_row, chgd_col, clue_row, clue_col); } /*****************************************/ /* Dump the state of the current markup. */ /*****************************************/ static void explain_current_markup(grid *g) { if (g->exposed >= PUZZLE_CELLS) return; fprintf(solnfile, "\n"); explain_indent(solnfile); fprintf(solnfile, "Current markup is as follows:"); diagnostic_grid(g, solnfile); fprintf(solnfile, "\n"); } /****************************************/ /* Explain the solving of a given cell. */ /****************************************/ static void explain_solve_cell(grid *g, int chgd) { int chgd_row, chgd_col; chgd_row = map[chgd].row+1; chgd_col = map[chgd].col+1; explain_indent(solnfile); fprintf(solnfile, "Cell at row %d, col %d solved with %s\n", chgd_row, chgd_col, clues(g->cell[chgd])); } /******************************************************************/ /* Explain the current impasse reached during markup elimination. */ /******************************************************************/ static void explain_markup_impasse(grid *g, int chgd, int clue) { int chgd_row, chgd_col, clue_row, clue_col; chgd_row = map[chgd].row+1; chgd_col = map[chgd].col+1; clue_row = map[clue].row+1; clue_col = map[clue].col+1; explain_indent(solnfile); fprintf(solnfile, "Impasse for cell at row %d, col %d because cell at row %d, col %d removes last candidate\n", chgd_row, chgd_col, clue_row, clue_col); explain_current_markup(g); } /****************************************/ /* Explain naked and/or hidden singles. */ /****************************************/ static void explain_singleton(grid *g, int chgd, int mask, char *vdesc) { int chgd_row, chgd_col, chgd_reg; chgd_row = map[chgd].row+1; chgd_col = map[chgd].col+1; chgd_reg = map[chgd].region+1; explain_indent(solnfile); fprintf(solnfile, "Cell of region %d at row %d, col %d will only solve for %s in this %s\n", chgd_reg, chgd_row, chgd_col, clues(mask), vdesc); explain_solve_cell(g, chgd); } /*********************************/ /* Explain initial puzzle state. */ /*********************************/ static void explain_markup() { fprintf(solnfile, "\n"); explain_indent(solnfile); fprintf(solnfile, "Assume all cells may contain any values in the range: [1 - 9]\n"); } /************************/ /* Explain given clues. */ /************************/ static void explain_given(int cell, char val) { int cell_row, cell_col; cell_row = map[cell].row+1; cell_col = map[cell].col+1; explain_indent(solnfile); fprintf(solnfile, "Cell at row %d, col %d is given clue value %c\n", cell_row, cell_col, val); } /*******************************************/ /* Explain region/row/column interactions. */ /*******************************************/ static void explain_vector_elim(char *desc, int i, int cell, int val, int region) { int cell_row, cell_col; cell_row = map[cell].row+1; cell_col = map[cell].col+1; explain_indent(solnfile); fprintf(solnfile, "Candidate %s removed from cell at row %d, col %d because it aligns along %s %d in region %d\n", clues(val), cell_row, cell_col, desc, i+1, region+1); } /******************************************************************/ /* Explain the current impasse reached during vector elimination. */ /******************************************************************/ static void explain_vector_impasse(grid *g, char *desc, int i, int cell, int val, int region) { int cell_row, cell_col; cell_row = map[cell].row+1; cell_col = map[cell].col+1; explain_indent(solnfile); fprintf(solnfile, "Impasse at cell at row %d, col %d because candidate %s aligns along %s %d in region %d\n", cell_row, cell_col, clues(val), desc, i+1, region+1); explain_current_markup(g); } /*****************************************************************/ /* Explain the current impasse reached during tuple elimination. */ /*****************************************************************/ static void explain_tuple_impasse(grid *g, char *desc, int elt, int tuple, int count, int bits) { explain_indent(solnfile); fprintf(solnfile, "Impasse in %s %d because too many (%d) cells have %d-valued %s\n", desc, elt+1, count, bits, clues(tuple)); explain_current_markup(g); } /*********************************************************************/ /* Explain the removal of a tuple of candidate solutions from a cell */ /*********************************************************************/ static void explain_tuple_elim(char *desc, int elt, int tuple, int cell) { explain_indent(solnfile); fprintf(solnfile, "Values of %s in %s %d removed from cell at row %d, col %d\n", clues(tuple), desc, elt+1, map[cell].row+1, map[cell].col+1); } /**************************************************/ /* Indicate that a viable solution has been found */ /**************************************************/ static void explain_soln_found(grid *g) { char buf[90]; fprintf(solnfile, "\n"); explain_indent(solnfile); fprintf(solnfile, "Solution found: %s\n", format_answer(g, buf)); print_grid(buf, solnfile); fprintf(solnfile, "\n"); } /***************************/ /* Show the initial puzzle */ /***************************/ static void explain_grid(grid *g) { char buf[90]; fprintf(solnfile, "Initial puzzle: %s\n", format_answer(g, buf)); print_grid(buf, solnfile); explain_current_markup(g); fprintf(solnfile, "\n"); } /*************************************************/ /* Explain attempt at a trial and error solution */ /*************************************************/ static void explain_trial(int cell, int value) { explain_indent(solnfile); fprintf(solnfile, "Attempt trial where cell at row %d, col %d is assigned value %s\n", map[cell].row+1, map[cell].col+1, clues(value)); } /**********************************************/ /* Explain back out of current trial solution */ /**********************************************/ static void explain_backtrack() { if (lvl <= 1) return; explain_indent(solnfile); fprintf(solnfile, "Backtracking\n\n"); } #define EXPLAIN_MARKUP if (explain) explain_markup() #define EXPLAIN_CURRENT_MARKUP(g) if (explain) explain_current_markup((g)) #define EXPLAIN_GIVEN(cell, val) if (explain) explain_given((cell), (val)) #define EXPLAIN_MARKUP_ELIM(g, chgd, clue) if (explain) explain_markup_elim((g), (chgd), (clue)) #define EXPLAIN_MARKUP_SOLVE(g, cell) if (explain) explain_solve_cell((g), (cell)) #define EXPLAIN_MARKUP_IMPASSE(g, chgd, clue) if (explain) explain_markup_impasse((g), (chgd), (clue)) #define EXPLAIN_SINGLETON(g, chgd, mask, vdesc) if (explain) explain_singleton((g), (chgd), (mask), (vdesc)) #define EXPLAIN_VECTOR_ELIM(desc, i, cell, v, r) if (explain) explain_vector_elim((desc), (i), (cell), (v), (r)) #define EXPLAIN_VECTOR_IMPASSE(g, desc, i, cell, v, r) if (explain) explain_vector_impasse((g), (desc), (i), (cell), (v), (r)) #define EXPLAIN_VECTOR_SOLVE(g, cell) if (explain) explain_solve_cell((g), (cell)) #define EXPLAIN_TUPLE_IMPASSE(g, desc, j, c, count, i) if (explain) explain_tuple_impasse((g), (desc), (j), (c), (count), (i)) #define EXPLAIN_TUPLE_ELIM(desc, j, c, cell) if (explain) explain_tuple_elim((desc), (j), (c), (cell)) #define EXPLAIN_TUPLE_SOLVE(g, cell) if (explain) explain_solve_cell((g), (cell)) #define EXPLAIN_SOLN_FOUND(g) if (explain) explain_soln_found((g)); #define EXPLAIN_GRID(g) if (explain) explain_grid((g)); #define EXPLAIN_TRIAL(cell, val) if (explain) explain_trial((cell), (val)); #define EXPLAIN_BACKTRACK if (explain) explain_backtrack(); #define EXPLAIN_INDENT(h) if (explain) explain_indent((h)) #else #define EXPLAIN_MARKUP #define EXPLAIN_CURRENT_MARKUP(g) #define EXPLAIN_GIVEN(cell, val) #define EXPLAIN_MARKUP_ELIM(g, chgd, clue) #define EXPLAIN_MARKUP_SOLVE(g, cell) #define EXPLAIN_MARKUP_IMPASSE(g, chgd, clue) #define EXPLAIN_SINGLETON(g, chgd, mask, vdesc); #define EXPLAIN_VECTOR_ELIM(desc, i, cell, v, r) #define EXPLAIN_VECTOR_IMPASSE(g, desc, i, cell, v, r) #define EXPLAIN_VECTOR_SOLVE(g, cell) #define EXPLAIN_TUPLE_IMPASSE(g, desc, j, c, count, i) #define EXPLAIN_TUPLE_ELIM(desc, j, c, cell) #define EXPLAIN_TUPLE_SOLVE(g, cell) #define EXPLAIN_SOLN_FOUND(g) #define EXPLAIN_GRID(g) #define EXPLAIN_TRIAL(cell, val) #define EXPLAIN_BACKTRACK #define EXPLAIN_INDENT(h) #endif /*****************************************************/ /* Initialize a grid to an empty state. */ /* At the start, all cells can have any value */ /* so set all 9 lower order bits in each cell. */ /* In effect, the 9x9 grid now has markup that */ /* specifies that each cell can assume any value */ /* of 1 through 9. */ /*****************************************************/ static void init_grid(grid *g) { int i; for (i = 0; i < PUZZLE_CELLS; i++) g->cell[i] = 0x01ff; memset(g->cellflags, 0, PUZZLE_CELLS*sizeof(g->cellflags[0])); g->exposed = 0; g->givens = 0; g->inc = 0; g->maxlvl = 0; g->score = 0; g->solncount = 0; g->reward = 1; g->next = NULL; g->tail = 0; EXPLAIN_MARKUP; } /*****************************************************/ /* Convert a puzzle from the input format, */ /* i.e. a string of 81 non-blank characters */ /* with ASCII digits '1' thru '9' specified */ /* for the givens, and non-numeric characters */ /* for the remaining cells. The string, read */ /* left-to-right fills the 9x9 Sudoku grid */ /* in left-to-right, top-to-bottom order. */ /*****************************************************/ static void cvt_to_grid(grid *g, char *game) { int i; init_grid(g); for (i = 0; i < PUZZLE_CELLS; i++) { if (is_given(game[i])) { /* warning -- ASCII charset assumed */ g->cell[i] = 1 << (game[i] - '1'); g->cellflags[i] = GIVEN; g->givens += 1; g->solved[g->exposed++] = i; EXPLAIN_GIVEN(i, game[i]); } } EXPLAIN_GRID(g); } /****************************************************************/ /* Print the partially solved puzzle and all associated markup */ /* in 9x9 fashion. */ /****************************************************************/ static void diagnostic_grid(grid *g, FILE *h) { int i, j, flag; short c; char line1[40], line2[40], line3[40], cbuf1[5], cbuf2[5], cbuf3[5], outbuf[PUZZLE_CELLS+1]; /* Sanity check */ for (flag = 1, i = 0; flag && i < PUZZLE_CELLS; i++) { if (bitcount(g->cell[i]) != 1) { flag = 0; } } /* Don't need to print grid with diagnostic markup? */ if (flag) { format_answer(g, outbuf); print_grid(outbuf, h); fflush(h); return; } strcpy(cbuf1, " |"); strcpy(cbuf2, cbuf1); strcpy(cbuf3, cbuf1); fprintf(h, "\n"); for (i = 0; i < PUZZLE_DIM; i++) { *line1 = *line2 = *line3 = 0; for (j = 0; j < PUZZLE_DIM; j++) { c = g->cell[row[i][j]]; if (bitcount(c) == 1) { strcpy(cbuf1, " |"); strcpy(cbuf2, cbuf1); strcpy(cbuf3, cbuf1); cbuf2[1] = symtab[c]; } else { if (c & 1) cbuf1[0] = '*'; else cbuf1[0] = '.'; if (c & 2) cbuf1[1] = '*'; else cbuf1[1] = '.'; if (c & 4) cbuf1[2] = '*'; else cbuf1[2] = '.'; if (c & 8) cbuf2[0] = '*'; else cbuf2[0] = '.'; if (c & 16) cbuf2[1] = '*'; else cbuf2[1] = '.'; if (c & 32) cbuf2[2] = '*'; else cbuf2[2] = '.'; if (c & 64) cbuf3[0] = '*'; else cbuf3[0] = '.'; if (c & 128) cbuf3[1] = '*'; else cbuf3[1] = '.'; if (c & 256) cbuf3[2] = '*'; else cbuf3[2] = '.'; } strcat(line1, cbuf1); strcat(line2, cbuf2); strcat(line3, cbuf3); } EXPLAIN_INDENT(h); fprintf(h, "+---+---+---+---+---+---+---+---+---+\n"); EXPLAIN_INDENT(h); fprintf(h, "|%s\n", line1); EXPLAIN_INDENT(h); fprintf(h, "|%s\n", line2); EXPLAIN_INDENT(h); fprintf(h, "|%s\n", line3); } EXPLAIN_INDENT(h); fprintf(h, "+---+---+---+---+---+---+---+---+---+\n"); fflush(h); } /***********************************************************************/ /* Validate that a sudoku grid contains a valid solution. Return 1 if */ /* true, 0 if false. If the verbose argument is non-zero, then print */ /* reasons for invalidating the solution to stderr. */ /***********************************************************************/ static int validate(grid *g, int verbose) { int i, j, regmask, rowmask, colmask, flag = 1; /* Sanity check */ for (i = 0; i < PUZZLE_CELLS; i++) { if (bitcount(g->cell[i]) != 1) { if (verbose) { fprintf(rejects, "Cell %d at row %d, col %d has no unique soln.\n", 1+i, 1+map[i].row, 1+map[i].col); fflush(rejects); flag = 0; } else return 0; } } /* Check rows */ for (i = 0; i < PUZZLE_DIM; i++) { for (rowmask = j = 0; j < PUZZLE_DIM; j++) { if (bitcount(g->cell[row[i][j]]) == 1) rowmask |= g->cell[row[i][j]]; } if (rowmask != 0x01ff) { if (verbose) { fprintf(rejects, "Row %d is inconsistent.\n", 1+i); fflush(rejects); flag = 0; } else return 0; } } /* Check columns */ for (i = 0; i < PUZZLE_DIM; i++) { for (colmask = j = 0; j < PUZZLE_DIM; j++) { if (bitcount(g->cell[col[i][j]]) == 1) colmask |= g->cell[col[i][j]]; } if (colmask != 0x01ff) { if (verbose) { fprintf(rejects, "Column %d is inconsistent.\n", 1+i); fflush(rejects); flag = 0; } else return 0; } } /* Check 3x3 regions */ for (i = 0; i < PUZZLE_DIM; i++) { for (regmask = j = 0; j < PUZZLE_DIM; j++) { if (bitcount(g->cell[region[i][j]]) == 1) regmask |= g->cell[region[i][j]]; } if (regmask != 0x01ff) { if (verbose) { fprintf(rejects, "Region %d is inconsistent.\n", 1+i); fflush(rejects); flag = 0; } else return 0; } } return flag; } /********************************************************************************/ /* This function uses the cells with unique values, i.e. the given */ /* or subsequently discovered solution values, to eliminate said values */ /* as candidates in other as yet unsolved cells in the associated */ /* rows, columns, and 3x3 regions. */ /* */ /* The function has three possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified, and */ /* STUCK - Markup results are invalid, i.e. a cell has no candidate values */ /********************************************************************************/ static int mark_cells(grid *g) { int i, chgflag, bc; int const *r, *c, *reg; short elt, mask, before; chgflag = NOCHANGE; while (g->tail < g->exposed) { elt = g->solved[g->tail++]; r = row[map[elt].row]; c = col[map[elt].col]; reg = region[map[elt].region]; mask = ~g->cell[elt]; for (i = 0; i < PUZZLE_DIM; i++) { if (r[i] != elt) { /* Get the cell value */ before = g->cell[r[i]]; /* Eliminate this candidate value whilst preserving other candidate values */ g->cell[r[i]] &= mask; /* Did the cell change value? */ if (before != g->cell[r[i]]) { chgflag |= CHANGE; /* Flag that puzzle markup was changed */ g->score += g->inc; /* More work means higher scoring */ if (!(bc = bitcount(g->cell[r[i]]))) { EXPLAIN_MARKUP_IMPASSE(g, r[i], elt); return STUCK; /* Crap out if no candidates remain */ } EXPLAIN_MARKUP_ELIM(g, r[i], elt); /* Check if we solved for this cell, i.e. bit count indicates a unique value */ if (bc == 1) { g->cellflags[r[i]] = FOUND; /* Mark cell as found */ g->score += g->reward; /* Add to puzzle score */ g->solved[g->exposed++] = r[i]; EXPLAIN_MARKUP_SOLVE(g, r[i]); } } } if (c[i] != elt) { /* Get the cell value */ before = g->cell[c[i]]; /* Eliminate this candidate value whilst preserving other candidate values */ g->cell[c[i]] &= mask; /* Did the cell change value? */ if (before != g->cell[c[i]]) { chgflag |= CHANGE; /* Flag that puzzle markup was changed */ g->score += g->inc; /* More work means higher scoring */ if (!(bc = bitcount(g->cell[c[i]]))) { EXPLAIN_MARKUP_IMPASSE(g, c[i], elt); return STUCK; /* Crap out if no candidates remain */ } EXPLAIN_MARKUP_ELIM(g, c[i], elt); /* Check if we solved for this cell, i.e. bit count indicates a unique value */ if (bc == 1) { g->cellflags[c[i]] = FOUND; /* Mark cell as found */ g->score += g->reward; /* Add to puzzle score */ g->solved[g->exposed++] = c[i]; EXPLAIN_MARKUP_SOLVE(g, c[i]); } } } if (reg[i] != elt) { /* Get the cell value */ before = g->cell[reg[i]]; /* Eliminate this candidate value whilst preserving other candidate values */ g->cell[reg[i]] &= mask; /* Did the cell change value? */ if (before != g->cell[reg[i]]) { chgflag |= CHANGE; /* Flag that puzzle markup was changed */ g->score += g->inc; /* More work means higher scoring */ if (!(bc = bitcount(g->cell[reg[i]]))) { EXPLAIN_MARKUP_IMPASSE(g, reg[i], elt); return STUCK; /* Crap out if no candidates remain */ } EXPLAIN_MARKUP_ELIM(g, reg[i], elt); /* Check if we solved for this cell, i.e. bit count indicates a unique value */ if (bc == 1) { g->cellflags[reg[i]] = FOUND; /* Mark cell as found */ g->score += g->reward; /* Add to puzzle score */ g->solved[g->exposed++] = reg[i]; EXPLAIN_MARKUP_SOLVE(g, reg[i]); } } } } } return chgflag; } /*******************************************************************/ /* Identify and "solve" all cells that, by reason of their markup, */ /* can only assume one specific value, i.e. the cell is the only */ /* one in a row/column/region (specified by vector) that is */ /* able to assume a particular value. */ /* */ /* The function has two possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified. */ /*******************************************************************/ static int find_singletons(grid *g, int const *vector, char *vdesc) { int i, j, mask, hist[PUZZLE_DIM], value[PUZZLE_DIM], found = NOCHANGE; /* We are going to create a histogram of cell candidate values */ /* for the specified cell vector (row/column/region). */ /* First set all buckets to zero. */ memset(hist, 0, sizeof(hist[0])*PUZZLE_DIM); /* For each cell in the vector... */ for (i = 0; i < PUZZLE_DIM; i++) { /* For each possible candidate value... */ for (mask = 1, j = 0; j < PUZZLE_DIM; j++) { /* If the cell may possibly assume this value... */ if (g->cell[vector[i]] & mask) { value[j] = vector[i]; /* Save the cell coordinate */ hist[j] += 1; /* Bump bucket in histogram */ } mask <<= 1; /* Next candidate value */ } } /* Examine each bucket in the histogram... */ for (mask = 1, i = 0; i < PUZZLE_DIM; i++) { /* If the bucket == 1 and the cell is not already solved, */ /* then the cell has a unique solution specified by "mask" */ if (hist[i] == 1 && !g->cellflags[value[i]]) { found = CHANGE; /* Indicate that markup has been changed */ g->cell[value[i]] = mask; /* Assign solution value to cell */ g->cellflags[value[i]] = FOUND; /* Mark cell as solved */ g->score += g->reward; /* Bump puzzle score */ g->solved[g->exposed++] = value[i]; EXPLAIN_SINGLETON(g, value[i], mask, vdesc); } mask <<= 1; /* Get next candidate value */ } return found; } /*******************************************************************/ /* Find all cells with unique solutions (according to markup) */ /* and mark them as found. Do this for each row, column, and */ /* region. */ /* */ /* The function has two possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified. */ /*******************************************************************/ static int eliminate_singles(grid *g) { int i, found = NOCHANGE; /* Do rows */ for (i = 0; i < PUZZLE_DIM; i++) { found |= find_singletons(g, row[i], "row"); } /* Do columns */ for (i = 0; i < PUZZLE_DIM; i++) { found |= find_singletons(g, col[i], "column"); } /* Do regions */ for (i = 0; i < PUZZLE_DIM; i++) { found |= find_singletons(g, region[i], "region"); } return found; } /********************************************************************************/ /* Solves simple puzzles, i.e. single elimination */ /* */ /* The function has three possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified, and */ /* STUCK - Markup results are invalid, i.e. a cell has no candidate values */ /********************************************************************************/ static int simple_solver(grid *g) { int flag = NOCHANGE; /* Mark the unsolved cells with candidate solutions based upon the current set of "givens" and solved cells */ while ((flag |= mark_cells(g)) == CHANGE) { g->inc = 1; /* After initial markup, we start scoring for additional markup work */ EXPLAIN_CURRENT_MARKUP(g); /* Continue to eliminate cells with unique candidate solutions from the game until */ /* elimination and repeated markup efforts produce no changes in the remaining */ /* candidate solutions. */ if (eliminate_singles(g) == NOCHANGE) break; EXPLAIN_CURRENT_MARKUP(g); } return flag; } /************************************************************************************/ /* Test a region to see if the candidate solutions for a paticular number */ /* are confined to one row or column, and if so, eliminate */ /* their occurences in the remainder of the given row or column. */ /* */ /* The function has three possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified, and */ /* STUCK - Markup results are invalid, i.e. a cell has no candidate values */ /************************************************************************************/ static int region_vector_elim(grid *g, int region_no, int num) { int i, j, r, c, mask, t, found; short rowhist[PUZZLE_DIM], colhist[PUZZLE_DIM]; /* Init */ found = NOCHANGE; memset(rowhist, 0, sizeof(rowhist[0])*PUZZLE_DIM); memset(colhist, 0, sizeof(colhist[0])*PUZZLE_DIM); mask = 1 << num; /* Create histograms for row and column placements for the value being checked */ for (i = 0; i < PUZZLE_DIM; i++) { j = region[region_no][i]; if ((g->cell[j] & mask)) { rowhist[map[j].row] += 1; colhist[map[j].col] += 1; } } /* Figure out if this number lies in only one row or column */ /* Check rows first*/ r = c = -1; for (i = 0; i < PUZZLE_DIM; i++) { if (rowhist[i]) { if (r < 0) { r = i; } else { r = -1; break; } } } /* Now check columns */ for (i = 0; i < PUZZLE_DIM; i++) { if (colhist[i]) { if (c < 0) { c = i; } else { c = -1; break; } } } /* If the number is only in one row, then eliminate this number from the cells in the row outside of this region */ if (r >= 0) { for (i = 0; i < PUZZLE_DIM; i++) { j = row[r][i]; if (map[j].region != region_no && !g->cellflags[j]) { t = g->cell[j]; if ((g->cell[j] &= ~mask) == 0) { EXPLAIN_VECTOR_IMPASSE(g, "row", r, j, mask, region_no); g->score += 10; return STUCK; } if (t != g->cell[j]) { found = CHANGE; g->score += g->inc; EXPLAIN_VECTOR_ELIM("row", r, j, mask, region_no); if (bitcount(g->cell[j]) == 1) { g->cellflags[j] = FOUND; g->score += g->reward; g->solved[g->exposed++] = j; EXPLAIN_VECTOR_SOLVE(g, j); } } } } } /* If the number is only in one column, then eliminate this number from the cells in the column outside of this region */ else if (c >= 0) { for (i = 0; i < PUZZLE_DIM; i++) { j = col[c][i]; if (map[j].region != region_no && !g->cellflags[j]) { t = g->cell[j]; if ((g->cell[j] &= ~mask) == 0) { EXPLAIN_VECTOR_IMPASSE(g, "column", c, j, mask, region_no); g->score += 10; return STUCK; } if (t != g->cell[j]) { found = CHANGE; g->score += g->inc; EXPLAIN_VECTOR_ELIM("column", c, j, mask, region_no); if (bitcount(g->cell[j]) == 1) { g->cellflags[j] = FOUND; g->score += g->reward; g->solved[g->exposed++] = j; EXPLAIN_VECTOR_SOLVE(g, j); } } } } } if (found == CHANGE) { g->score += 10; /* Bump score for sucessfully invoking this rule */ } return found; } /**********************************************************************************/ /* Test all regions to see if the possibilities for a number */ /* are confined to specific rows or columns, and if so, eliminate */ /* the occurence of candidate solutions from the remainder of the */ /* specified row or column. */ /* */ /* The function has three possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified, and */ /* STUCK - Markup results are invalid, i.e. a cell has no candidate values */ /**********************************************************************************/ static int vector_elimination(grid *g) { int i, j, rc; /* For each region... */ for (rc = NOCHANGE, i = 0; i < PUZZLE_DIM && rc != STUCK; i++) { /* For each digit... */ for (j = 0; j < PUZZLE_DIM && rc != STUCK; j++) { /* Eliminate candidates outside of regions when a particular */ /* candidate value aligns itself to a row or column within */ /* a 3x3 region. */ rc |= region_vector_elim(g, i, j); } } return rc; } /**********************************************************************************/ /* This function implements the rule that when a subset of cells */ /* in a row/column/region contain matching subsets of candidate */ /* solutions, i.e. 2 matching possibilities for 2 cells, 3 */ /* matching possibilities for 3 cells, etc., then those */ /* candidates may be eliminated from the other cells in the */ /* row, column, or region. */ /* */ /* The function has three possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified, and */ /* STUCK - Markup results are invalid, i.e. a cell has no candidate values */ /**********************************************************************************/ static int elim_matches(grid *g, int const *cell_list, char *desc, int ndx) { int i, j, k, e, count, rc, flag; short c, mask, tmp, elts[PUZZLE_DIM], eliminated[PUZZLE_DIM]; static int counts[1<cell[k]; /* Copy original cell candidates */ if (bitcount(g->cell[k]) == i) { counts[g->cell[k]] += 1; /* The bucket records the number of cells with this subset */ } } /* For each cell in the list... */ for (e = j = 0; j < PUZZLE_DIM; j++) { c = g->cell[cell_list[j]]; /* Get cell's candidates */ /* Check to see if we've already eliminated this subset */ for (k = 0; k < e; k++) if (c == eliminated[k]) break; if (e && k < e) continue; /* Get count from histogram bucket */ count = (int) (counts[c]); /* If too few solution candidates for the number of cells, then we're stuck */ if (count > i) { EXPLAIN_TUPLE_IMPASSE(g, desc, ndx, c, count, i); /* Clean up static array */ for (k = 0; k < 9; k++) counts[elts[k]] = 0; g->score += 10; return STUCK; } /* Do candidate and cell counts match? */ if (count == i) { /* Compute mask used to eliminate candidates from other cells */ mask = ~c; /* Record (for later) the values being eliminated */ eliminated[e++] = c; /* Eliminate candidates from the other cells in the list */ /* For each cell... */ for (k = 0; k < PUZZLE_DIM; k++) { /* If the cell candidates do not exactly match the current subset... */ if (c != g->cell[cell_list[k]] && !g->cellflags[cell_list[k]]) { /* Get cell candidates */ tmp = g->cell[cell_list[k]]; /* Eliminate candidates with our mask */ g->cell[cell_list[k]] &= mask; /* Did the elimination change the candidates? */ if (tmp != g->cell[cell_list[k]]) { /* Note the change and bump the score */ flag = CHANGE; g->score += i; EXPLAIN_TUPLE_ELIM(desc, ndx, c, cell_list[k]); /* Did we solve the cell under consideration? */ if (bitcount(g->cell[cell_list[k]]) == 1) { /* Mark cell as found and bump the score */ g->cellflags[cell_list[k]] = FOUND; g->score += g->reward; g->solved[g->exposed++] = cell_list[k]; EXPLAIN_TUPLE_SOLVE(g, cell_list[k]); } } } } } } /* Cleanup the static histogram array */ for (j = 0; j < PUZZLE_DIM; j++) counts[elts[j]] = 0; rc |= flag; } return rc; } /**********************************************************************************/ /* Eliminate subsets from rows, columns, and regions. */ /* */ /* The function has three possible return values: */ /* NOCHANGE - Markup did not change during the last pass, */ /* CHANGE - Markup was modified, and */ /* STUCK - Markup results are invalid, i.e. a cell has no candidate values */ /**********************************************************************************/ static int mult_elimination(grid *g) { int i, rc = NOCHANGE; /* Eliminate subsets from rows */ for (i = 0; i < PUZZLE_DIM; i++) { rc |= elim_matches(g, row[i], "row", i); } /* Eliminate subsets from columns */ for (i = 0; i < PUZZLE_DIM; i++) { rc |= elim_matches(g, col[i], "column", i); } /* Eliminate subsets from regions */ for (i = 0; i < PUZZLE_DIM; i++) { rc |= elim_matches(g, region[i], "region", i); } return rc; } /**************************************************/ /* Entry point to the recursive solver algorithm. */ /**************************************************/ static int rsolve(grid *g, return_soln soln_callback) { int i, j, min, c, weight, mask, flag = 0; grid mygrid; /* Keep track of recursive depth */ lvl += 1; if (lvl > g->maxlvl) g->maxlvl = lvl; for (;;) { /* Attempt a simple solution */ if (simple_solver(g) == STUCK) break; /* Check for solution */ if (g->exposed >= PUZZLE_CELLS) break; g->reward += 2; /* Bump reward as we graduate to more "advanced" solving techniques */ /* Eliminate tuples */ if ((flag = mult_elimination(g)) == CHANGE) { EXPLAIN_CURRENT_MARKUP(g); continue; } /* Check if impasse */ if (flag == STUCK) break; /* Check for solution */ if (g->exposed >= PUZZLE_CELLS) break; /* Eliminate clues aligned within regions from exterior cells in rows or columns */ if ((flag = vector_elimination(g)) == CHANGE) { EXPLAIN_CURRENT_MARKUP(g); continue; } /* Check if impasse */ if (flag == STUCK) break; /* Check for solution */ if (g->exposed >= PUZZLE_CELLS) break; g->reward += 5; /* Bump reward as we are about to start trial soutions */ /* Attempt a trial solution */ memcpy(&mygrid, g, sizeof(grid)); /* Make working copy of puzzle */ /* Find the first cell with the smallest number of alternatives */ for (weight= 0, c = -1, min = PUZZLE_DIM, i = 0; i < PUZZLE_CELLS; i++) { if (!mygrid.cellflags[i]) { j = bitcount(mygrid.cell[i]); weight += 1; if (j < min) { min = j; c = i; } } } mygrid.score += weight; /* Add penalty to score */ /* Cell at index 'c' will be our starting point */ if (c >= 0) for (mask = 1, i = 0; i < PUZZLE_DIM; i++) { /* Is this a candidate? */ if (mask & g->cell[c]) { EXPLAIN_TRIAL(c, mask); mygrid.score += (int)(((50.0 * lvl * weight) / (double)(PUZZLE_CELLS)) + 0.5); /* Add'l penalty */ /* Try one of the possible candidates for this cell */ mygrid.cell[c] = mask; mygrid.cellflags[c] = FOUND; mygrid.solved[mygrid.exposed++] = c; EXPLAIN_CURRENT_MARKUP(&mygrid); flag = rsolve(&mygrid, soln_callback); /* Recurse with working copy of puzzle */ /* Did we find a solution? */ if (flag == FOUND && !enumerate_all) { EXPLAIN_BACKTRACK; lvl -= 1; return FOUND; } /* Preserve score, solution count and recursive depth as we back out of recursion */ g->score = mygrid.score; g->solncount = mygrid.solncount; g->maxlvl = mygrid.maxlvl; memcpy(&mygrid, g, sizeof(grid)); } mask <<= 1; /* Get next possible candidate */ } break; } if (g->exposed == PUZZLE_CELLS && validate(g, 0)) { soln_callback(g); g->solncount += 1; EXPLAIN_SOLN_FOUND(g); EXPLAIN_BACKTRACK; lvl -= 1; flag = FOUND; } else { EXPLAIN_BACKTRACK; lvl -= 1; flag = STUCK; if (!lvl && !g->solncount) validate(g, 1); /* Print verbose diagnostic for insoluble puzzle */ } return flag; } /*****************************************************************/ /* Add a puzzle solution to the singly linked list of solutions. */ /* Crap out if no memory available. */ /*****************************************************************/ static int add_soln(grid *g) { grid *tmp; if ((tmp = malloc(sizeof(grid))) == NULL) { fprintf(stderr, "Out of memory.\n"); exit(1); } memcpy(tmp, g, sizeof(grid)); tmp->next = soln_list; soln_list = tmp; return 0; } /************************************/ /* Print hints as to command usage. */ /************************************/ static void usage() { fprintf(stderr, "Usage:\n\t%s {-p puzzle | -f } [-o ]\n", myname); fprintf(stderr, "\t\t[-r ] [-1][-a][-c][-G][-g][-l][-m][-n][-s]\n"); fprintf(stderr, "where:\n\t-1\tSearch for first solution, otherwise all solutions are returned\n" "\t-a\tRequests that the answer (solution) be printed\n" "\t-c\tPrint a count of solutions for each puzzle\n" "\t-d\tPrint the recursive trial depth required to solve the puzzle\n" #ifdef EXPLAIN "\t-e\tPrint a step-by-step explanation of the solution(s)\n" #endif "\t-f\tTakes an argument which specifes an input file\n\t\tcontaining one or more unsolved puzzles (default: stdin)\n" "\t-G\tPrint the puzzle solution(s) in a 9x9 grid format\n" "\t-g\tPrint the number of given clues\n" "\t-m\tPrint an octal mask for the puzzle givens\n" "\t-n\tNumber each result\n" "\t-o\tSpecifies an output file for the solutions (default: stdout)\n" "\t-p\tTakes an argument giving a single inline puzzle to be solved\n" "\t-r\tSpecifies an output file for unsolvable puzzles\n\t\t(default: stderr)\n" "\t-s\tPrint the puzzle's score or difficulty rating\n" "\t-?\tPrint usage information\n\n"); fprintf(stderr, "The return code is zero if all puzzles had unique solutions,\n" "(or have one or more solutions when -1 is specified) and non-zero\n" "when no unique solution exists.\n"); } /********************************************************/ /* Print the puzzle as an 81 character string of digits */ /********************************************************/ static char *format_answer(grid *g, char *outbuf) { int i; for (i = 0; i < PUZZLE_CELLS; i++) outbuf[i] = symtab[g->cell[i]]; outbuf[i] = 0; return outbuf; } /*******************************************/ /* Print the puzzle as a standard 9x9 grid */ /*******************************************/ static void print_grid(char *sud, FILE *h) { fprintf(h, "\n"); EXPLAIN_INDENT(h); fprintf(h, "+---+---+---+\n"); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud, PUZZLE_ORDER, PUZZLE_ORDER, sud+3, PUZZLE_ORDER, PUZZLE_ORDER, sud+6); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+9, PUZZLE_ORDER, PUZZLE_ORDER, sud+12, PUZZLE_ORDER, PUZZLE_ORDER, sud+15); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+18, PUZZLE_ORDER, PUZZLE_ORDER, sud+21, PUZZLE_ORDER, PUZZLE_ORDER, sud+24); EXPLAIN_INDENT(h); fprintf(h, "+---+---+---+\n"); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+27, PUZZLE_ORDER, PUZZLE_ORDER, sud+30, PUZZLE_ORDER, PUZZLE_ORDER, sud+33); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+36, PUZZLE_ORDER, PUZZLE_ORDER, sud+39, PUZZLE_ORDER, PUZZLE_ORDER, sud+42); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+45, PUZZLE_ORDER, PUZZLE_ORDER, sud+48, PUZZLE_ORDER, PUZZLE_ORDER, sud+51); EXPLAIN_INDENT(h); fprintf(h, "+---+---+---+\n"); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+54, PUZZLE_ORDER, PUZZLE_ORDER, sud+57, PUZZLE_ORDER, PUZZLE_ORDER, sud+60); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+63, PUZZLE_ORDER, PUZZLE_ORDER, sud+66, PUZZLE_ORDER, PUZZLE_ORDER, sud+69); EXPLAIN_INDENT(h); fprintf(h, "|%*.*s|%*.*s|%*.*s|\n", PUZZLE_ORDER, PUZZLE_ORDER, sud+72, PUZZLE_ORDER, PUZZLE_ORDER, sud+75, PUZZLE_ORDER, PUZZLE_ORDER, sud+78); EXPLAIN_INDENT(h); fprintf(h, "+---+---+---+\n"); } /*****************************************************/ /* Based upon the Left-to-Right-Top-to-Bottom puzzle */ /* presented in "sbuf", create a 27 octal digit */ /* mask of the givens in the 28 character buffer */ /* pointed to by "mbuf." Return a pointer to mbuf. */ /*****************************************************/ static char *cvt_to_mask(char *mbuf, char *sbuf) { char *mask_buf = mbuf; static const char *maskchar = "01234567"; int i, m; mask_buf[PUZZLE_DIM*3] = 0; for (i = 0; i < PUZZLE_CELLS; i += 3) { m = 0; if (is_given(sbuf[i])) { m |= 4; } else { sbuf[i] = '0'; } if (is_given(sbuf[i+1])) { m |= 2; } else { sbuf[i+1] = '0'; } if (is_given(sbuf[i+2])) { m |= 1; } else { sbuf[i+2] = '0'; } *mask_buf++ = maskchar[m]; } return mbuf; } /*******************/ /* Mainline logic. */ /*******************/ int main(int argc, char **argv) { int i, rc, bog, count, opt, solved, unsolved, solncount, flag, prt_count, prt_num, prt_score, prt_answer, prt_depth, prt_grid, prt_mask, prt_givens, prt, len; char *infile, *outfile, *rejectfile, inbuf[128], outbuf[128], mbuf[28]; grid g, *s; FILE *h; /* Get our command name from invoking command line */ if ((myname = strrchr(argv[0], '/')) == NULL) myname = argv[0]; else myname++; /* Print sign-on message to console */ fprintf(stderr, "%s version %s\n", myname, VERSION); fflush(stderr); /* Init */ h = stdin; solnfile = stdout; rejects = stderr; rejectfile = infile = outfile = NULL; rc = bog = prt_mask = prt_grid = prt_score = prt_depth = prt_answer = prt_count = prt_num = prt_givens = 0; *inbuf = 0; /* Parse command line options */ while ((opt = getopt(argc, argv, OPTIONS)) != -1) { switch (opt) { case '1': enumerate_all = 0; /* only find first soln */ break; case 'a': prt_answer = 1; /* print solution */ break; case 'c': prt_count = 1; /* number solutions */ break; case 'd': prt_depth = 1; break; #ifdef EXPLAIN case 'e': explain = 1; break; #endif case 'f': if (*inbuf) { /* -p and -f options are mutually exclusive */ fprintf(stderr, "The -p and -f options are mutually exclusive\n"); usage(); exit(1); } infile = optarg; /* get name of input file */ break; case 'G': prt_grid = 1; break; case 'g': prt_givens = 1; break; case 'm': prt_mask = 1; break; case 'n': prt_num = 1; break; case 'o': outfile = optarg; break; case 'p': if (infile) { fprintf(stderr, "The -p and -f options are mutually exclusive\n"); usage(); exit(1); } if (strlen(optarg) == PUZZLE_CELLS) { strcpy(inbuf, optarg); } else { fprintf(stderr, "Invalid puzzle specified: %s\n", optarg); usage(); exit(1); } h = NULL; break; case 'r': rejectfile = optarg; break; case 's': prt_score = 1; break; default: case '?': usage(); exit(1); } } /* Set prt flag if we're printing anything at all */ prt = prt_mask | prt_grid | prt_score | prt_depth | prt_answer | prt_num | prt_givens; /* Anthing else on the command line is bogus */ if (argc > optind) { fprintf(stderr, "Extraneous args: "); for (i = optind; i < argc; i++) { fprintf(stderr, "%s ", argv[i]); } fprintf(stderr, "\n\n"); usage(); exit(1); } if (!enumerate_all && prt_score) { fprintf(stderr, "Scoring is meaningless when multi-solution mode is disabled.\n"); } if (rejectfile && !(rejects = fopen(rejectfile, "w"))) { fprintf(stderr, "Failed to open reject output file: %s\n", rejectfile); exit(1); } if (outfile && !(solnfile = fopen(outfile, "w"))) { fprintf(stderr, "Failed to open solution output file: %s\n", outfile); exit(1); } if (infile && strcmp(infile, "-") && !(h = fopen(infile, "r"))) { fprintf(stderr, "Failed to open input game file: %s\n", infile); exit(1); } count = solved = unsolved = 0; if (h) fgets(inbuf, 128, h); while (*inbuf) { if ((len = strlen(inbuf)) && inbuf[len-1] == '\n') { len -= 1; inbuf[len] = 0; } count += 1; if (len != PUZZLE_CELLS) { fprintf(rejects, "%d: %s bogus puzzle format\n", count, inbuf); fflush(rejects); *inbuf = 0; bog += 1; if (h) fgets(inbuf, 128, h); continue; } cvt_to_grid(&g, inbuf); if (g.givens < 17) { fprintf(rejects, "%d: %*.*s bogus puzzle has less than 17 givens\n", count, PUZZLE_CELLS, PUZZLE_CELLS, inbuf); fflush(rejects); *inbuf = 0; bog += 1; if (h) fgets(inbuf, 128, h); continue; } for (s = soln_list; s;) { s = soln_list->next; free(soln_list); soln_list = s; } flag = rsolve(&g, add_soln); if (soln_list) { solved++; for (solncount = 0, s = soln_list; s; s = s->next) { solncount += 1; if (prt_num) { char nbuf[32]; if (!enumerate_all) sprintf(nbuf, "%d: ", count); else sprintf(nbuf, "%d:%d ", count, solncount); fprintf(solnfile, "%-s", nbuf); } if (solncount > 1 || !enumerate_all) g.score = 0; if (prt_score) fprintf(solnfile, "score: %-7d ", g.score); if (prt_depth) fprintf(solnfile, "depth: %-3d ", g.maxlvl); if (prt_answer || prt_grid) format_answer(s, outbuf); if (prt_answer) fprintf(solnfile, "%s", outbuf); if (prt_mask) fprintf(solnfile, " %s", cvt_to_mask(mbuf, inbuf)); if (prt_givens) fprintf(solnfile, " %d", g.givens); if (prt_grid) print_grid(outbuf, solnfile); if (prt) fprintf(solnfile, "\n"); if (s->next == NULL && prt_count) fprintf(solnfile, "count: %d\n", solncount); } if (solncount > 1 && enumerate_all) { rc |= 1; } } else { unsolved++; rc |= 1; fprintf(rejects, "%d: %*.*s unsolved\n", count, PUZZLE_CELLS, PUZZLE_CELLS, inbuf); fflush(rejects); diagnostic_grid(&g, rejects); #if defined(DEBUG) mypause(); #endif } *inbuf = 0; if (h) fgets(inbuf, 128, h); } if (prt) fprintf(solnfile, "\nPuzzles: %d, Solved: %d, Unsolved: %d, Bogus: %d\n", count, solved, unsolved, bog); return rc; }