The main program, sudoku_solver.c, accepts the Sudoku to be solved, performs some checks, solves the Sudoku, and presents the final result. It is the module that binds together all the various functions of the program.

Several of the modules listed in this and following chapters include commented-out pieces of code whose purpose is to display partial or final results of algorithms. If you enable them by removing the enclosing /* and */, they will help you to better understand how the program works and to modify the code if you so wish.

Before talking about the main program itself, you need to study def.h (see Listing 3-1), the header file that contains definitions and declarations used throughout the program.

Listing 3-1. def.h

/* def.h
 *
 * Definitions and declarations
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#ifndef DEF
#define DEF

// General definitions
#define FALSE 0
#define TRUE  1

// Definitions for logging
#define LOG_FOOTPRINT
#define LOG_HIDDEN_PAIR
#define LOG_NAKED_QUAD
#define LOG_HIDDEN_TRIPLE
//#define LOG_IN_OUT
#define LOG_LINES
#define LOG_NAKED_PAIR
#define LOG_NAKED_TRIPLE
#define LOG_POINTING_LINE
#define LOG_RECTANGLE
#define LOG_REMOVE_CANDIDATE
#define LOG_BOX_LINE
#define LOG_UNIQUE
#define LOG_XY_CHAIN
#define LOG_Y_WING

// Definitions to distinguish between Y-wing and XY-chain when invoking
// pairs_find()
#define DEF_Y_WING  0
#define DEF_XY_CHAIN 1

// Structure and typedef to build chains of cell coordinates.
// It makes possible to develop functions that return lists of cells.
#define MAX_INTER_N 13
typedef struct rc_struct *rc_p_t;
typedef struct rc_struct {
  int row;
  int col;
  rc_p_t next;
  } rc_struct_t;

// Strategy functions
typedef int (*f_ptr_t)(void);
extern f_ptr_t *strat_all[];
extern char **strat_all_names[];
extern int n_strat_all[];
extern int n_levels;

// List of strategies used in a solution
// 0 means 'unique', 40 means 'backtrack'
// Other strategies: (strat level) * 10 + (strat ID within the level)
extern int strats_used[];
extern int n_strats_used;

// Used in some strategies for clarity
#define ROW 0
#define COL 1
#define BOX 2
extern char *unit_names[3];

// Sudoku declarations in sudoku_solver.c
extern char grid[9][9][10];
extern char row[9][9][2];
extern char col[9][9][2];
extern char box[9][9][2];

// Flags
extern int problem_found;
extern int silent;
extern int backtracking;

// Patch because Windows doesn't recognize srandom() and random()
#ifdef __WIN32__
#define srandom srand
#define random rand
#endif

#endif

The first two lines and the last line ensure that multiple inclusions of def.h will not cause any problem:

#ifndef DEF
#define DEF
...
#endif

This is a mechanism that, to be on the safe side, you should use in all header files: if an identifier matching the name of the header file is undefined, define it and do the rest. Otherwise, do nothing.

The definitions of FALSE and TRUE deserve a couple of comments. The use of symbolic names for true and false makes for more readable code, but you have to keep in mind that in C the condition (an_integer == TRUE) succeeds only if an_integer is equal to 1, while the condition (an_integer) succeeds when an_integer is not equal to zero. That is, (an_integer == TRUE) and (an_integer == FALSE) are not mutually exclusive. If a variable gets corrupted (e.g., because you write outside the boundaries of an array) and an_integer is assigned a value other than 0 or 1, (an_integer == TRUE) fails, while (an_integer != FALSE) succeeds!

I developed the Solver on a Mac. When I tested the code on a PC, I discovered that stdlib.h didn’t declare srandom() and random() and that the linker didn’t find them in the libraries.

By choosing to use srandom() and random() instead of srand() and rand(), I had made my code not portable to Windows! I decided to stick to my choice because srandom() and random() work better, and add to def.h the following ‘patch’:

#ifdef __WIN32__
#define srandom srand
#define random rand
#endif

The definitions for logging allow you to selectively switch out the displaying of messages when some events occur, as in

#ifdef LOG_UNIQUE
  if (!silent) {
    printf("unique_unit: %d in (%d,%d) is unique"
           "within the %s
",
        i, kR, kC, what
        );
    }
#endif

In this example, you also see the use of the global variable silent. By setting it to TRUE, you can completely suppress logging. Also, and most important, you can change silent at runtime. It allows you to temporarily suppress logging while doing the initial cleanup of a Sudoku and while backtracking.

Ignore for the moment the definitions associated with pairs_find(). You will learn about them in Chapters 10 and 11, which explain the implementation of the strategies Y-wing and XY-chain.

The definition

typedef int (*f_ptr_t)(void);

and the declarations

extern f_ptr_t *strat_all[];
extern char **strat_all_names[];
extern int n_strat_all[];
extern int n_levels;

make it possible to execute sequences of strategies of any particular level of difficulty without having to call them one by one. The Solver initializes the arrays strat_all, strat_all_names, and n_strat_all in the main program (sudoku_solver.c) as follows:

// Arrays of strategies
//
// Trivial strategies (level 0)
f_ptr_t strat0[] = {unique_loop};
char *strat0_names[] = {
    "unique-loop"
    };
//
// Easy strategies (level 1)
f_ptr_t strat1[] = {naked_pair, hidden_pair, box_line, pointing_line};
char *strat1_names[] = {
    "naked-pair", "hidden-pair", "box-line", "pointing-line"
    };
//
// Intermediate strategies (level 2)
f_ptr_t strat2[] = {naked_triple, hidden_triple, lines_2,
    naked_quad, y_wing
    };
char *strat2_names[] = {
    "naked-triple", "hidden-triple", "lines-2", "naked-quad", "Y-wing"
    };
//
// Complex strategies (level 3)
f_ptr_t strat3[] = {rectangle, xy_chain, lines_3, lines_4};
char *strat3_names[] = {
    "rectangle", "XY-chain", "lines-3", "lines-4"
    };
//
// All strategies
f_ptr_t *strat_all[] = {
    &strat0[0], &strat1[0], &strat2[0], &strat3[0]
    };
char **strat_all_names[] = {
    &strat0_names[0], &strat1_names[0], &strat2_names[0], &strat3_names[0]
    };
int n_strat_all[] = {
    sizeof(strat0)/sizeof(f_ptr_t),
    sizeof(strat1)/sizeof(f_ptr_t),
    sizeof(strat2)/sizeof(f_ptr_t),
    sizeof(strat3)/sizeof(f_ptr_t)
    };
int n_levels = N_LEVELS;

First, you initialize the group of strategies of a particular level of difficulty, as in the following example for level 1:

// Easy strategies (level 1)
f_ptr_t strat1[] = {naked_pair, hidden_pair, box_line, pointing_line};
char *strat1_names[] = {
    "naked-pair", "hidden-pair", "box-line", "pointing-line"
    };

Then, you initialize the arrays for all levels.

As all functions that implement strategies have no parameters and return an int value, you can execute all the strategies of a particular level with a simple loop like in the following example, in which k_level is a non-negative number smaller than n_levels:

for (int k_strat = 0; k_strat < n_strat_all[k_level]; k_strat++) {
  printf("Executing %s...
", strat_all_names[k_level][k_strat]);
  int result = strat_all[k_level][k_strat]();
  printf("...%s happened
", (result)?"something":"nothing");
  }

For improved readability of the code, you could also decide to use pointers as in

f_ptr_t *strats = strat_all[k_level];
char **strat_names = strat_all_names[k_level];
int n_strat = n_strat_all[level];
for (int k_strat = 0; k_strat < n_strat; k_strat++) {
  printf("Executing %s...
", strat_names[k_strat]);
  int result = strats[k_strat]();
  printf("...%s happened
", (result)?"something":"nothing");
  }

strats_used and n_strats_used make possible for the Solver to save a list of all strategies it needs to solve a particular Sudoku puzzle. Such summaries of strategy usage are useful when the program solves many puzzles one after the other. (More about this in Chapter 14).

In the remaining statements of def.h, only the declarations of problem_found and backtracking require some explanation, but it would be confusing to explain them here. You will find their description in Chapter 13, concerned with the implementation of backtracking.

Now that you know most of what def.h does, you can look at the main program. Its first part consists of “include” statements, as shown in Listing 3-2.

Listing 3-2. sudoku_solver.c–Part 1: Includes

/* sudoku_solver.c
 *
 * Main program.
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "backtrack.h"
#include "box_line.h"
#include "cleanup.h"
#include "count_candidates.h"
#include "count_solved.h"
#include "def.h"
#include "display.h"
#include "display_strats_in_clear.h"
#include "display_string.h"
#include "hidden_pair.h"
#include "hidden_triple.h"
#include "inconsistent_grid.h"
#include "init.h"
#include "lines_2.h"
#include "lines_3.h"
#include "lines_4.h"
#include "naked_pair.h"
#include "naked_quad.h"
#include "naked_triple.h"
#include "pointing_line.h"
#include "rectangle.h"
#include "solve.h"
#include "unique_loop.h"
#include "xy_chain.h"
#include "y_wing.h"

Notice that the includes are in alphabetical order. This is possible because their order is irrelevant. To rely on the order of includes is a very bad programming practice that can only result in disaster!

After the includes, come the definitions of two configuration parameters.

//#define USE_FILES
#define N_LEVELS 4  // levels of strategies

The Solver looks for the definition of USE_FILES to decide whether to solve multiple puzzles contained in a file or a single one passed to the program via an input argument. In the previous code, the comment before the definition renders it inactive.

Then, the definitions of global variables follow (see Listing 3-3). These are the variables declared in def.h.

Listing 3-3. sudoku_solver.c–Part 2: Global Variables

// Sudoku grid and Sudoku indexing arrays
char grid[9][9][10];
char row[9][9][2];
char col[9][9][2];
char box[9][9][2];

// Unit names used for display in clear
char *unit_names[3] = {"row", "column", "box"};

// Easy strategies (level 1)
f_ptr_t strat1[] = {
    naked_pair, hidden_pair, box_line, pointing_line
    };
char *strat1_names[] = {
    "naked-pair", "hidden-pair", "box-line",
    "pointing-line"
    };
int n_strat1 = sizeof(strat1)/sizeof(f_ptr_t);

// Intermediate strategies (level 2)
f_ptr_t strat2[] = {
    naked_triple, hidden_triple, lines_2,
    naked_quad, y_wing
    };
char *strat2_names[] = {
    "naked-triple", "hidden-triple", "lines-2",
    "naked-quad", "Y-wing", "XY-chain"
    // Warning: appended "XY-chain"
    };
int n_strat2 = sizeof(strat2)/sizeof(f_ptr_t);

// Complex strategies (level 3)
// WARNING: Keep XY-chain in the first position
//          because strategy() depends on it to set
//          strats_used
f_ptr_t strat3[] = {
    xy_chain, rectangle, lines_3, lines_4
    };
char *strat3_names[] = {
    "XY-chain", "rectangle", "lines-3", "lines-4"
    };
int n_strat3 = sizeof(strat3)/sizeof(f_ptr_t);

// List of used strategies (never seen more than 19)
int strats_used[50];
int n_strats_used;

// Global flags, to 'pop out' from nested calls
int problem_found = FALSE;
int silent = FALSE;

After that, the executable statements begin, and the Solver follows different paths depending on whether you have defined USE_FILES or not. You achieve this with an ifdef directive to the C preprocessor:

int main(int argc, char *argv[]) {

#ifdef USE_FILES
... Code to process multiple puzzles read from file.
... See Chapter 14.
#else
... Code to process a single puzzle obtained from an input argument.
#endif

Listing 3-4 shows how the Solver obtains a puzzle definition from an input argument and checks that it is correct.

Listing 3-4. sudoku_solver.c–Part 3: Checks

#else

  // Check for the presence of an input Sudoku string
  if (argc < 2) {
    puts("*** You need to provide a sudoku string");
    return EXIT_FAILURE;
    }

  // Check that the Sudoku string is 81-chars long
  if (strlen(argv[1]) != 81) {
    puts("*** The sudoku string must be 81 characters long");
    return EXIT_FAILURE;
    }

  // Check that the Sudoku string consists of digits between 0 and 9
  for (int k = 0; k < 81; k++) {
    if (argv[1][k] < '0' || argv[1][k] > '9') {
      puts("*** The sudoku string must only contain 0 to 9 digits");
      return EXIT_FAILURE;
      }
    }

These are not exhaustive and foolproof checks, but they catch some major mistakes that would prevent the program from working.

They ensure that you launch the program with at least one argument, that the string contained in the first argument is 81 characters long (i.e., equal to the number of cells in a Sudoku), and that it consists of digits between 0 and 9 (1 to 9 for the clues and 0 for the empty cells of the puzzle). Obviously, it doesn’t mean that the string represents a valid Sudoku puzzle, because not all sequences of digits admit one (and only one) solution, but it is better than no check at all. More about this argument in the section “Input/Output.”

The last part of sudoku_solver.c is where you do the interesting work (see Listing 3-5).

Listing 3-5. sudoku_solver.c–Part 4: Solving the Sudoku

// Print the Sudoku string
if (argc > 2) {
  printf("--- "%s"
", argv[2]);
  }
printf("--- "%s"
", argv[1]);

// Initialize the Sudoku arrays
init(argv[1]);
display();

// Remove the impossible numbers with an initial cleanup without
// displaying any logging messages
printf("sudoku: the initial grid contains %d solved cells
",
    count_solved()
    );
silent = TRUE;
cleanup();
silent = FALSE;
printf("sudoku: after the initial cleanup, the grid"
       " contains %d solved cells
", count_solved()
       );
display();

// Execute the strategies
solve();

// Backtrack if necessary
if (count_solved() < 81) {
  backtracking = TRUE;
  backtrack(0);
  backtracking = FALSE;
  }

// Check that everything is OK
if (inconsistent_grid()) {
  printf("*** The grid is inconsistent
");
  }

printf("sudoku: the final grid contains %d solved cells
 ",
       count_solved()
       );
display();
display_string();
prinf("Strategies used %d: ", n_strats_used);
/*
for (int k = 0; k < n_strats_used; k++) {
  printf(" %d", strats_used[k]);
  }
printf("
");
*/
  display_strats_in_clear();

#endif

  return EXIT_SUCCESS;
  }

sudoku_solver.c does its work by executing four functions, highlighted in bold in Listing 3-5. The following sections describe the first three of them in detail. For the description of the function backtrack() refer to Chapter 13.

init()

This function initializes the Sudoku arrays and fills in the grid with the input Sudoku string (see Listing 3-6).

Listing 3-6. init.c

/* init.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "init.h"

void init(char *arg) {
#ifdef LOG_IN_OUT
  printf("--- init >>>
");
#endif

  // Initialize the sudoku arrays
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      grid[k][j][0] = 9;
      for (int i = 1; i <= 9; i++) {
        grid[k][j][i] = TRUE;
        }
      row[k][j][0] = k;
      row[k][j][1] = j;
      col[j][k][0] = k;
      col[j][k][1] = j;
      box[k/3*3+j/3][k%3*3+j%3][0] = k;
      box[k/3*3+j/3][k%3*3+j%3][1] = j;
      }
    }

  // Save the sudoku string into the array
  for (int k = 0; k < 81; k++) {
    int kR = k / 9;
    int kC = k – kR * 9;
    if (arg[k] != '0') {
      for (int i = 1; i <= 9; i++) {
        grid[kR][kC][i] = FALSE;
        }
      grid[kR][kC][arg[k] - '0'] = TRUE;
      grid[kR][kC][0] = 1;
      }
    }

/*
  // Display the allocated numbers
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      if (grid[k][j][0] == 1) {
        int i = 0;
        do {
          i++;
          } while (grid[k][j][i] == 0);
        printf("%d", i);
        }
      else {
        printf(".");
        }
      }
    printf("
");
    }
*/
#ifdef LOG_IN_OUT
  printf("<<< init ---
");
#endif
  }

The first set of for-loops is independent of the input string. It sets up the arrays row, col, and box so that they point to the correct cells of the Sudoku grid (i.e., the array grid). At the same time, it also initializes each cell of the grid to contain all nine possible candidates.

The second set of for-loops examines each character of the input string, and when it is non-zero, it sets the corresponding element of the grid to that number.

Straightforward, really.

cleanup()

This function uses the level 0 strategies naked single and cleanup to remove as many candidates as possible from the initial Sudoku. As you can see from Listing 3-7, it simply executes the function cleanup_around() for each cell of the grid.

Listing 3-7. cleanup.c

/* cleanup.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "cleanup.h"
#include "cleanup_around.h"
#include "def.h"

void cleanup() {
#ifdef LOG_IN_OUT
  printf("--- cleanup >>>
");
#endif
  for (int k = 0; k < 9 && !problem_found; k++) {
    for (int j = 0; j < 9 && !problem_found; j++) {
      if (grid[k][j][0] == 1) cleanup_around(k, j);
      }
    }
#ifdef LOG_IN_OUT
  printf("<<< cleanup ---
");
#endif
  }

Notice that both for-loops are aborted when the variable problem_found is not FALSE. As I already said, I will explain how you use problem_found in Chapter 13.

The function cleanup_around() (see Listing 3-8) executes the function cleanup_unit() for the row, column, and box containing the specified cell.

Listing 3-8. cleanup_around.c

/* cleanup_around.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "cleanup_around.h"
#include "cleanup_unit.h"
#include "def.h"

void cleanup_around(int k, int j) {
#ifdef LOG_IN_OUT
  printf("--- cleanup_around (%d,%d) >>>
", k, j);
#endif
  cleanup_unit("row", k, j, row[k]);
  if (!problem_found) cleanup_unit("column", k, j, col[j]);
  if (!problem_found) cleanup_unit("box", k, j, box[k/3*3+j/3]);
#ifdef LOG_IN_OUT
  printf("<<< cleanup_around (%d,%d) ---
", k, j);
#endif
  }

You now have to look at cleanup_unit() (see Listing 3-9).

Listing 3-9. cleanup_unit.c

/* cleanup_unit.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "cleanup_around.h"
#include "cleanup_unit.h"
#include "def.h"
#include "remove_candidate.h"

void cleanup_unit(char *what, int kElem, int jElem, char unit[9][2]) {
#ifdef LOG_IN_OUT
  printf("--- cleanup_unit (%s) for (%d,%d) >>>
", what, kElem, jElem);
#endif
  char *elem = grid[kElem][jElem];
  if (elem[0] == 1) {
    int i = 0;
    do { i++; } while (elem[i] == FALSE);
    for (int j1 = 0; j1 < 9 && !problem_found; j1++) {
      int kR = unit[j1][ROW];
      int kC = unit[j1][COL];
      if ((kR != kElem || kC != jElem) &&
          grid[kR][kC][i] != FALSE
          ) {
        char mess[40];
        sprintf(mess, "cleanup_unit [%s of (%d,%d)]",
                what, kElem, jElem
                );
        remove_candidate(mess, i, kR, kC);
        if (grid[kR][kC][0] == 1 && !problem_found) {
          cleanup_around(kR, kC);
          }
        }
      }
    }
#ifdef LOG_IN_OUT
  printf("<<< cleanup_unit (%s) for (%d,%d) ---
", what, kElem, jElem);
#endif
  }

If cleanup_unit() finds that the cell with coordinates (kElem,jElem) is solved (i.e., elem[0] == 1), it removes from the given unit all the candidates for the number i that solve the cell. It does so by executing the function remove_candidate(). The bit highlighted in bold is worth examining in more detail: if removing a candidate from the cell (kR,kC) leaves the cell with a single candidate, the function executes cleanup_around() for that cell. This is how it applies the strategy naked single, but the interesting bit is that cleanup_around(), as you have seen, executes cleanup_unit(). It means that cleanup_unit() executes itself recursively through cleanup_around().

You can only execute a function recursively if there is a well-defined termination condition, to ensure that the recursion doesn’t continue forever (i.e., until the stack overflows and the program crashes). This is certainly true in the Solver’s case, because you only execute cleanup_around() recursively when you solve a cell, and there are only 81 cells in a puzzle.

remove_candidate() is straightforward (see Listing 3-10).

Listing 3-10. remove_candidate.c

/* remove_candidate.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "remove_candidate.h"

void remove_candidate(*caller, int i, int k, int j) {
  grid[k][j][i] = FALSE;
  grid[k][j][0]--;
#ifdef LOG_REMOVE_CANDIDATE
  if (!silent) {
    printf("%s: removed %d from (%d,%d)
", caller, i, k, j);
    }
#endif
  if (grid[k][j][0] < 1) {
    if (!silent) {
      printf("*** No candidates left in (%d,%d)
", k, j);
      }
    problem_found = TRUE;
    }
  }

The statements highlighted in bold are the key ones: the first one sets the ith digit of the cell (k,j) to FALSE, and the second one decrements the counter of candidates. Notice that remove_candidate() doesn’t check whether i is indeed a candidate present in (k,j). You must do it before executing the function. The execution of remove_candidate() for a candidate that is not present in the specified cell would cause an erroneous decrement of the counter of candidates of the cell (i.e., grid[k][j][0]), with catastrophic results.

solve()

The function solve() keeps executing strategy functions until all 81 cells are solved or until two successive executions of the strategies are unable to remove a single candidate (see Listing 3-11).

Listing 3-11. solve.c

/* solve.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "count_candidates.h"
#include "def.h"
#include "display.h"
#include "display_string.h"
#include "execute_strategies.h"
#include "keep_going.h"
#include "solve.h"

void solve() {
#ifdef LOG_IN_OUT
  printf("--- solve >>>
");
#endif
  if (!backtracking) n_strats_used = 0;
  int n_candidates = count_candidates();
  int n_candidates_old = n_candidates + 1;

  while (keep_going()  &&  n_candidates < n_candidates_old) {
    n_candidates_old = n_candidates;
    if (keep_going()  &&  !execute_strategies(0)) {
      if (keep_going()  &&  !execute_strategies(1)) {
        if (keep_going()  &&  !execute_strategies(2)) {
          execute_strategies(3);
          }
        }
      }
    n_candidates = count_candidates();
    }
#ifdef LOG_IN_OUT
  printf("<<< solve ---
");
#endif
  }

keep_going() is a one-line function defined to improve readability (see Listing 3-12).

Listing 3-12. keep_going.c

/* keep_going.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "count_solved.h"
#include "def.h"

int keep_going(void) {
  return (count_solved() < 81  &&  !problem_found);
  }

Therefore, the main loop continues executing as long as some cells are still unsolved, the puzzle remains consistent, and the previous loop execution has removed at least one candidate.

The core of solve() is in the four lines highlighted in bold (note that the braces are syntactically unnecessary and are only present to make the code more readable). Each line contains the execution of execute_strategies() (see Listing 3-13) for increasing levels of difficulty, from 0 to 3.

But, because execute_strategies() only returns TRUE if a strategy has removed at least one candidate, solve() only tries more difficult strategies when the easier ones have had no effect at all. For example, if execute_strategies(1) returns TRUE, it means that one of the level 1 strategies has succeeded in removing at least one candidate. Then, the condition of the third if fails, and solve(), instead of proceeding with execute_strategies(2), updates n_candidates and starts a new loop iteration with level 0 strategies. If execute_strategies(1) returns FALSE, it means that no level 1 strategy has managed to remove any candidate, and solve() tries level 2 strategies by invoking execute_strategies(2) within the condition of the if that follows.

Listing 3-13. execute_strategies.c

/* execute_strategies.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "count_candidates.h"
#include "count_solved.h"
#include "def.h"
#include "display.h"
#include "display_string.h"
#include "execute_strategies.h"
#include "keep_going.h"
#include "unique_loop.h"

/*
 * It returns TRUE when at least one candidate is removed.
 *
 * It goes through all the strategies of the level, but only as long as no
 * candidate is removed.  When that happens, it aborts the loop and returns.
 */
int execute_strategies(int level) {
#ifdef LOG_IN_OUT
  printf("--- execute_strategies >>>
");
#endif
  f_ptr_t *strats = strat_all[level];
  char **strat_names = strat_all_names[level];
  int n_strat = n_strat_all[level];
  int n_candidates = count_candidates();
  int n_candidates_initial = n_candidates;
  for (  int k = 0;
         k < n_strat && keep_going()  &&  n_candidates == n_candidates_initial;
         k++
         ) {
    (void)strats[k]();
    n_candidates = count_candidates();
    if (n_candidates < n_candidates_initial) {
      if (!backtracking) {
        strats_used[n_strats_used] = level * 10 + k;
        n_strats_used++;
        }
      if (!silent) {
        printf("strategy: after '%s' the grid contains "
            "%d solved cells

", strat_names[k], count_solved()
            );
        }
      if (!silent) { display(); display_string(); }
      }
    }
#ifdef LOG_IN_OUT
  printf("<<< execute_strategies ---
");
#endif
  return (n_candidates < n_candidates_initial);
  }

To guarantee that the program solves a puzzle with the simplest possible strategies, the while-loop in solve() must restart from level 0 strategies whenever any strategy removes at least one candidate. To see how this happens, look at the for-loop in execute_strategies() (see Listing 3-13) and in particular to the end condition highlighted in bold: the loop terminates as soon as a strategy causes the number of candidates to decrease. The decrease of the number of candidates also causes the function to return TRUE, which, as you have already seen, forces the while-loop in solve() to restart from level 0 strategies.

If no strategy of the given level removes candidates, the for-loop runs to completion and execute_strategies() returns FALSE, thereby forcing solve() to attempt more difficult strategies until it reaches level 3.

Counting

In the previous sections, you have already seen that there are two counting functions: count_solved() (see Listing 3-14) and count_candidates() (see Listing 3-15). Their names say it all.

Listing 3-14. count_solved.c

/* count_solved.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "count_solved.h"
#include "def.h"

int count_solved() {
#ifdef LOG_IN_OUT
  printf("--- count_solved >>>
");
#endif
  int result = 0;
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      if (grid[k][j][0] == 1) result++;
      }
    }
#ifdef LOG_IN_OUT
  printf("<<< count_solved ---
");
#endif
  return result;
  }

Listing 3-15. count_candidates.c

/* count_candidates.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"

int count_candidates() {
#ifdef LOG_IN_OUT
  printf("--- count_candidates >>>
");
#endif
  int result = 0;
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      result += grid[k][j][0];
      }
    }
#ifdef LOG_IN_OUT
  printf("<<< count_candidates ---
");
#endif
  return result;
  }

As you can see, the only difference between count_solved() and count_candidates() is that count_solved() adds 1 for each cell that has a single candidate, while count_candidates() adds up the counter of candidates of all cells. You could have written a single function and used an argument to choose between the two statements, as in the following:

int count(int what) { // what: 0 for counting solved, otherwise counting candidates
  int result = 0;
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      if (what) result += grid[k][j][0];     // count candidates
      else if (grid[k][j][0] == 1) result++; // count solved
      }
    }
  return result;
  }

The only advantage of having two separate functions is that you are more likely to avoid confusion and can more easily insert printf()s for debugging purposes. Not a big deal either way.

Checking Consistency

You probably noticed in Listing 3-5 the invocation of inconsistent_grid(). This function (see Listings 3-16 and 3-17) ensures that the grid does not contain empty cells (i.e., without candidates at all) or units with more than one cell solved by the same number (e.g., two 7s in the same row).

Listing 3-16. inconsistent_grid.c

/* inconsistent_grid.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "inconsistent_grid.h"
#include "inconsistent_unit.h"

int inconsistent_grid() {
  int result = FALSE;
  for (int k = 0; k < 9 && !result; k++) {
    result |= inconsistent_unit("row", k, row[k]);
    if (!result) {
      result |= inconsistent_unit("column", k,
                                  col[k]
                                  );
      if (!result) {
        result |= inconsistent_unit("box", k, box[k]);
        }
      }
    } // for (int k..
  return result;
  }

inconsistent_grid() executes inconsistent_unit() for every row, column, and box of the Sudoku, and aborts the execution immediately if one of the units is inconsistent.

Listing 3-17. inconsistent_unit.c

/* inconsistent_unit.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "inconsistent_unit.h"

int inconsistent_unit(char *what, int kG, char unit[9][2]) {
  int result = FALSE;
  int i_vect[10] = {0};
  for (int k = 0; k < 9 && !result; k++) {
    int kR = unit[k][ROW];
    int kC = unit[k][COL];
    char *elem = grid[kR][kC];
    if (elem[0] < 1) {  // we have an empty cell
      result = TRUE;
      if (!silent) {
        printf("*** (%d,%d) has %d candidates
", kR, kC, elem[0]);
        }
      } // if (elem[0]..
    else if (elem[0] == 1) {
      int i = 0;
      do { i++; } while (!elem[i]);
      if (i_vect[i] == FALSE) {
        i_vect[i] = TRUE;
        }
      else {  // we have a duplicate solution
        result = TRUE;
        if (!silent) {
          printf("*** More than a single %d solution in %s %d
", i, what, kG);
          }
        } // else..
      } // else if (elem[0]..
    } // for (int k..
  problem_found = result;
  return result;
  }

Input/Output

You have become used to interacting with computer programs via smart dialog boxes and flashy graphics. In fact, the graphical user interface (GUI) is what drives the specification and a large portion of the design of most applications. But a program to solve and generate Sudoku puzzles is a different type of program, because it doesn’t require much interaction with the user. In particular, the Solver program only needs one input: the initial Sudoku. And as outputs, it only needs to list what candidates it eliminates and why, followed by a display of the solved puzzle.

You are interested in solving Sudokus, not in fancy graphics. Aren’t you?

Therefore, the Solver accepts a puzzle as a string of 81 characters, representing the contents of the cells scanned from left to right and from top to bottom, with empty cells represented by zeroes. For example, you would input the partially solved Sudoku of Figure 1-2 with the following string:

409701003005400200060503040078614900000958400954372186013840020042100308890235014

To provide a Sudoku to be solved in the form of a string of characters might seem awkward, but it is in fact more convenient than having a fancy input interface that forces you to fill in a Sudoku grid by hand. Typing a command-line directive often is much more efficient than clicking on dialog buttons.

The information the program generates also has a very simple format. The program sends one or two lines of text to the standard output every time something happens (i.e., when the application of a strategy results in solving a cell or removing candidates). It also shows the current state of the puzzle it is solving. Not with graphics but with ASCII characters. For example, the program would display the puzzle of Figure 1-2 as shown in Figure 3-1.

The solved digits are highlighted by round brackets and placed in the middle of their cells. See Listing 3-18 for the full code of the function that does the display.

Listing 3-18. display.c

/* display.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "display.h"

void display() {
  char *h =
        "  ++---+---+---++---+---+---++---+---+---++";
  char *hh =
        "  ++===+===+===++===+===+===++===+===+===++";
  int jBase[] = {2, 6, 10, 15, 19, 23, 28, 32, 36};
  printf(
      "     0   1   2    3   4   5    6   7   8
"
      );
  for (int k = 0; k < 9; k++) {
    if (k%3 == 0) {
      printf("%s
", hh);
      }
    else {
      printf("%s
", h);
      }
    //       000 000 111  111 122 222  223 333 333
    //       234 678 012  567 901 345  890 234 678
    char top[42] =
          "||   |   |   ||   |   |   ||   |   |   ||";
    char mid[42] =
          "||   |   |   ||   |   |   ||   |   |   ||";
    char bot[42] =
          "||   |   |   ||   |   |   ||   |   |   ||";
    char *displ[42] = {top, mid, bot};
    for (int j = 0; j < 9; j++) {
      if (grid[k][j][0] == 1) {
        int i = 0;
        do { i++; } while (grid[k][j][i] == 0);
        mid[jBase[j]] = '(';
        mid[jBase[j]+1] = '0'+i;
        mid[jBase[j]+2] = ')';
        }
      else {
        for (int i = 0; i < 9; i++) {
          if (grid[k][j][i+1] != 0) {
            displ[i/3][jBase[j] + i%3] = '0' + (i+1);
            }
          } // for (int i..
        } // else..
      } // for (int j..
    printf("  %s
", displ[0]);
    printf("%d %s
", k, displ[1]);
    printf("  %s
", displ[2]);
    }
  printf("%s
", hh);
  }

For each row of the grid, display() prepares three character arrays (top, mid, and bot) and then fills them in with the candidates. The tricky bit is to make the line offsets defined in jBase point to the sequences of empty spaces in top/mid/bot. To make sense of it, refer to the offsets of the empty spaces listed as comments above the character arrays.

Notice that some closed braces are followed by a comment indicating what block they are closing. This is a practice that makes the source code easier to read when you nest more than a couple of block statements and/or the open and close braces are at a certain distance from each other. Software development environments have made it almost redundant, because they highlight for you the open brace that corresponds to the closed brace you click on (and vice versa), but the little comments are still useful when reading a listing, especially when you print it out.

Finally, the program can display a Sudoku puzzle as a string of 81 characters, via the function display_string() (see Listing 3-19).

Listing 3-19. display_string.c

/* display_string.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include "def.h"
#include "display_string.h"

void display_string() {
  printf("****** ");
  for (int k = 0; k < 9; k++) {
    for (int j = 0; j < 9; j++) {
      char *elem = grid[k][j];
      if (elem[0] > 1) {
        printf("0");
        }
      else {
        int i = 0;
        do { i++; } while (!elem[i]);
        printf("%d", i);
        }
      }
    }
  printf("
");
  }

Summary

In this chapter, I have explained the main program of the Sudoku Solver, together with its utility functions to initialize the Sudoku arrays, solve the puzzle, and display information. The next chapter is the first one of a series of chapters dedicated to the implementation of the solving strategies. First up: the level 0 unique strategy.