Create your own Sudoku book

Pre

Solving Sudokus. It’s fun for most people. It keeps you busy while sitting on the john. Everybody has done it at least once in their life. But if you don’t have a smartphone/tablet/eBook reader you may have to do it in the old-fashioned way, resorting to a paper book and pencil. Those books sell for 5-15 $ on Amazon and contain nothing but numbers. One question that immediately jumps to my mind: how are generated? Is there a way to do that myself? I tried and today I am going to present you a method to create your very own and unique Sudoku puzzle book! The general workflow is as follows. As a first and most non-trivial step one generates the puzzles and their solutions and saves them into a .tex file. Second, we compile the .tex file with e.g. pdflatex, producing the book in portable document format. Third and last, you can print the pdf at home or submit it to an online printing service. This last step is the most expensive one and you will probably not save much money (or at all?) compared to just ordering a book. But the home-brew puzzle book has some advantages as well, least of it that the book will be your own creation.

Tools

Let’s give a list of the tools you need:

  •  A C++ compiler with support for the C++11 standard. I used g++ version 4.8.1 with the -std=c++11 and -O3 command line options. Profile guided optimization can also be used.
  • The source code below.
  • A latex distribution including pdflatex with the tikz/pgf packages installed.
  • A little time to compute.

Generating valid puzzles and C++ source

At the end of this section you will find the source code that I wrote to generate the Sudokus. It is commented and (hopefully) self-explanatory. For the sake of clarity, here is a top down description of what is done:

  • The number of puzzles to be generated is passed to the program by command line.
  • The program writes some \LaTeX document header to stdout.
  • Puzzles are generated in increasing difficulty, i.e. in descending number of initial (preoccupied) entries, ranging from 38 to 23. This concept of “difficulty” is not very rigorous (and in fact misleading) but it will do for now.
  • A single puzzle is created as follows:
    • The required initial entries are distributed randomly on the grid with random values between 1 and 9.
    • For every random number to be added one checks that the game is still valid, otherwise one chooses another random location and value. Once this is done the generated game is treated as a “candidate” for a valid Sudoku.
    • If there still are a couple of trivial values to be filled in, this is done right away.
    • If there are other simple-to-detect flaws in the game, it is discarded and one starts over.

Now the “candidate” needs to processed further. First one has to check that it has solution. Second one has to check that the solution is unique. Let’s address the first issue first. We use a backtracking algorithm to solve the game, which essentially tries out all values recursively on the empty cells until it finds a solution. For example, starting with a puzzle

3 9 6
7 1 5
1
7 3 6
9
8 2
4 1 8 7
6 8
9 2

The upper left corner is tentatively filled with a ‘1’ (the first a-priori-valid value) and then recursively tries to solve the game with the ‘1’ in the upper left corner. So on the next level one will try

1 3 9 2 6
7 1 5
1
7 3 6
9
8 2
4 1 8 7
6 8
9 2

Then

1 3 9 2 4 6
7 1 5
1
7 3 6
9
8 2
4 1 8 7
6 8
9 2

and after some more moves

1 3 9 2 4 6 8 7 9
2 4 6 7 1 5 X
1
7 3 6
9
8 2
4 1 8 7
6 8
9 2

If the try doesn’t work, as above (indicated by the X), one goes back to most recent level and tries the next allowed value. In this case the next in line is

1 3 9 2 4 6 8 7 9
2 4 8 7 1 5
1
7 3 6
9
8 2
4 1 8 7
6 8
9 2

etc. If the whole space of possibilities is exhausted and no solution is found, then there is no solution. I guess that statement was sort of trivial.
Let’s continue the formulation of the algorithm.

  • A single puzzle is created as follows (cont’d):
    • The candidate is solved by the backtracking algo. If no solution exists the puzzle candidate is discarded and one starts over again. If it has a solution, it’s uniqueness is checked by solving the candidate again with backtracking, but this time in “descending order” of trial values. In the above example the upper left corner is tried with an ‘8’. In doing so the space of possibilities is searched in reverse order. If both methods lead to the same solution, the solution is unique. The game is then accepted as a valid puzzle and enters book!
  • The accepted puzzles (and their solutions) are written to stdout in \LaTeX code. I use an example code by Roberto Bonvallet available at http://www.texample.net/tikz/examples/sudoku.
  • When all puzzles are created, we write the remaining \LaTeX  document-ending code to stdout.

So finally here is the code:

#include <iostream>
#include <sstream>
#include <random>
#include <ctime>
#include <cassert>

typedef char cell;
typedef cell game[9][9];

using namespace std;

/*low-level functions on game(s)*/
void  zeroGame(game); //sets all values to zero
void  copyGame(game, game); // Copies first arg to second arg
int getNextEmptyAddress(game); // returns next empty address as if the array was flattened out
int getValue(cell); //returns int value of a cell if it has a sane value. returns zero otherwise.
int fullCells(game); //returns number of full cells
bool gamesEqual(game, game); //tests if 2 games are equal.
bool isStoneCarvedValue(cell); //checks if a value is 'written down', i.e. fixed

/*high-level functions on game(s)*/
bool  isValidGame(game); //checks for correctness of the game
bool isSolvedGame(game); //checks if game is solved.
bool isObviouslyFlawed(game); //checks if game has obious traps. If not, trivial gaps are filled in.
bool isValidMove(game, int, int, cell);

/*brute-force solution of the game*/
int solveGame (game); //tries to  solve the game by brute-force in "ascending"  order. returns -1 if it fails and 0 if it succeeds.
int solveGame2(game); //tries to  solve the game by brute-force in "descending" order. returns -1 if it fails and 0 if it succeeds.

/*Generation of game(s) using Mersenne PRNG*/
void createRandomCandidate(game, uniform_int_distribution<int>* , mt19937*, int); //Creates random candidate
void generateValidSudokus(int, int, uniform_int_distribution<int>*, mt19937*); //22 or below is infeasible or 39 and above

/*LaTex printout*/
void  printHeaderLaTEx(); //self-explanatory
void printClosingLaTEx(); //self-explanatory
void printGameLaTEx(game); //self-explanatory
void printSolutionLaTEx(game, game); //self-explanatory

int main(int argc, char *argv[])
{
    /*parse total number of sudokus to generate*/
    assert(argc > 1);
    stringstream strstr;
    strstr << argv[1];
    int numSudokus;
    strstr >> numSudokus;
    if(numSudokus <= 0)
        return 1;
    constexpr int range = 38-22;

    cout<<"%generated by Gooby's Sudoku Generator"<<endl;
    printHeaderLaTEx();

    random_device rd; //not implemented in g++ 4.8x yet
    mt19937 mt(rd()); //Engine, seed
    uniform_int_distribution<int> random(1,9); //Distribution

    int currentDifficulty = 38;
    int numSudokusRemaining = numSudokus;
    int nextNumSudokus;

    float numSudokusPerSecond[range];
    int t1, t2;
    for (int i = 0; i < range; i++)
        numSudokusPerSecond[i] = 0;

    while(numSudokusRemaining > 0)
    {
        cout<<"%difficulty batch: "<<currentDifficulty<<endl;
        nextNumSudokus = (numSudokus/range == 0)? 1 : numSudokus/range;
        if(currentDifficulty == 23)
            nextNumSudokus = numSudokusRemaining;
        cout<<"%generating: "<<nextNumSudokus<<endl;
        t1 = time(0);
        generateValidSudokus(currentDifficulty,nextNumSudokus,&random,&mt);
        t2 = time(0);
        numSudokusPerSecond[currentDifficulty-23] = (float)nextNumSudokus/(t2-t1);
        numSudokusRemaining -= nextNumSudokus;
        currentDifficulty--;
    }

    printClosingLaTEx();
    cout<"%stats: ";
    for (int i = 0; i < range; i++)
        cout<<numSudokusPerSecond[i]<<' ';
    cout<<endl;

    return 0;
}

void generateValidSudokus(int difficulty, int number, uniform_int_distribution<int> *random, mt19937 *engine) //22 or below is infeasible or 39 and above
{
    game candidate, copy1_candidate, copy2_candidate;
    zeroGame(candidate);
    int solveCode;
    long long numTries = 0;
    int t1 = time(0);

    while(number > 0)
    {
        numTries++;
        createRandomCandidate(candidate, random, engine, difficulty);

        copyGame(candidate, copy1_candidate);
        if(isObviouslyFlawed(copy1_candidate)) //changes content of copy1_candidate by makeing trivial simplifications
            continue;

        copyGame(copy1_candidate, copy2_candidate);

        solveCode = solveGame(copy1_candidate); //tryin 2 solv teh pozzl...
        if(solveCode == -1)
            continue; //no solution! skip!

        solveGame2(copy2_candidate); //tryin 2 solv teh pozzl agen, but searching teh solution space in reverse order...

        if(gamesEqual(copy1_candidate, copy2_candidate))
        {
            cout<<"%Generated after "<<numTries<<" tries in "<<(time(0)-t1)<<"s"<<endl;
            printGameLaTEx(candidate); //game
            printSolutionLaTEx(candidate,copy1_candidate); //Solution
            number--;
            t1 = time(0);
        } //if solutions are not equal, there is no unique solution and we continue rolling the dice
    }
}

inline bool isValidMove(game g, int x, int y, cell v)
{
    for(int k = 0; k < x; k++) //checks the column part 1
        if(isStoneCarvedValue(g[k][y]))
            if(g[k][y] == v)
                return false;
    for(int k = x+1; k < 9; k++) //checks the column part 2
        if(isStoneCarvedValue(g[k][y]))
            if(g[k][y] == v)
                return false;
    for(int k = 0; k < y; k++) //checks the line 1
        if(isStoneCarvedValue(g[x][k]))
            if(g[x][k] == v)
                return false;
    for(int k = y+1; k < 9; k++) //checks the line 2
        if(isStoneCarvedValue(g[x][k]))
            if(g[x][k] == v)
                return false;
    int sq = 3*(x/3) + y/3;
    int sqx, sqy;
    for(int a = 0; a < 3; a++)
        for(int b = 0; b < 3; b++)
        {
            sqx = 3*(sq/3) + a;
            sqy = (3*sq)%9 + b;
            if(isStoneCarvedValue(g[sqx][sqy]) && (sqx != x) && (sqy != y) )
                if(g[sqx][sqy] == v)
                    return false;
        }
    return true;
}

bool isObviouslyFlawed(game g)
{
    bool possbilities[9][9][9];
    for(int i = 0; i < 9; i++) //set everything to 'possible'
        for(int j = 0; j < 9; j++)
            for(int k = 0; k < 9; k++)
                possbilities[i][j][k] = true;
    for(int i = 0; i < 9; i++) //set vixed values to an exclusive 'possible'
        for(int j = 0; j < 9; j++)
            if(isStoneCarvedValue(g[i][j]))
            {
                for(int k = 0; k < 9; k++)
                     possbilities[i][j][k] = false;
                possbilities[i][j][getValue(g[i][j])-1] = true;
            }

    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
            if(!isStoneCarvedValue(g[i][j]))
            {
                for(int k = 0; k < i; k++) //remove possiblilties from the column due to a fixed value
                    if(isStoneCarvedValue(g[k][j]))
                        possbilities[i][j][getValue(g[k][j])-1] = false;

                for(int k = i + 1; k < 9; k++) //remove possiblilties from the column due to a fixed value (part 2)
                    if(isStoneCarvedValue(g[k][j]))
                        possbilities[i][j][getValue(g[k][j])-1] = false;

                for(int k = 0; k < j; k++) //remove possiblilties from the line due to a fixed value
                    if(isStoneCarvedValue(g[i][k]))
                        possbilities[i][j][getValue(g[i][k])-1] = false;

                for(int k = j + 1; k < 9; k++) //remove possiblilties from the line due to a fixed value (part 2)
                    if(isStoneCarvedValue(g[i][k]))
                        possbilities[i][j][getValue(g[i][k])-1] = false;
                //find out which square to process
                int sq = 3*(i/3) + j/3;
                int sqx, sqy;
                for(int a = 0; a < 3; a++) //remove possiblilties from the 3x3 due to a fixed value
                    for(int b = 0; b < 3; b++)
                    {
                        sqx = 3*(sq/3) + a;
                        sqy = (3*sq)%9 + b;
                        if(isStoneCarvedValue(g[sqx][sqy]))
                            possbilities[i][j][getValue(g[sqx][sqy])-1] = false;
                    }
            }

    bool madeChanges = false;

    /*check that each line either has a value or can take it*/
    bool hasValue;
    bool canTakeValue;
    int numbeerOfRecipients;
    int positionOfRecipient = -1, positionOfRecipient2 = -1;
    for(int i = 0; i < 9; i++) //Check: can each line hold every value?
    {
        for(cell c = '1'; c <= '9'; c++)
        {
            hasValue = ( (g[i][0] == c) || (g[i][1] == c) || (g[i][2] == c) || (g[i][3] == c) || (g[i][4] == c) || (g[i][5] == c) || (g[i][6] == c) || (g[i][7] == c) || (g[i][8] == c) );

            numbeerOfRecipients = 0;
            canTakeValue = false;
            for(int j = 0; j < 9; j++)
                if(possbilities[i][j][getValue(c)-1])
                {
                    canTakeValue = true;
                    numbeerOfRecipients++;
                    positionOfRecipient = j;
                }

            if( !(hasValue || canTakeValue) )
                return true;

            if( (!hasValue) && (numbeerOfRecipients == 1) )
            {
                g[i][positionOfRecipient] = c;
                madeChanges = true;
            }
        }
    }

    /*check that each column either has a value or can take it*/
    for(int j = 0; j < 9; j++) //Check: can each column hold every value?
    {
        for(cell c = '1'; c <= '9'; c++)
        {
            hasValue = ( (g[0][j] == c) || (g[1][j] == c) || (g[2][j] == c) || (g[3][j] == c) || (g[4][j] == c) || (g[5][j] == c) || (g[6][j] == c) || (g[7][j] == c) || (g[8][j] == c) );

            numbeerOfRecipients = 0;
            canTakeValue = false;
            for(int i = 0; i < 9; i++)
                if(possbilities[i][j][getValue(c)-1])
                {
                    canTakeValue = true;
                    numbeerOfRecipients++;
                    positionOfRecipient = i;
                }

            if( !(hasValue || canTakeValue) )
                return true;
            if( (!hasValue) && (numbeerOfRecipients == 1) )
            {
                g[positionOfRecipient][j] = c;
                madeChanges = true;
            }
        }
    }

    /*check that each 3x3 either has a value or can take it*/
    for(int sq = 0; sq < 9; sq++) //Check: can each 3x3 hold every value?
    {
        for(cell c = '1'; c <= '9'; c++)
        {
            hasValue = false;
            canTakeValue = false;
            numbeerOfRecipients = 0;
            //upper-left corner has address <3*(sq%3), (3*sq)%9>
            for(int a = 0; a < 3; a++)
                for(int b = 0; b < 3; b++)
                {
                    if(g[3*(sq/3) + a][(3*sq)%9 + b] == c)
                        hasValue = true;
                    if(possbilities[3*(sq/3) + a][(3*sq)%9 + b][getValue(c)-1])
                    {
                        canTakeValue = true;
                        numbeerOfRecipients++;
                        positionOfRecipient = 3*(sq/3) + a;
                        positionOfRecipient2 = (3*sq)%9 + b;
                    }
                }
            if( !(hasValue || canTakeValue) )
                return true;
            if( (!hasValue) && (numbeerOfRecipients == 1) )
            {
                g[positionOfRecipient][positionOfRecipient2] = c;
                madeChanges = true;
            }
        }
    }

    //solve naked singles
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            int numPossibilities = 0;
            int position = 0;
            for (int k = 0; k < 9; k++)
                if (possbilities[i][j][k])
                {
                    numPossibilities++;
                    position = k;
                }
            if( (numPossibilities == 1) && (!isStoneCarvedValue(g[i][j])) )
            {
                g[i][j] = '1' + position;
                madeChanges = true;
            }
            if(numPossibilities <= 0)
                return true;
        }
    }
    if(!madeChanges)
        return false;
    else
        return isObviouslyFlawed(g);
}

void createRandomCandidate(game g, uniform_int_distribution<int> *random, mt19937 *engine, int numbersToBeFilled)
{
    int numbersToBeAdded = numbersToBeFilled - fullCells(g);

    if(numbersToBeAdded <= 0)
    {
        zeroGame(g);
        numbersToBeAdded = numbersToBeFilled;
    }

    int rand_i;
    int rand_j;
    cell rand_cell, old_cell;
    while(numbersToBeAdded > 0)
    {
        rand_i = (random->operator())(*engine)-1;
        rand_j = (random->operator())(*engine)-1;
        rand_cell = '0'+(random->operator())(*engine);

        old_cell = g[rand_i][rand_j];

        if (isStoneCarvedValue(g[rand_i][rand_j]))
            continue;

        g[rand_i][rand_j] = rand_cell;

        if(isValidGame(g))
            numbersToBeAdded--;
        else
             g[rand_i][rand_j] = old_cell;
    }
}

bool gamesEqual(game g1, game g2)
{
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (g1[i][j] != g2[i][j])
                return false;
    return true;
}

void zeroGame(game g)
{
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            g[i][j] = '0';
}

int fullCells(game g)
{
    int numSaneValues = 0;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if(isStoneCarvedValue(g[i][j]))
                numSaneValues++;
    return numSaneValues;
}

void copyGame(game src, game dest)
{
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            dest[i][j] = src[i][j];
}

int getNextEmptyAddress(game g)
{
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if(!isStoneCarvedValue(g[i][j]))
                return i*9 + j;
    return -1;
}

inline bool isStoneCarvedValue(cell v)
{
    return ( (v >='1') && (v <='9') );
}

inline int getValue(cell v)
{
    if(isStoneCarvedValue(v))
        return v-'0';
    else
        return 0;
}

inline bool isValidGame(game g)
{
    int freqs[10];

    //check lines and columns
    for (int i = 0; i < 9; i++)
    {
        freqs[1] = freqs[2] = freqs[3] = freqs[4] = freqs[5] = freqs[6] = freqs[7] = freqs[8] = freqs[9] = 0;
        freqs[getValue(g[i][0])]++;
        freqs[getValue(g[i][1])]++;
        freqs[getValue(g[i][2])]++;
        freqs[getValue(g[i][3])]++;
        freqs[getValue(g[i][4])]++;
        freqs[getValue(g[i][5])]++;
        freqs[getValue(g[i][6])]++;
        freqs[getValue(g[i][7])]++;
        freqs[getValue(g[i][8])]++;
        if( (freqs[1]>1) || (freqs[2]>1) || (freqs[3]>1) || (freqs[4]>1) || (freqs[5]>1) || (freqs[6]>1) || (freqs[7]>1) || (freqs[8]>1) || (freqs[9]>1) )
            return false;

        freqs[1] = freqs[2] = freqs[3] = freqs[4] = freqs[5] = freqs[6] = freqs[7] = freqs[8] = freqs[9] = 0;
        freqs[getValue(g[0][i])]++;
        freqs[getValue(g[1][i])]++;
        freqs[getValue(g[2][i])]++;
        freqs[getValue(g[3][i])]++;
        freqs[getValue(g[4][i])]++;
        freqs[getValue(g[5][i])]++;
        freqs[getValue(g[6][i])]++;
        freqs[getValue(g[7][i])]++;
        freqs[getValue(g[8][i])]++;

        if( (freqs[1]>1) || (freqs[2]>1) || (freqs[3]>1) || (freqs[4]>1) || (freqs[5]>1) || (freqs[6]>1) || (freqs[7]>1) || (freqs[8]>1) || (freqs[9]>1) )
            return false;
    }

    //check 3x3 squares
    int ul_i, ul_j;
    for(int sq = 0; sq < 9; sq++)
    {
        freqs[1] = freqs[2] = freqs[3] = freqs[4] = freqs[5] = freqs[6] = freqs[7] = freqs[8] = freqs[9] = 0;
        //upper-left corner has address <3*(sq%3), (3*sq)%9>
        ul_i = 3*(sq/3);
        ul_j = (3*sq)%9;
        freqs[getValue(g[ul_i][ul_j])]++;
        freqs[getValue(g[ul_i][ul_j+1])]++;
        freqs[getValue(g[ul_i][ul_j+2])]++;
        freqs[getValue(g[ul_i+1][ul_j])]++;
        freqs[getValue(g[ul_i+1][ul_j+1])]++;
        freqs[getValue(g[ul_i+1][ul_j+2])]++;
        freqs[getValue(g[ul_i+2][ul_j])]++;
        freqs[getValue(g[ul_i+2][ul_j+1])]++;
        freqs[getValue(g[ul_i+2][ul_j+2])]++;

        if( (freqs[1]>1) || (freqs[2]>1) || (freqs[3]>1) || (freqs[4]>1) || (freqs[5]>1) || (freqs[6]>1) || (freqs[7]>1) || (freqs[8]>1) || (freqs[9]>1) )
            return false;
    }

    return true;
}

bool isSolvedGame(game g)
{
    int numSaneValues = 0;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if(isStoneCarvedValue(g[i][j]))
                numSaneValues++;
    return ( (numSaneValues==81) && isValidGame(g) );
}

int solveGame(game g)
{
    int nextEmptyAddress = getNextEmptyAddress(g);

    if(nextEmptyAddress == -1)
        return (isSolvedGame(g)? 0 : -1);

    int nexti = nextEmptyAddress/9, nextj = nextEmptyAddress%9;
    int nextSolveResult;
    for (char newTry = '1'; newTry <= '9'; newTry++)
    {
        g[nexti][nextj] = newTry;
        if(!isValidMove(g,nexti,nextj,newTry))
            continue; //Skip obviously stupid tries
        nextSolveResult = solveGame(g);
        if(nextSolveResult == 0)
            return 0;
    }
    g[nexti][nextj] = '0';
    return -1;
}

int solveGame2(game g)
{
    int nextEmptyAddress = getNextEmptyAddress(g);

    if(nextEmptyAddress == -1)
        return (isSolvedGame(g)? 0 : -1);

    int nexti = nextEmptyAddress/9, nextj = nextEmptyAddress%9;
    int nextSolveResult;
    for (char newTry = '9'; newTry >= '1'; newTry--)
    {
        g[nexti][nextj] = newTry;
        if(!isValidMove(g,nexti,nextj,newTry))
            continue; //Skip obviously stupid tries
        nextSolveResult = solveGame2(g);
        if(nextSolveResult == 0)
            return 0;
    }
    g[nexti][nextj] = '0';
    return -1;
}

void printGameLaTEx(game g)
{
    //http://www.texample.net/tikz/examples/sudoku/
    cout<<"\\begin{center}"<<endl;
    cout<<"\\begin{tikzpicture}"<<endl;
    cout<<"\\draw (0, 0) grid (9, 9);"<<endl;
    cout<<"\\draw[very thick, scale=3] (0, 0) grid (3, 3);"<<endl;
    cout<<"\\setcounter{row}{1}"<<endl;
    for(int i = 0; i < 9; i++)
    {
        cout<<"\\setrow"<<endl;
        for(int j = 0; j < 9; j++)
            cout<<'{'<<( ( (g[i][j] <='9') && (g[i][j] >='1') ) ? g[i][j] : ' ')<<'}';
        cout<<endl;
    }
    cout<<"\\end{tikzpicture}"<<endl;
    cout<<"\\end{center}"<<endl;
    cout<<"\\newpage"<<endl;
}

void printSolutionLaTEx(game g, game s)
{
    //code used from http://www.texample.net/tikz/examples/sudoku/
    cout<<"\\begin{center}"<<endl;
    cout<<"\\begin{tikzpicture}"<<endl;
    cout<<"\\draw (0, 0) grid (9, 9);"<<endl;
    cout<<"\\draw[very thick, scale=3] (0, 0) grid (3, 3);"<<endl;
    cout<<"\\setcounter{row}{1}"<<endl;
    for(int i = 0; i < 9; i++)
    {
        cout<<"\\setrow"<<endl;
        for(int j = 0; j < 9; j++)
            cout<<'{'<<( ( (g[i][j] <='9') && (g[i][j] >='1') ) ? g[i][j] : ' ')<<'}';
        cout<<endl;
    }
    cout<<"\\begin{scope}[blue, font=\\sffamily\\slshape]"<<endl;
    cout<<"\\setcounter{row}{1}"<<endl;
    for(int i = 0; i < 9; i++)
    {
        cout<<"\\setrow"<<endl;
        for(int j = 0; j < 9; j++)
            cout<<'{'<<( ( (g[i][j] <='9') && (g[i][j] >='1') ) ? ' ' : s[i][j])<<'}';
        cout<<endl;
    }
    cout<<"\\end{scope}"<<endl;
    cout<<"\\end{tikzpicture}"<<endl;
    cout<<"\\end{center}"<<endl;
    cout<<"\\newpage"<<endl<<endl;

}

void printHeaderLaTEx()
{
    //code used from http://www.texample.net/tikz/examples/sudoku/
    cout<<"\\documentclass{article}\n\\usepackage{tikz}\n\\usepackage{mathpazo}"<<endl;
    cout<<"\\newcounter{row}\n\\newcounter{col}"<<endl<<endl;
    cout<<"\\newcommand\\setrow[9]{\n\\setcounter{col}{1}\n\\foreach \\n in {#1, #2, #3, #4, #5, #6, #7, #8, #9} {\n\\edef\\x{\\value{col} - 0.5}\n\\edef\\y{9.5 - \\value{row}}\n\\node[anchor=center] at (\\x, \\y) {\\LARGE\\n};\n\\stepcounter{col}\n}\n\\stepcounter{row}\n}"<<endl;
    cout<<"\\begin{document}"<<endl<<endl;
}

void printClosingLaTEx()
{
    //code used from http://www.texample.net/tikz/examples/sudoku/
    cout<<"\\end{document}"<<endl;
}

Producing the book

In fact, the steps are simple:

  • Save the source to GoobysSudokus.cpp
  • Compile with
    $ g++ -O3 -std=c++11 -o GoobysSudokus GoobysSudokus.cpp
    

    Note that I used the C++11 standard for the pseuo random number generation. In principle this can be relaxed and you can replace the PRNG by one you prefer.

  • Run the program with e.g.
    $ ./GoobysSudokus 500 > sudokubook.tex
    

    where the stdout output is redirected into a \LaTeX source file. This step can take some time. For 500 puzzles it took me about 20 minutes (see also the discussion below).

  • Compile the book with
    $ pdflatex sudokubook.tex
    

    This step took me another 10 minutes. It’s a 1000 page document after all.

The resulting file sudokubook.pdf is final product! Is is unique (most likely 😉 he he)! And has solutions! It will look something like

sudoku_examplepage

These final words

C++11 is not strictly necessary, I just wanted to try out the extended capabilities of the STL in terms of pseudo-random numbers. Also, readers of my blog know that I don’t have the heart to use rand().

Considering performance, the method I suggested has two kind-of-obvious bottlenecks. First, generation of “easy” puzzles, i.e. those with many numbers already filled in, is very costly. The reason is that it becomes more and more unlikely to produce a valid Sudoku from randomness with too many constraints. I found that for the number of prefilled entries 39 is an enormous threshold, where the rate of generating valid puzzles drops almost to zero. 38 is still OK, but considerably slow. One achieves the best performance for 28. One can go below that until 23. 22 is already infeasible. At this “end” (few initial values) the backtracking becomes pretty expensive and the likelihood that some random configuration has more than one solution is not in our favor.

Just for fun I tried to produce a Sudoku with 17 starting values, but I failed for the reason mentioned above. And I lost patience after one-and-a-half hours of pointless calculation. You shouldn’t try 16, because there is compelling evidence that this is bound to fail anyway.

Personally I am not an expert in Sudoku-generation, but there may be more efficient ways. One suggestion is to take an already generated one and apply to it a number of “symmetry” transformations, i.e. tansformations that are known to preserve solvability and uniqeness. I don’t like this approach, because it’s like cheating. It doesn’t increase complexity, it just produces equivalent representations of a specific class of a puzzle. In the program presented here this unlikely to happen, one might even argue that we are creating “high-entropy” Sudokus here which by construction provide a better user experience ;).

The styling of the final “book” is very spartan. You may add a decent titlepage easily. I leave it to my readers to improve the code with a couple of tweaks like “more puzzles on one page” or “solutions belong in the appendix”.

I suspect that further variants of Sudoku, like Sudoku X, Killer Sudoku etc. should also be producable by a program similar to the one above. Of course there are a lot of implementation details and I don’t have the time right now to address the relevant generalizations. But maybe someone else wants to do it!? Let’s call it a day.

Advertisements

About goobypl5

pizza baker, autodidact, particle physicist
This entry was posted in Programming and tagged , , , , , , . Bookmark the permalink.

Share your thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s