You obtain a multi-grid Sudoku when you combine two or more classic puzzles by partially overlapping them. For example, Figure 18-1 shows a double Sudoku.

You solve a double Sudoku by solving the two 9x9 puzzles normally, but whenever you solve one of the cells grayed in Figure 18-1, that solution is valid for both puzzles.

There Are Many Different Multi-Grid Sudokus

To explore the way in which you can combine several Sudoku grids to form composite puzzles, let’s reduce multi-grid Sudokus to the outlines of their boxes, as shown in the examples in Figure 18-2.

All the puzzles in Figure 18-2 overlap by one of their corner boxes, but you can also overlap two, three, four, and even six boxes, as shown in Figure 18-3.

You can also obtain new configurations with rotations and flips. For example, you can obtain three additional configurations by rotating the third puzzle of Figure 18-2, as shown in Figure 18-4.

Theoretically, there is no limit to the number of grids you can combine. For an example of a very complex configuration, take a deep breath and have a look at Figure 18-5 (the non-overlapping boxes are not in white because otherwise you would have had problems in seeing the holes in the grid).

If you are interested in such “monster” Sudokus, I’m afraid you will have to make your own version of the Generator, because this book is only going to show you how you can create four configurations of multi-grid Sudokus: the first two of Figure 18-2 plus those shown in Figure 18-6 (the second one is a “samurai Sudoku”), with one-box overlapping, no rotations, and no flippings.

I left out the third configuration of Figure 18-2 because its shape didn’t appeal to me, but also to simplify the code. I initially had also discarded the four-grid configuration on the left of Figure 18-6, but, after I completed the implementation of the two-, three-, and five-grid puzzles, I realized that exactly the same code would work for the four-grid puzzle as well. I only needed to change an if-condition from

(N_GRIDS == 2  ||  N_GRIDS == 3  ||  N_GRIDS == 5)

to

(N_GRIDS >= 2  &&  N_GRIDS <= 5)

It was too good to ignore, although I have to admit that I find the four-grid configuration even less appealing than the three-grid one shaped like a Mickey Mouse’s head!

How You Join the Grids

To fully understand the code of the Generator, you need to be familiar with the issues that arise when you join grids. First of all, Figure 18-7 shows how I numbered the grids to form multi-grid Sudokus.

Consider the simplest case of multi-grid puzzles shown in Figure 18-1, with only the two grids 0 and 1. Box 8 of grid 1 overlaps with box 0 of grid 0. This means that the three clues 1, 4, and 9 belong to both grids. But it also means that the content of the two boxes must remain identical when they are fully solved.

As you know, when you configure the Generator to create several puzzles (by setting N_SEEDS to a value greater than 1), the program starts working on each puzzle by filling up its grid.

But, if you generate two grids that you want to combine to form a double Sudoku, you must modify the Generator in such a way that box 8 of puzzle 1 contains the nine numbers in exactly the same order as they appear in box 0 of puzzle 0.

You have two alternatives: either you predefine box 8 of the second grid so that the match is there from the start, or you fill in the second grid at random and then “play” with the numbers to achieve the match.

The Generator, as you will see shortly, uses the second alternative. To see how it works, suppose that the box on the left of Figure 18-8 solves box 0 of puzzle 0, while the right box solves box 8 of grid 1.

After reading Chapter 17, you should be comfortable with the idea that the Sudoku numbers are just a particular choice of symbols. Then, all you need to do is change all 3s (in the whole puzzle, not just in box 8) of grid 1 to 5s, all 4s to 8s . . . and all 1s to 6s. If you do so, the two boxes will match!

Once you have made the shared boxes of both puzzles identical, you still need to ensure that in box 8 of puzzle 1 you remove all and only the clues you have already removed from box 0 of puzzle 0. Only then can you integrate the two puzzles.

How the Generator Does It

After writing the Generator for classic Sudokus, to implement multi-grid puzzles, you need to modify sudoku_gen.c and add a couple of new modules.

To see all the changes and to understand how they work together, let’s go through the full code of the main program as shown in Listing 18-1. Note that all the new code, as well as the relevant parts you already saw in Chapter 15, is in bold.

Listing 18-1. sudoku_gen.c—Modified for Multi-grid Sudokus

/* sudoku_gen.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "brute_comp.h"
#include "count_solved.h"
#include "def.h"
#include "display.h"
#include "display_string.h"
#include "fill.h"
#include "inconsistent_grid.h"
#include "inconsistent_unit.h"
#include "init.h"
#include "in_box.h"
#include "list_solved.h"
#include "multi_html.h"
#include "save_html.h"

#define LOG_TO_FILE___NO
#define FILE_NAME "puzzles.txt"

#define SAVE_HTML_PUZZLE
#define SAVE_HTML_SOLUTION

// N_GRIDS is defined in multi_html.h.
// When N_GRIDS is between 2 and 5, it triggers the creation of multi-grid
// puzzles. With any other value, the Generator creates a classic Sudoku.
#define DO_MULTI_GRID (N_GRIDS >= 2  &&  N_GRIDS <= 5)

// Parameters
#define N_SET_QUADS 5
#define N_SET_PAIRS 10
#define N_SET_CELLS 0
#define ADDITIONAL_CELLS TRUE
#define FIRST_SEED 123456
#define N_SEEDS 1

// Global variables
char *unit_names[3] = {"row", "column", "box"};
char grid[9][9];
char row[9][9][2];
char col[9][9][2];
char box[9][9][2];
char puzzle[9][9];
int silent = FALSE;

// Variables and functions local to this module
char solved[9][9];
int r_1[81];
int c_1[81];
int k_cell;
int remove_quads(int k_puz);
int remove_pairs(int k_puz);
void make_clue_list(void);
int remove_clues(int k_puz);
void remove_more_clues(int k_puz);
int check_uniqueness(void);

// The following table identifies the box of grid 0 that overlaps with other
// grids when creating multi-grid Sudokus.
// The first box refers to puzzle0 and second one to the other puzzle:
//
// N_GRIDS  kPuz=1  kPuz=2  kPuz=3  kPuz=4
//     2    b0-b8
//     3    b0-b8   b8-b0
//     4    b0-b8   b8-b0   b2-b6
//     5    b0-b8   b8-b0   b2-b6   b6-b2
//
// Puzzle:     0   1   2   3   4
int box0[] = {-1,  0,  8,  2,  6};

//======================================================================== main
int main(int argc, char *argv[]) {
  printf("*** sudoku_gen ***
");
  char mess[32];
  int n_seeds = N_SEEDS;
  k_try = 0;

#if DO_MULTI_GRID
  // When creating multi-grid puzzles, set n_seed to the number of
  // puzzles that you need
  n_seeds = N_GRIDS;
#endif

  // Open a file to log the results
  FILE *fp = NULL;
#ifdef LOG_TO_FILE
  fp = fopen(FILE_NAME, "a");
  if (fp == NULL) {
    printf("Unable to open the file '%s' for reading
", FILE_NAME);
    return EXIT_FAILURE;                                                  //==>
    }
#endif

  // Try all the seeds in the given range
  unsigned long start_time = clock();

  for (int k_seed = 0; k_seed < n_seeds; k_seed++) {
    int seed = FIRST_SEED + k_seed;
    srand(seed);
    int brute_result;
    int n;

    // Keep repeating the generation until you find a unique solution
    char puzzle_string[82];
    char solution_string[82];
    do {

      // Generate a solved Sudoku
      do { init(); } while (fill());

      // Save the solved Sudoku
      for (int k = 0; k < 9; k++) {
        for (int j = 0; j < 9; j++) {
          solved[k][j] = grid[k][j];
          puzzle[k][j] = grid[k][j];
          }
        }

#if DO_MULTI_GRID
      if (k_seed > 0) {
        // You arrive here if you are creating a multi-grid puzzle and
        // have already created the first one (puzzle 0).
        int k0 = box0[k_seed]/3*3;
        int j0 = box0[k_seed]%3*3;
        int kk = overlapping_box[k_seed]/3*3;
        int jj = overlapping_box[k_seed]%3*3;

        // Build the look-up list of numbers to match puzzle 0 when creating
        // subsequent grids.
        char map[10] = {0};
        for (int k = 0; k < 3; k++) {
          for (int j = 0; j < 3; j++) {
            map[(int)grid[(kk + k)][jj + j]] =
                multi_string[0][SOL][(k0 + k)*9 + j0 + j] - '0'
                ;
            }
          }

        // Convert the numbers in the grid and save the modified grid
        for (int k = 0; k < 9; k++) {
          for (int j = 0; j < 9; j++) {
            grid[k][j] = map[(int)grid[k][j]];
            solved[k][j] = grid[k][j];
            puzzle[k][j] = grid[k][j];
            }
          }

        // Make the box that overlaps puzzle 0 identical to the
        // corresponding one of puzzle 0
        for (int k = 0; k < 3; k++) {
          for (int j = 0; j < 3; j++) {
            grid[(kk + k)][jj + j] =
                multi_string[0][PUZ][(k0 + k)*9 + j0 + j] - '0'
                ;
            }
          }
        }
#endif

      //========= Remove N_SET_QUADS quadruples of clues
      if (N_SET_QUADS > 0) {
        int success = remove_quads(k_seed);
        if (!success) {
          brute_result = BRUTE_COMP_DIFFERENT;
          goto skip;                                                      //==>
          }
        }

      //========= Remove N_SET_PAIRS pairs of clues
      if (N_SET_PAIRS > 0) {
        int success = remove_pairs(k_seed);
        if (!success) {
          brute_result = BRUTE_COMP_DIFFERENT;
          goto skip;                                                      //==>
          }
        }

      //========= Remove N_SET_CELLS individual clues and then some more
      make_clue_list();
      k_cell = 0;
      if (N_SET_CELLS > 0) {
        int success = remove_clues(k_seed);
        if (!success) {
          brute_result = BRUTE_COMP_DIFFERENT;
          goto skip;                                                      //==>
          }
        }
      if (ADDITIONAL_CELLS && k_cell < 81) remove_more_clues(k_seed);

      //========= Check whether the solution is really unique
      brute_result = check_uniqueness();

      //========= Done
      for (int k = 0; k < 9; k++) {
        for (int j = 0; j < 9; j++) {
          grid[k][j] = puzzle[k][j];
          }
        }
      n = count_solved();
      if (!silent && fp == NULL) {
        display();
        sprintf(mess, "seed %d %d", seed, n);
        display_string(mess);
        printf("The puzzle contains %d clues:", n);
        list_solved(stdout);
        }

skip:                                                                    // <==
      k_try++;
      printf("%d: %s
",
          k_try,
          (brute_result == BRUTE_COMP_DIFFERENT) ? "No" : "Yes"
          );
      } while (brute_result == BRUTE_COMP_DIFFERENT);

    // Save puzzle and solution into strings
    int kar = 0;
    for (int k = 0; k < 9; k++) {
      for (int j = 0; j < 9; j++) {
        puzzle_string[kar] = puzzle[k][j] + '0';
        solution_string[kar] = solved[k][j] + '0';
        kar++;
        }
      }
    puzzle_string[kar] = '';
    solution_string[kar] = '';

#if DO_MULTI_GRID
    // Save the puzzle and solution strings to be combined later into
    // a multi-grid Sudoku
    for (int i = 0; i < 82; i++) { // copy also the '' at the end
      multi_string[k_seed][PUZ][i] = puzzle_string[i];
      multi_string[k_seed][SOL][i] = solution_string[i];
      }
#endif

#ifdef SAVE_HTML_PUZZLE
    save_html(puzzle_string, seed, "p");
#endif

#ifdef SAVE_HTML_SOLUTION
    save_html(solution_string, seed, "s");
#endif
    if (fp != NULL) {
      printf("#%d
", k_seed);
      fprintf(fp, "%s	%d", puzzle_string, seed);
      if (brute_result != BRUTE_COMP_DIFFERENT) {
        fprintf(fp, "	%d", n);
        list_solved(fp);
        }
      fprintf(fp, "
");
      }
    } // for (k_seed..

#if DO_MULTI_GRID
  multi_html(FIRST_SEED, PUZ);
  multi_html(FIRST_SEED, SOL);
#endif

  unsigned long end_time = clock();
  printf("********* done in %ld microseconds
", end_time - start_time);
  if (fp != NULL) fclose(fp);
  return EXIT_SUCCESS;
  }

The first relevant part is the inclusion of in_box.h and multi_html.h (see Listing 18-2 for in_box.c and Listing 18-3 for multi_html.c). Essentially, in_box() checks whether a particular cell belongs to a box, while multi_html() is an extension of save_html(), which you know from Chapter 15.

The line

#define DO_MULTI_GRID (N_GRIDS >= 2  &&  N_GRIDS <= 5)

allows you to easily switch on and off code within sudoku_gen.c that is only to be executed when generating multi-grid puzzles. You only need to set N_GRIDS to 1 within multi_html.h to make the Generator behave as described in Chapter 15.

Listing 18-1 highlights the four declarations

int remove_quads(int k_puz);
int remove_pairs(int k_puz);
int remove_clues(int k_puz);
void remove_more_clues(int k_puz);

because the functions I wrote for the original Generator to create classic Sudokus didn’t need any argument, as each created a puzzle that consisted of a single grid.

You use the one-dimensional array

int box0[] = {-1,  0,  8,  2,  6};

to determine which boxes of grid 0 overlaps with the other grids. For example, box0[3] is 2 because grid 3 is positioned top right with respect to grid 0, where grid 0’s box 2 is.

The statement

n_seeds = N_GRIDS;

is where you tell the Generator that it needs to create as many grids as are to appear in the composite Sudoku. Note that n_seeds originally allowed you to create many puzzles with a single run of the Generator. This is not possible with multi-grid Sudokus because the Generator, in the implementation I am describing, relies on n_seeds to create a single composite puzzle. If you need to create many multi-grid Sudokus, you should be able to adapt the existing code to do so. For example, you could enclose a loop that generates N_GRIDS Sudokus inside the loop with control variable k_seed. The only thing you would need to be careful with would be initializing/resetting all the affected variables.

The next block of conditional code is more substantial, but note that it is only executed when k_seed is greater than 0. In other words, the Generator creates the first puzzle of a multi-grid Sudoku (i.e., with k_seed == 0) in exactly the same way as it creates a classic, single-grid puzzle.

When DO_MULTI_GRID is true and you are creating puzzles with k_seed > 0, you need to “play with the numbers” of the current puzzle as I briefly described in the section “How You Join the Grids,” so that the two overlapping boxes of the current puzzle and puzzle 0 become identical.

The two expressions box0[k_seed]/3*3 and box0[k_seed]%3*3 give you the coordinates of the top-left cell that puzzle 0 shares with the current puzzle. This is because box0[] identifies the overlapping box of puzzle 0. For example, if you are currently generating puzzle 3, box0[3] is 2, consistent with the fact that the overlapping box of puzzle 0 is the top-right one. Then, k0 is 2/3*3 = 0 (because the result of a division between integers is truncated) and j0 is 2%3*3 = 2*3 = 6 (because the remainder of 2 divided by 3 is 2).

The two definitions

int kk = overlapping_box[k_seed] / 3 * 3;
int jj = overlapping_box[k_seed] % 3 * 3;

do the same for the current puzzle. overlapping_box[] is defined in multi_html.c as follows:

int overlapping_box[] = {0, 8, 0, 6, 2};

So, for example, puzzle 3’s box that overlaps with puzzle 0 is the bottom-left one. Accordingly, overlapping_box[3] is 6 and the top-left cell of the overlap has coordinates (6,6).

Once you know the top-left cells of the two overlapping boxes, you can map the numbers in the current puzzle’s box with the corresponding ones in the puzzle 0’s box:

char map[10] = {0};
for (int k = 0; k < 3; k++) {
  for (int j = 0; j < 3; j++) {
    map[(int)grid[(kk + k)][jj + j]] =
        multi_string[0][SOL][(k0 + k)*9 + j0 + j] - '0'
        ;
    }
  }

where SOL and multi_string[][][] are defined in multi_html.h as follows:

#define PUZ 0
#define SOL 1
extern char multi_string[N_GRIDS][2][82];

multi_string[][][] is used to save all Sudoku strings (both of the solved and the unsolved puzzle) of a multi-grid Sudoku.

The map is a character array in which the position of each character corresponds to a number in the overlapping box of the current puzzle, while the character is the corresponding number in the overlapping box of puzzle 0.

For example, with the two overlapping boxes in Figure 18-8, the algorithm results in map[1] to map[9] being set to the characters 675834291. Figure 18-8 refers to a double Sudoku. Therefore, the two overlapping boxes are box 0 of puzzle 0 and box 8 of puzzle 1. Accordingly, (k0,j0) is (0,0) and (kk,jj) is (6,6). The map assignment in the first iteration of the two loops, with both k and j set to 0, then results in map[3] = '5' . The second assignment is map[4] = '8' , the third map[2] = '7' , etc., until the map is completed with map[1] = '6'.

Once the map is done, it is easy to convert the current puzzle with

for (int k = 0; k < 9; k++) {
  for (int j = 0; j < 9; j++) {
    grid[k][j] = map[(int)grid[k][j]];
    }
  }

The last thing you need to do at this point of the puzzle-creation process is to remove from the grid the clues that were removed when creating puzzle 0. You do this by simply overwriting in grid the box of the current puzzle with the box of puzzle 0.

for (int k = 0; k < 3; k++) {
  for (int j = 0; j < 3; j++) {
    grid[(kk + k)][jj + j] =
        multi_string[0][PUZ][(k0 + k)*9 + j0 + j] - '0'
        ;
    }
  }

You will recall that when I described the remove_*() functions in the section “Removing Clues to Make a Puzzle” in Chapter 15, I said that in

for (int k = 0; k < 4; k++) {
  int kR = quad[k][ROW];
  int kC = quad[k][COL];
  if (kPuz == 0  ||  !in_box(kR, kC, overlapping_box[kPuz])) {
    grid[kR][kC] = 0;
    }
  }

the reason for making the removal of the clue from the cell with coordinates (kR,kC) conditional would become clear in Chapter 18. You now know that when the Generator removes clues from the puzzles 1 to 4 of multi-grid Sudokus, one box of those puzzles is already identical to the corresponding box of puzzle 0. You must therefore ensure that the remove_*() functions leave those boxes unchanged. This is exactly what the condition (kPuz == 0  || !in_box(kR, kC, overlapping_box[kPuz]) does. The first part tells you that puzzle 0 is just a standard puzzle. But when kPuz is not 0, you only want to remove clues from boxes other than the preformatted (i.e., overlapping) one. As in_box() returns TRUE if a cell belongs to a given box, as shown in Listing 18-2, you only need to pass to in_box() the current cell and the ID of overlapping box to identify the cells from which you can safely remove the clues.

Listing 18-2. in_box.c

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

int in_box(int kR, int kC, int kB) {
  int kkR = kB / 3 * 3;
  int kkC = kB % 3 * 3;
  return (kR >= kkR  &&  kR < kkR + 3  &&  kC >= kkC  &&  kC < kkC + 3);
  } // in_box

The next block of conditional code needed to create multi-grid puzzles saves solved and unsolved puzzles in the array multi_string[][][]

for (int i = 0; i < 82; i++) { // copy also the '' at the end
  multi_string[k_seed][PUZ][i] = puzzle_string[i];
  multi_string[k_seed][SOL][i] = solution_string[i];
  }

This is necessary because you need all two to five puzzles in order to display the multi-grid puzzle and its solution with

multi_html(FIRST_SEED, PUZ);
multi_html(FIRST_SEED, SOL);

which I describe in the following section.

Displaying a Multi-Grid Sudoku

In Chapter 15, you saw how to save a puzzle to disk with save_html() (Listing 15-25). To save a multi-grid Sudoku to disk in HTML format, you need first to join the grids of the individual puzzles. The equivalent of save_html.c for multi-grids puzzle is the module multi_html.c shown in Listing 18-3.

Listing 18-3. multi_html.c

/* multi_html.c
 *
 * This module must be able to display all different types of multi-grid
 * puzzles (only the boxes are shown):
 *
 * +---+---+---+
 * |   |   |   |
 * +---+---+---+
 * |   | 1 |   |
 * +---+---+---+---+---+         N_GRIDS == 2 (double Sudokus)
 * |   |   |   |   |   |
 * +---+---+---+---+---+
 *         |   | 0 |   |
 *         +---+---+---+
 *         |   |   |   |
 *         +---+---+---+
 *
 * +---+---+---+
 * |   |   |   |
 * +---+---+---+
 * |   | 1 |   |
 * +---+---+---+---+---+
 * |   |   |   |   |   |
 * +---+---+---+---+---+
 *         |   | 0 |   |           N_GRIDS == 3
 *         +---+---+---+---+---+
 *         |   |   |   |   |   |
 *         +---+---+---+---+---+
 *                 |   | 2 |   |
 *                 +---+---+---+
 *                 |   |   |   |
 *                 +---+---+---+
 *
 * +---+---+---+   +---+---+---+
 * |   |   |   |   |   |   |   |
 * +---+---+---+   +---+---+---+
 * |   | 1 |   |   |   | 3 |   |
 * +---+---+---+---+---+---+---+
 * |   |   |   |   |   |   |   |
 * +---+---+---+---+---+---+---+
 *         |   | 0 |   |           N_GRIDS == 4
 *         +---+---+---+---+---+
 *         |   |   |   |   |   |
 *         +---+---+---+---+---+
 *                 |   | 2 |   |
 *                 +---+---+---+
 *                 |   |   |   |
 *                 +---+---+---+
 *
 * +---+---+---+   +---+---+---+
 * |   |   |   |   |   |   |   |
 * +---+---+---+   +---+---+---+
 * |   | 1 |   |   |   | 3 |   |
 * +---+---+===+===+===+---+---+
 * |   |   I   |   |   I   |   |
 * +---+---+---+---+---+---+---+
 *         I   | 0 |   I           N_GRIDS == 5 (samurai)
 * +---+---+---+---+---+---+---+   (the central puzzle is highlighted)
 * |   |   I   |   |   I   |   |
 * +---+---+===+===+===+---+---+
 * |   | 4 |   |   |   | 2 |   |
 * +---+---+---+   +---+---+---+
 * |   |   |   |   |   |   |   |
 * +---+---+---+   +---+---+---+
 *
 * The cell borders are defined like in save_html.c, but their position
 * and the size of the HTML table depend on the type of puzzle.
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "def.h"
#include "in_box.h"
#include "multi_html.h"

// Define the number of rows and columns needed for the multi-grid
#if N_GRIDS == 2
#define SIZE 15
#else
#define SIZE 21
#endif

char multi_string[N_GRIDS][2][82];

// The following table identifies the box of each grid that overlaps with
// a corner box of grid 0 when creating multi-grid Sudokus.
//
// N_GRIDS  kPuz=1  kPuz=2  kPuz=3  kPuz=4
//     2      8
//     3      8       0
//     4      8       0       6
//     5      8       0       6       2
//
// Puzzle:               0  1  2  3  4
int overlapping_box[] = {0, 8, 0, 6, 2};

void multi_html(int seed, int what) {
  char *header_1 =
      "<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "
        ""http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
"
      "<html xmlns="http://www.w3.org/1999/xhtml">
"
      "<head>
"
      "<title>"
      ;
  char *header_2 =
      "</title>
"
      "<meta http-equiv="Content-type" "
        "content="text/html;charset=UTF-8"/>
"
      "<style type="text/css">
"
      "table {empty-cells:show; border-collapse:collapse;}
"
      "td {
"
      "  width:50px; height:50px;
"
      "  border-style:solid; border-width:1px; border-color:#000000;
"
      "  text-align:center; vertical-align:middle;
"
      "  font-family:Arial, Verdana, Sans-serif; font-size:2em;
"
      "  }
"
      ".c0 {border-top-width:3px; border-left-width:3px;}
"
      ".c1 {border-top-width:3px;}
"
      ".c2 {border-top-width:3px; border-right-width:3px;}
"
      ".c3 {border-left-width:3px;}
"
      ".c4 {}
"
      ".c5 {border-right-width:3px;}
"
      ".c6 {border-bottom-width:3px; border-left-width:3px;}
"
      ".c7 {border-bottom-width:3px;}
"
      ".c8 {border-bottom-width:3px; border-right-width:3px;}
"
      ".c_ {border-top-width:0px; border-right-width:0px; "
              "border-bottom-width:0px; border-left-width:0px;}
"
      "</style>
</head>
<body>
<table>
"
      ;
  char *footer = "</table>
</body>
</html>";

  // Puzzle offsets (row/column) for each puzzle (puzzle 0 is in the middle):
  //                  0      1       2       3        4
  int offs[5][2] = {{6,6}, {0,0}, {12,12}, {0,12}, {12,0}};

  // Combined multi-string (+1 to be able to close each string with a '').
  char multi_s[SIZE][SIZE + 1];
  for (int k = 0; k < SIZE; k++) {
    for (int j = 0; j < SIZE; j++) {
      multi_s[k][j] = ' ';
      }
    multi_s[k][SIZE] = '';
    }

  // Copy the puzzles to the places they belong.
  // The boxes that overlap are set twice, first for puzzle 0 and then for
  // the other one. But it doesn't matter, as the two boxes are identical.
  // To set them only once, it would be sufficient to do the setting only
  // if (multi_s[baseR + kR][baseC + kC] == ' ')
  for (int kPuz = 0; kPuz < N_GRIDS; kPuz++) {
    int baseR = offs[kPuz][ROW];
    int baseC = offs[kPuz][COL];
    char *s = multi_string[kPuz][what];
    for (int i = 0; i < 81; i++) {
      int kR = i / 9;
      int kC = i - kR * 9;
      multi_s[baseR + kR][baseC + kC] = (s[i] == '0') ? '.' : s[i];
      }
    }
  for (int k = 0; k < SIZE; k++) printf("%s
", multi_s[k]);
  printf("
");

  // Finally, save the HTML to disk
  char f_name[64] = {0};
  sprintf(f_name, "%d_%d%c.html", seed, N_GRIDS, (what == SOL) ? 's' : 'p'),
  FILE *fp = fopen(f_name, "w");
  if (fp == NULL) {
    printf("Unable to open the file '%s' for writing
", f_name);
    }
  else {
    fprintf(fp, "%s%d%s", header_1, seed, header_2);
    for (int kRow = 0; kRow < SIZE; kRow++) {
      char *s = multi_s[kRow];
      fprintf(fp, "<tr>");
      for (int i = 0; i < SIZE; i++) {
        if (s[i] == ' ') {
          fprintf(fp, "<td class="c_"> </td>");
          }
        else {
          fprintf(fp, "<td class="c%d" style="background-color:%s">%c</td>",
              kRow % 3 * 3 + i % 3,
              (what == SOL  ||  (s[i] == '.') ? "White" : "LightGray"),
              ((s[i] == '.') ? ' ' : s[i])
              );
          }
        }
      fprintf(fp, "</tr>
");
      }
    fprintf(fp, "%s
", footer);
    fclose(fp);
    }
  }

The initial comment shows how the individual puzzles join to form a multi-grid Sudoku. Admittedly, as you already know multi-grid Sudokus from Figures 18-2 and 18-6, I could have omitted the comment. But, I confess, after having drawn the nice diagrams (before writing the code that generated the figures), I didn’t have the heart to throw them away, with the excuse that source code should be well commented!

The first interesting piece of code is

// Define the number of rows and columns needed for the multi-grid
#if N_GRIDS == 2
#define SIZE 15
#else
#define SIZE 21
#endif

If you look at Figures 18-2 and 18-6 or at the nice diagrams in the comment at the beginning of the module, you see that the double Sudoku is 15 cells wide and 15 cells high. All the other multi-grid Sudokus are 21 cells wide and 21 cells high. By making the definition of SIZE a C preprocessor directive linked to N_GRIDS, you can define the array to store the multi-grid of exactly the size you need.

As you learned at the end of Chapter 15, save_html() defines nine styles, named c0 to c8, whose function is to render the nine cells of a box in HTML with the appropriate borders. multi_html() uses the exact same styles, because they apply to each box separately, regardless of how many boxes exist in a puzzle.

But if you left it at that, a double Sudoku, just as an example, would look like that shown in Figure 18-9.

To remove the borders of empty cells, you only need to add the c_ style and use it for the cells that contain a space instead of a number.

To make the puzzles more interesting, you can add a background color to the cells of the puzzle that contain a clue, as shown in Figures 18-10 to 18-13.

Notice that all three instances of puzzle 0 in Figures 18-10 to 18-12 are identical, as are those of puzzle 1 and, for the two larger puzzles in Figures 18-11 and 18-12, those of puzzle 2.

This tells you that all three multi-grid puzzles have been generated with the same choice of FIRST_SEED, which is defined in sudoku_gen.c (set to 123456 to create the examples). It is something you have to keep in mind when you create a multi-grid puzzle. The grids are not different simply because their number changes.

Designer Multi-Grid Sudokus

In Chapter 17, you saw how to create puzzles in which the clues formed a predefined pattern. You can do the same with multi-grid Sudokus to great effect. But you have to be careful how you choose the patterns.

Listing 18-4 shows the third (and last) version of the Generator’s main program. As usual, I have highlighted the new parts.

Listing 18-4. sudoku_gen.c—The Final Version of main()

/* sudoku_gen.c
 *
 * Copyright (C) 2015  Giulio Zambon  - http://zambon.com.au/
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "brute_comp.h"
#include "count_solved.h"
#include "def.h"
#include "display.h"
#include "display_string.h"
#include "fill.h"
#include "inconsistent_grid.h"
#include "inconsistent_unit.h"
#include "init.h"
#include "in_box.h"
#include "list_solved.h"
#include "multi_html.h"
#include "save_html.h"

#define LOG_TO_FILE___NO
#define FILE_NAME "puzzles.txt"

#define SAVE_HTML_PUZZLE
#define SAVE_HTML_SOLUTION

#define DO_PATTERN

// N_GRIDS is defined in multi_html.h.
// When N_GRIDS is between 2 and 5, it triggers the creation of multi-grid
// puzzles. With any other value, the Generator creates a classic Sudoku.
#define DO_MULTI_GRID (N_GRIDS >= 2  &&  N_GRIDS <= 5)

// Parameters
#define N_SET_QUADS 5
#define N_SET_PAIRS 10
#define N_SET_CELLS 0
#define ADDITIONAL_CELLS TRUE
#define FIRST_SEED 12345
#define N_SEEDS 1

// Global variables
char *unit_names[3] = {"row", "column", "box"};
char grid[9][9];
char row[9][9][2];
char col[9][9][2];
char box[9][9][2];
char solved[9][9];
int silent = TRUE;

// Variables and functions local to this module
char puzzle[9][9];
int r_1[81];
int c_1[81];
int k_cell;
int remove_quads(int k_puz);
int remove_pairs(int k_puz);
void make_clue_list(void);
int remove_clues(int k_puz);
void remove_more_clues(int k_puz);
int check_uniqueness(void);

// The following table identifies the box of grid 0 that overlaps with other
// grids when creating multi-grid Sudokus.
// The first box refers to puzzle0 and second one to the other puzzle:
//
// N_GRIDS  kPuz=1  kPuz=2  kPuz=3  kPuz=4
//     2    b0-b8
//     3    b0-b8   b8-b0
//     4    b0-b8   b8-b0   b2-b6
//     5    b0-b8   b8-b0   b2-b6   b6-b2
//
// Puzzle:     0   1   2   3   4
int box0[] = {-1,  0,  8,  2,  6};

#ifdef DO_PATTERN
const char KEEP0[82] =
    "..1.1.1.."
    ".1..1..1."
    "1..1.1..1"
    "..1…1.."
    "11..1..11"
    "..1…1.."
    "1..1.1..1"
    ".1..1..1."
    "..1.1.1.."
    ;
const char KEEP1[82] =
    "..11111.."
    ".1.....1."
    "1..111..1"
    "1.1…1.1"
    "1.1.1.1.1"
    "1.1…1.1"
    "1..111..1"
    ".1.....1."
    "..11111.."
    ;
const char KEEP2[82] =
    "..11111.."
    ".1.....1."
    "1..111..1"
    "1.1…1.1"
    "1.1.1.1.1"
    "1.1…1.1"
    "1..111..1"
    ".1.....1."
    "..11111.."
    ;
const char KEEP3[] =
    "..11111.."
    ".1.....1."
    "1..111..1"
    "1.1…1.1"
    "1.1.1.1.1"
    "1.1…1.1"
    "1..111..1"
    ".1.....1."
    "..11111.."
    ;
const char KEEP4[] =
    "..11111.."
    ".1.....1."
    "1..111..1"
    "1.1…1.1"
    "1.1.1.1.1"
    "1.1…1.1"
    "1..111..1"
    ".1.....1."
    "..11111.."
    ;
const char *KEEPS[5] = { KEEP0, KEEP1, KEEP2, KEEP3, KEEP4 };
#endif

//======================================================================== main
int main(int argc, char *argv[]) {
  printf("*** sudoku_gen ***
");
  char mess[32];
  int n_seeds = N_SEEDS;
  int k_try = 0;

#if DO_MULTI_GRID
  // When creating multi-grid puzzles, set n_seed to the number of
  // puzzles that you need
  n_seeds = N_GRIDS;
#endif

  // Open a file to log the results
  FILE *fp = NULL;
#ifdef LOG_TO_FILE
  fp = fopen(FILE_NAME, "a");
  if (fp == NULL) {
    printf("Unable to open the file '%s' for reading
", FILE_NAME);
    return EXIT_FAILURE;                                                  //==>
    }
#endif

  // Try all the seeds in the given range
  unsigned long start_time = clock();

  for (int k_seed = 0; k_seed < n_seeds; k_seed++) {
    int seed = FIRST_SEED + k_seed;
    srand(seed);
    int brute_result;
    int n;

    // Keep repeating the generation until you find a unique solution
    char puzzle_string[82];
    char solution_string[82];
    do {

      // Generate a solved Sudoku
      do { init(); } while (fill());

      // Save the solved Sudoku
      for (int k = 0; k < 9; k++) {
        for (int j = 0; j < 9; j++) {
          solved[k][j] = grid[k][j];
          puzzle[k][j] = grid[k][j];
          }
        }

#if DO_MULTI_GRID
      if (k_seed > 0) {
        // You arrive here if you are creating a multi-grid puzzle and
        // have already created the first one (puzzle 0).
        int k0 = box0[k_seed]/3*3;
        int j0 = box0[k_seed]%3*3;
        int kk = overlapping_box[k_seed]/3*3;
        int jj = overlapping_box[k_seed]%3*3;

        // Build the look-up list of numbers to match puzzle 0 when creating
        // subsequent grids.
        char map[10] = {0};
        for (int k = 0; k < 3; k++) {
          for (int j = 0; j < 3; j++) {
            map[(int)grid[(kk + k)][jj + j]] =
                multi_string[0][SOL][(k0 + k)*9 + j0 + j] - '0'
                ;
            }
          }

        // Convert the numbers in the grid and save the modified grid
        for (int k = 0; k < 9; k++) {
          for (int j = 0; j < 9; j++) {
            grid[k][j] = map[(int)grid[k][j]];
            solved[k][j] = grid[k][j];
            puzzle[k][j] = grid[k][j];
            }
          }
#ifndef DO_PATTERN
        // Make the box that overlaps puzzle 0 identical to the
        // corresponding one of puzzle 0
        for (int k = 0; k < 3; k++) {
          for (int j = 0; j < 3; j++) {
            grid[(kk + k)][jj + j] =
                multi_string[0][PUZ][(k0 + k)*9 + j0 + j] - '0'
                ;
            }
          }
#endif
        }
#endif

#ifdef DO_PATTERN
      for (int i = 0; i < 81; i++) {
        if (KEEPS[k_seed][i] == '.') {
          int k = i / 9;
          int j = i - k * 9;
          grid[k][j] = 0;
          puzzle[k][j] = 0;
          }
        }
#else
      //========= Remove N_SET_QUADS quadruples of clues
      if (N_SET_QUADS > 0) {
        int success = remove_quads(k_seed);
        if (!success) {
          brute_result = BRUTE_COMP_DIFFERENT;
          goto skip;                                                      //==>
          }
        }

      //========= Remove N_SET_PAIRS pairs of clues
      if (N_SET_PAIRS > 0) {
        int success = remove_pairs(k_seed);
        if (!success) {
          brute_result = BRUTE_COMP_DIFFERENT;
          goto skip;                                                      //==>
          }
        }

      //========= Remove N_SET_CELLS individual clues and then some more
      make_clue_list();
      k_cell = 0;
      if (N_SET_CELLS > 0) {
        int success = remove_clues(k_seed);
        if (!success) {
          brute_result = BRUTE_COMP_DIFFERENT;
          goto skip;                                                      //==>
          }
        }
      if (ADDITIONAL_CELLS && k_cell < 81) remove_more_clues(k_seed);
#endif

      //========= Check whether the solution is really unique
      brute_result = check_uniqueness();

      //========= Done
      for (int k = 0; k < 9; k++) {
        for (int j = 0; j < 9; j++) {
          grid[k][j] = puzzle[k][j];
          }
        }
      n = count_solved();
      if (!silent && fp == NULL) {
        display();
        sprintf(mess, "seed %d %d", seed, n);
        display_string(mess);
        printf("The puzzle contains %d clues:", n);
        list_solved(stdout);
        }

skip:                                                                    // <==
      k_try++;
      printf("%d: %s
",
          k_try,
          (brute_result == BRUTE_COMP_DIFFERENT) ? "No" : "Yes"
          );
      } while (brute_result == BRUTE_COMP_DIFFERENT);

    // Save puzzle and solution into strings
    int kar = 0;
    for (int k = 0; k < 9; k++) {
      for (int j = 0; j < 9; j++) {
        puzzle_string[kar] = puzzle[k][j] + '0';
        solution_string[kar] = solved[k][j] + '0';
        kar++;
        }
      }
    puzzle_string[kar] = '';
    solution_string[kar] = '';

#if DO_MULTI_GRID
    // Save the puzzle and solution strings to be combined later into
    // a multi-grid Sudoku
    for (int i = 0; i < 82; i++) { // copy also the '' at the end
      multi_string[k_seed][PUZ][i] = puzzle_string[i];
      multi_string[k_seed][SOL][i] = solution_string[i];
      }
#endif

#ifdef SAVE_HTML_PUZZLE
    save_html(puzzle_string, seed, "p");
#endif

#ifdef SAVE_HTML_SOLUTION
    save_html(solution_string, seed, "s");
#endif
    if (fp != NULL) {
      printf("#%d
", k_seed);
      fprintf(fp, "%s	%d", puzzle_string, seed);
      if (brute_result != BRUTE_COMP_DIFFERENT) {
        fprintf(fp, "	%d", n);
        list_solved(fp);
        }
      fprintf(fp, "
");
      }
    } // for (k_seed..

#if DO_MULTI_GRID
  multi_html(FIRST_SEED, PUZ);
  multi_html(FIRST_SEED, SOL);
#endif

  unsigned long end_time = clock();
  printf("********* done in %ld microseconds
", end_time - start_time);
  if (fp != NULL) fclose(fp);
  return EXIT_SUCCESS;
  }

The first difference from the previous version of the Generator’s main() is the definition of DO_PATTERN. The first effect of defining DO_PATTERN is to switch on the definition of the KEEP* arrays. KEEP0 to KEEP4 determine the position of the clues in the five grids of a samurai Sudoku. But if you set N_GRIDS to 1 in multi_html.h, only puzzle 0 will be created and only KEEP0 will be used.

Once you define the clue patterns, all you need to do is use them to remove the clues. You do this with the following few lines of code:

for (int i = 0; i < 81; i++) {
  if (KEEPS[k_seed][i] == '.') {
    int k = i / 9;
    int j = i - k * 9;
    grid[k][j] = 0;
    puzzle[k][j] = 0;
    }
  }

Note that when you create designer multi-grid puzzles, you don’t need to do anything concerning the overlapping boxes because you have already matched them by defining the KEEP* arrays.

Many patterns of clues do not result in valid puzzles. Therefore, defining the matching patterns for up to five grids is at times a bit frustrating. But the results can be very rewarding, as the samurai shown in Figure 18-13 convincingly testifies.

Summary

This chapter taught you how to generate multi-grid Sudokus. It is the last chapter of the book and you now know everything I know concerning the generation of Sudoku puzzles. Appendix A will tell you how to set up the Eclipse development environment.

I hope you have enjoyed reading this book as I have enjoyed writing it. Happy puzzling!