HTML of qqwing

/*
 * qqwing - A Sudoku solver and generator
 * Copyright (C) 2006 Stephen Ostermiller
 * http://ostermiller.org/qqwing/
 * Copyright (C) 2007 Jacques Bensimon (jacques@ipm.com)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include "config.h"
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
#if HAVE_GETTIMEOFDAY == 1
    #include <sys/time.h>
#else
    #include <time.h>
#endif

using namespace std;
class SuddokuBoard;
class LogItem;

/**
 * The board containing all the memory structures and
 * methods for solving or generating sudoku puzzles.
 */
class SudokuBoard {
    public:
        enum PrintStyle {
            ONE_LINE,
            COMPACT,
            READABLE,
            CSV,
        };
        enum Difficulty {
            UNKNOWN,
            SIMPLE,
            EASY,
            INTERMEDIATE,
            EXPERT,
        };
        SudokuBoard();
        bool setPuzzle(int* initPuzzle);
        void printPuzzle();
        void printSolution();
        bool solve();
        int countSolutions();
        void printPossibilities();
        bool isSolved();
        void printSolveHistory();
        void setRecordHistory(bool recHistory);
        void setLogHistory(bool logHist);
        void setPrintStyle(PrintStyle ps);
        bool generatePuzzle();
        int getGivenCount();
        int getSingleCount();
        int getHiddenSingleCount();
        int getNakedPairCount();
        int getHiddenPairCount();
        int getBoxLineReductionCount();
        int getPointingPairTripleCount();
        int getGuessCount();
        int getBacktrackCount();
        void printSolveInstructions();
        SudokuBoard::Difficulty getDifficulty();
        char* getDifficultyAsString();
        ~SudokuBoard();

    private:
        /**
         * The 81 integers that make up a sudoku puzzle.
         * Givens are 1-9, unknows are 0.
         * Once initialized, this puzzle remains as is.
         * The answer is worked out in "solution".
         */
        int* puzzle;

        /**
         * The 81 integers that make up a sudoku puzzle.
         * The solution is built here, after completion
         * all will be 1-9.
         */
        int* solution;

        /**
         * Recursion depth at which each of the numbers
         * in the solution were placed.  Useful for backing
         * out solve branches that don't lead to a solution.
         */
        int* solutionRound;

        /**
         * The 729 integers that make up a the possible
         * values for a suduko puzzle. (9 possibilities
         * for each of 81 squares).  If possibilities[i]
         * is zero, then the possibility could still be
         * filled in according to the sudoku rules.  When
         * a possibility is eliminated, possibilities[i]
         * is assigned the round (recursion level) at
         * which it was determined that it could not be
         * a possibility.
         */
        int* possibilities;

        /**
         * An array the size of the board (81) containing each
         * of the numbers 0-n exactly once.  This array may
         * be shuffled so that operations that need to
         * look at each cell can do so in a random order.
         */
        int* randomBoardArray;

        /**
         * An array with one element for each position (9), in
         * some random order to be used when trying each
         * position in turn during guesses.
         */
        int* randomPossibilityArray;

        /**
         * Whether or not to record history
         */
        bool recordHistory;

        /**
         * Whether or not to print history as it happens
         */
        bool logHistory;

        /**
         * A list of moves used to solve the puzzle.
         * This list contains all moves, even on solve
         * branches that did not lead to a solution.
         */
        vector<LogItem*>* solveHistory;

        /**
         * A list of moves used to solve the puzzle.
         * This list contains only the moves needed
         * to solve the puzzle, but doesn't contain
         * information about bad guesses.
         */
        vector<LogItem*>* solveInstructions;

        /**
         * The style with which to print puzzles and solutions
         */
        PrintStyle printStyle;

        /**
         * The last round of solving
         */
        int lastSolveRound;
        bool reset();
        bool singleSolveMove(int round);
        bool onlyPossibilityForCell(int round);
        bool onlyValueInRow(int round);
        bool onlyValueInColumn(int round);
        bool onlyValueInSection(int round);
        bool solve(int round);
        int countSolutions(int round, bool limitToTwo);
        bool guess(int round, int guessNumber);
        bool isImpossible();
        void rollbackRound(int round);
        bool pointingRowReduction(int round);
        bool rowBoxReduction(int round);
        bool colBoxReduction(int round);
        bool pointingColumnReduction(int round);
        bool hiddenPairInRow(int round);
        bool hiddenPairInColumn(int round);
        bool hiddenPairInSection(int round);
        void mark(int position, int round, int value);
        int findPositionWithFewestPossibilities();
        bool handleNakedPairs(int round);
        int countPossibilities(int position);
        bool arePossibilitiesSame(int position1, int position2);
        void addHistoryItem(LogItem* l);
        void markRandomPossibility(int round);
        void shuffleRandomArrays();
        void print(int* sudoku);
        void rollbackNonGuesses();
        void clearPuzzle();
        void printHistory(vector<LogItem*>* v);
        bool removePossibilitiesInOneFromTwo(int position1, int position2, int round);

};

/**
 * While solving the puzzle, log steps taken in a log item.
 * This is useful for later printing out the solve history
 * or gathering statistics about how hard the puzzle was to
 * solve.
 */
class LogItem {
    public:
        enum LogType {
            GIVEN,
            SINGLE,
            HIDDEN_SINGLE_ROW,
            HIDDEN_SINGLE_COLUMN,
            HIDDEN_SINGLE_SECTION,
            GUESS,
            ROLLBACK,
            NAKED_PAIR_ROW,
            NAKED_PAIR_COLUMN,
            NAKED_PAIR_SECTION,
            POINTING_PAIR_TRIPLE_ROW,
            POINTING_PAIR_TRIPLE_COLUMN,
            ROW_BOX,
            COLUMN_BOX,
            HIDDEN_PAIR_ROW,
            HIDDEN_PAIR_COLUMN,
            HIDDEN_PAIR_SECTION,
        };
        LogItem(int round, LogType type);
        LogItem(int round, LogType type, int value, int position);
        int getRound();
        void print();
        LogType getType();
        ~LogItem();
    private:
        void init(int round, LogType type, int value, int position);
        /**
         * The recursion level at which this item was gathered.
         * Used for backing out log items solve branches that
         * don't lead to a solution.
         */
        int round;

        /**
         * The type of log message that will determine the
         * message printed.
         */
        LogType type;

        /**
         * Value that was set by the operation (or zero for no value)
         */
        int value;

        /**
         * position on the board at which the value (if any) was set.
         */
        int position;
};

string IntToString(int num);
long getMicroseconds();
void shuffleArray(int* array, int size);
bool readPuzzleFromStdIn(int* puzzle);
int main(int argc, char *argv[]);
void printHelp(char* programName);
void printVersion();
void printAbout();
int getLogCount(vector<LogItem*>* v, LogItem::LogType type);
static inline int cellToColumn(int cell);
static inline int cellToRow(int cell);
static inline int cellToSectionStartCell(int cell);
static inline int cellToSection(int cell);
static inline int rowToFirstCell(int row);
static inline int columnToFirstCell(int column);
static inline int sectionToFirstCell(int section);
static inline int getPossibilityIndex(int valueIndex, int cell);
static inline int rowColumnToCell(int row, int column);
static inline int sectionToCell(int section, int offset);

#define GRID_SIZE 3
#define ROW_LENGTH          (GRID_SIZE*GRID_SIZE)
#define COL_HEIGHT          (GRID_SIZE*GRID_SIZE)
#define SEC_SIZE            (GRID_SIZE*GRID_SIZE)
#define SEC_COUNT           (GRID_SIZE*GRID_SIZE)
#define SEC_GROUP_SIZE      (SEC_SIZE*GRID_SIZE)
#define NUM_POSS            (GRID_SIZE*GRID_SIZE)
#define BOARD_SIZE          (ROW_LENGTH*COL_HEIGHT)
#define POSSIBILITY_SIZE    (BOARD_SIZE*NUM_POSS)

/**
 * Main method -- the entry point into the program.
 * Run with --help as an argument for usage and documentation
 */
int main(int argc, char *argv[]){
    try {
        // Start time for the application for timing
        long applicationStartTime = getMicroseconds();

        // The number of puzzles solved or generated.
        int puzzleCount = 0;

        enum Action {NONE, GENERATE, SOLVE};

        // defaults for options
        bool printPuzzle = false;
        bool printSolution = false;
        bool printHistory = false;
        bool printInstructions = false;
        bool timer = false;
        bool countSolutions = false;
        Action action = NONE;
        bool logHistory = false;
        SudokuBoard::PrintStyle printStyle = SudokuBoard::READABLE;
        int numberToGenerate = 1;
        bool printStats = false;
        SudokuBoard::Difficulty difficulty = SudokuBoard::UNKNOWN;

        // Read the arguments and set the options
        {for (int i=1; i<argc; i++){
            if (!strcmp(argv[i],"--puzzle")){
                printPuzzle = true;
            } else if (!strcmp(argv[i],"--nopuzzle")){
                printPuzzle = false;
            } else if (!strcmp(argv[i],"--solution")){
                printSolution = true;
            } else if (!strcmp(argv[i],"--nosolution")){
                printSolution = false;
            } else if (!strcmp(argv[i],"--history")){
                printHistory = true;
            } else if (!strcmp(argv[i],"--nohistory")){
                printHistory = false;
            } else if (!strcmp(argv[i],"--instructions")){
                printInstructions = true;
            } else if (!strcmp(argv[i],"--noinstructions")){
                printInstructions = false;
            } else if (!strcmp(argv[i],"--stats")){
                printStats = true;
            } else if (!strcmp(argv[i],"--nostats")){
                printStats = false;
            #if HAVE_GETTIMEOFDAY == 1
                } else if (!strcmp(argv[i],"--timer")){
                    timer = true;
                } else if (!strcmp(argv[i],"--notimer")){
                    timer = false;
            #endif
            } else if (!strcmp(argv[i],"--count-solutions")){
                countSolutions = true;
            } else if (!strcmp(argv[i],"--nocount-solutions")){
                countSolutions = false;
            } else if (!strcmp(argv[i],"--generate")){
                action = GENERATE;
                printPuzzle = true;
                if (i+1 < argc && argv[i+1][0] >= '1' && argv[i+1][0] <= '9'){
                    numberToGenerate = atoi(argv[i+1]);
                    i++;
                }
            } else if (!strcmp(argv[i],"--difficulty")){
                if (argc < i+1){
                    cout << "Please specify a difficulty." << endl;
                    return 1;
                } else if (!strcmp(argv[i+1],"simple")){
                    difficulty = SudokuBoard::SIMPLE;
                } else if (!strcmp(argv[i+1],"easy")){
                    difficulty = SudokuBoard::EASY;
                } else if (!strcmp(argv[i+1],"intermediate")){
                    difficulty = SudokuBoard::INTERMEDIATE;
                } else if (!strcmp(argv[i+1],"expert")){
                    difficulty = SudokuBoard::EXPERT;
                } else {
                    cout << "Difficulty expected to be simple, easy, intermediate, or expert, not " << argv[i+1] << endl;
                    return 1;
                }
                i++;
            } else if (!strcmp(argv[i],"--solve")){
                action = SOLVE;
                printSolution = true;
            } else if (!strcmp(argv[i],"--log-history")){
                logHistory = true;
            } else if (!strcmp(argv[i],"--nolog-history")){
                logHistory = false;
            } else if (!strcmp(argv[i],"--one-line")){
                printStyle=SudokuBoard::ONE_LINE;
            } else if (!strcmp(argv[i],"--compact")){
                printStyle=SudokuBoard::COMPACT;
            } else if (!strcmp(argv[i],"--readable")){
                printStyle=SudokuBoard::READABLE;
            } else if (!strcmp(argv[i],"--csv")){
                printStyle=SudokuBoard::CSV;
            } else if (!strcmp(argv[i],"-n") || !strcmp(argv[i],"--number")){
                if (i+1 < argc){
                    numberToGenerate = atoi(argv[i+1]);
                    i++;
                } else {
                    cout << "Please specify a number." << endl;
                    return 1;
                }
            } else if (!strcmp(argv[i],"-h") || !strcmp(argv[i],"--help") || !strcmp(argv[i],"help") || !strcmp(argv[i],"?")){
                printHelp(argv[0]);
                return 0;
            } else if (!strcmp(argv[i],"--version")){
                printVersion();
                return 0;
            } else if (!strcmp(argv[i],"--about")){
                printAbout();
                return 0;
            } else {
                cout << "Unknown argument: '" << argv[i] << "'" << endl;
                printHelp(argv[0]);
                return 1;
            }
        }}

        if (action == NONE){
            cout << "Either --solve or --generate must be specified." << endl;
            printHelp(argv[0]);
            return 1;
        }

        // Initialize the random number generator
        int timeSeed = time(NULL);
        srand(timeSeed);

        // If printing out CSV, print a header
        if (printStyle == SudokuBoard::CSV){
            if (printPuzzle) cout << "Puzzle,";
            if (printSolution) cout << "Solution,";
            if (printHistory) cout << "Solve History,";
            if (printInstructions) cout << "Solve Instructions,";
            if (countSolutions) cout << "Solution Count,";
            if (timer) cout << "Time (milliseconds),";
            if (printStats) cout << "Givens,Singles,Hidden Singles,Naked Pairs,Hidden Pairs,Pointing Pairs/Triples,Box/Line Intersections,Guesses,Backtracks,Difficulty";
            cout << "" << endl;
        }

        // Create a new puzzle board
        // and set the options
        SudokuBoard* ss = new SudokuBoard();
        ss->setRecordHistory(printHistory || printInstructions || printStats || difficulty!=SudokuBoard::UNKNOWN);
        ss->setLogHistory(logHistory);
        ss->setPrintStyle(printStyle);

        // Solve puzzle or generate puzzles
        // until end of input for solving, or
        // until we have generated the specified number.
        bool done = false;
        int numberGenerated = 0;
        while (!done){
            // record the start time for the timer.
            long puzzleStartTime = getMicroseconds();

            // iff something has been printed for this particular puzzle
            bool printedSomething = false;

            // Record whether the puzzle was possible or not,
            // so that we don't try to solve impossible givens.
            bool havePuzzle = false;
            if (action == GENERATE){
                // Generate a puzzle
                havePuzzle = ss->generatePuzzle();
                if (!havePuzzle && printPuzzle){
                    cout << "Could not generate puzzle.";
                    if (printStyle==SudokuBoard::CSV){
                        cout << ",";
                    } else {
                        cout << endl;
                    }
                    printedSomething = true;
                }
            } else {
                // Read the next puzzle on STDIN
                int* puzzle = new int[BOARD_SIZE];
                if (readPuzzleFromStdIn(puzzle)){
                    havePuzzle = ss->setPuzzle(puzzle);
                    if (!havePuzzle){
                        if (printPuzzle){
                            ss->printPuzzle();
                            printedSomething = true;
                        }
                        if (printSolution) {
                            cout << "Puzzle is not possible.";
                            if (printStyle==SudokuBoard::CSV){
                                cout << ",";
                            } else {
                                cout << endl;
                            }
                            printedSomething = true;
                        }
                    }
                } else {
                    // Set loop to terminate when nothing is left on STDIN
                    havePuzzle = false;
                    done = true;
                }
                delete puzzle;
            }

           int solutions = 0;

            if (havePuzzle){

                // Count the solutions if requested.
                // (Must be done before solving, as it would
                // mess up the stats.)
                if (countSolutions){
                    solutions = ss->countSolutions();
                }

                // Solve the puzzle
                if (printSolution || printHistory || printStats || printInstructions || difficulty!=SudokuBoard::UNKNOWN){
                    ss->solve();
                }

                // Bail out if it didn't meet the difficulty standards for generation
                if (action == GENERATE){
                    if (difficulty!=SudokuBoard::UNKNOWN && difficulty!=ss->getDifficulty()){
                        havePuzzle = false;
                    } else {
                        numberGenerated++;
                        // Set loop to terminate if enough have been generated.
                        if (numberGenerated >= numberToGenerate) done = true;
                    }
                }
            }

            if (havePuzzle){

                // With a puzzle now in hand and possibly solved
                // print out the solution, stats, etc.
                printedSomething = true;

                // Record the end time for the timer.
                long puzzleDoneTime = getMicroseconds();

                // Print the puzzle itself.
                if (printPuzzle) ss->printPuzzle();

                // Print the solution if there is one
                if (printSolution){
                    if (ss->isSolved()){
                        ss->printSolution();
                    } else {
                        cout << "Puzzle has no solution.";
                        if (printStyle==SudokuBoard::CSV){
                            cout << ",";
                        } else {
                            cout << endl;
                        }
                    }
                }

                // Print the steps taken to solve or attempt to solve the puzzle.
                if (printHistory) ss->printSolveHistory();
                // Print the instructions for solving the puzzle
                if (printInstructions) ss->printSolveInstructions();

                // Print the number of solutions to the puzzle.
                if (countSolutions){
                    if (printStyle == SudokuBoard::CSV){
                        cout << solutions << ",";
                    } else {
                        if (solutions == 0){
                            cout << "There are no solutions to the puzzle." << endl;
                        } else if (solutions == 1){
                            cout << "The solution to the puzzle is unique." << endl;
                        } else {
                            cout << "There are " << solutions << " solutions to the puzzle." << endl;
                        }
                    }
                }

                // Print out the time it took to solve the puzzle.
                if (timer){
                    double t = ((double)(puzzleDoneTime - puzzleStartTime))/1000.0;
                    if (printStyle == SudokuBoard::CSV){
                        cout << t << ",";
                    } else {
                        cout << "Time: " << t  << " milliseconds" << endl;
                    }
                }

                // Print any stats we were able to gather while solving the puzzle.
                if (printStats){
                    int givenCount = ss->getGivenCount();
                    int singleCount = ss->getSingleCount();
                    int hiddenSingleCount = ss->getHiddenSingleCount();
                    int nakedPairCount = ss->getNakedPairCount();
                    int hiddenPairCount = ss->getHiddenPairCount();
                    int pointingPairTripleCount = ss->getPointingPairTripleCount();
                    int boxReductionCount = ss->getBoxLineReductionCount();
                    int guessCount = ss->getGuessCount();
                    int backtrackCount = ss->getBacktrackCount();
                    char* difficultyString = ss->getDifficultyAsString();
                    if (printStyle == SudokuBoard::CSV){
                        cout << givenCount << ","  << singleCount << "," << hiddenSingleCount
                                << "," << nakedPairCount << "," << hiddenPairCount
                                << ","  << pointingPairTripleCount  << ","  << boxReductionCount
                                << "," << guessCount << "," << backtrackCount
                                << "," << difficultyString << ",";
                    } else {
                        cout << "Number of Givens: " << givenCount  << endl;
                        cout << "Number of Singles: " << singleCount << endl;
                        cout << "Number of Hidden Singles: " << hiddenSingleCount  << endl;
                        cout << "Number of Naked Pairs: " << nakedPairCount  << endl;
                        cout << "Number of Hidden Pairs: " << hiddenPairCount  << endl;
                        cout << "Number of Pointing Pairs/Triples: " << pointingPairTripleCount  << endl;
                        cout << "Number of Box/Line Intersections: " << boxReductionCount  << endl;
                        cout << "Number of Guesses: " << guessCount  << endl;
                        cout << "Number of Backtracks: " << backtrackCount  << endl;
                        cout << "Difficulty: " << difficultyString  << endl;
                    }
                }
                puzzleCount++;
            }
            if (printedSomething && printStyle == SudokuBoard::CSV){
                cout << endl;
            }
        }

        delete ss;

        long applicationDoneTime = getMicroseconds();
        // Print out the time it took to do everything
        if (timer){
            double t = ((double)(applicationDoneTime - applicationStartTime))/1000000.0;
            cout << puzzleCount << " puzzle" << ((puzzleCount==1)?"":"s") << " " << (action==GENERATE?"generated":"solved") << " in " << t << " seconds." << endl;
        }


    } catch (char const* s){
        cout << s <<  endl;
        return 1;
    }

    return 0;
}

void printVersion(){
    cout << PACKAGE_STRING << endl;
}

void printAbout(){
    cout << PACKAGE_NAME << " - Sudoku solver and generator." << endl;
    cout << "Written by Stephen Ostermiller copyright 2006." << endl;
    cout << "http://ostermiller.org/qqwing/" << endl;
    cout << "" << endl;
    cout << "This program is free software; you can redistribute it and/or modify" << endl;
    cout << "it under the terms of the GNU General Public License as published by" << endl;
    cout << "the Free Software Foundation; either version 2 of the License, or" << endl;
    cout << "(at your option) any later version." << endl;
    cout << "" << endl;
    cout << "This program is distributed in the hope that it will be useful," << endl;
    cout << "but WITHOUT ANY WARRANTY; without even the implied warranty of" << endl;
    cout << "MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the" << endl;
    cout << "GNU General Public License for more details." << endl;
    cout << "" << endl;
    cout << "You should have received a copy of the GNU General Public License" << endl;
    cout << "along with this program; if not, write to the Free Software" << endl;
    cout << "Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA" << endl;
}

void printHelp(char* programName){
    cout << programName << " <options>" << endl;
    cout << "Sudoku solver and generator." << endl;
    cout << "  --generate <num>     Generate new puzzles" << endl;
    cout << "  --solve              Solve all the puzzles from standard input" << endl;
    cout << "  --difficulty <diff>  Generate only simple,easy, intermediate, or expert" << endl;
    cout << "  --puzzle             Print the puzzle (default when generating)" << endl;
    cout << "  --nopuzzle           Do not print the puzzle (default when solving)" << endl;
    cout << "  --solution           Print the solution (default when solving)" << endl;
    cout << "  --nosolution         Do not print the solution (default when generating)" << endl;
    cout << "  --stats              Print statistics about moves used to solve the puzzle" << endl;
    cout << "  --nostats            Do not print statistics (default)" << endl;
    #if HAVE_GETTIMEOFDAY == 1
        cout << "  --timer              Print time to generate or solve each puzzle" << endl;
        cout << "  --notimer            Do not print solve or generation times (default)" << endl;
    #endif
    cout << "  --count-solutions    Count the number of solutions to puzzles" << endl;
    cout << "  --nocount-solutions  Do not count the number of solutions (default)" << endl;
    cout << "  --history            Print trial and error used when solving" << endl;
    cout << "  --nohistory          Do not print trial and error to solve (default)" << endl;
    cout << "  --instructions       Print the steps (at least 81) needed to solve the puzzle" << endl;
    cout << "  --noinstructions     Do not print steps to solve (default)" << endl;
    cout << "  --log-history        Print trial and error to solve as it happens" << endl;
    cout << "  --nolog-history      Do not print trial and error  to solve as it happens" << endl;
    cout << "  --one-line           Print puzzles on one line of 81 characters" << endl;
    cout << "  --compact            Print puzzles on 9 lines of 9 characters" << endl;
    cout << "  --readable           Print puzzles in human readable form (default)" << endl;
    cout << "  --csv                Ouput CSV format with one line puzzles" << endl;
    cout << "  --help               Print this message" << endl;
    cout << "  --about              Author and license information" << endl;
    cout << "  --version            Display current version number" << endl;
}

/**
 * Create a new Sudoku board
 */
SudokuBoard::SudokuBoard(){
    puzzle = new int[BOARD_SIZE];
    solution = new int[BOARD_SIZE];
    solutionRound = new int[BOARD_SIZE];
    possibilities = new int[POSSIBILITY_SIZE];
    recordHistory = false;
    printStyle = READABLE;
    randomBoardArray = new int[BOARD_SIZE];
    randomPossibilityArray = new int[NUM_POSS];
    solveHistory = new vector<LogItem*>();
    solveInstructions = new vector<LogItem*>();
    {for (int i=0; i<BOARD_SIZE; i++){
        randomBoardArray[i] = i;
    }}
    {for (int i=0; i<NUM_POSS; i++){
        randomPossibilityArray[i] = i;
    }}
}

/**
 * Get the number of cells that are
 * set in the puzzle (as opposed to
 * figured out in the solution
 */
int SudokuBoard::getGivenCount(){
    int count = 0;
    {for (int i=0; i<BOARD_SIZE; i++){
        if (puzzle[i] != 0) count++;
    }}
    return count;
}

/**
 * Set the board to the given puzzle.
 * The given puzzle must be an array of 81 integers.
 */
bool SudokuBoard::setPuzzle(int* initPuzzle){
    {for (int i=0; i<BOARD_SIZE; i++){
        puzzle[i] = (initPuzzle==NULL)?0:initPuzzle[i];
    }}
    return reset();
}

/**
 * Reset the board to its initial state with
 * only the givens.
 * This method clears any solution, resets statistics,
 * and clears any history messages.
 */
bool SudokuBoard::reset(){
    {for (int i=0; i<BOARD_SIZE; i++){
        solution[i] = 0;
    }}
    {for (int i=0; i<BOARD_SIZE; i++){
        solutionRound[i] = 0;
    }}
    {for (int i=0; i<POSSIBILITY_SIZE; i++){
        possibilities[i] = 0;
    }}

    {for (int i=0;i<solveHistory->size();i++){
        delete solveHistory->at(i);
    }}
    solveHistory->clear();
    solveInstructions->clear();

    int round = 1;
    for (int position=0; position<BOARD_SIZE; position++){
        if (puzzle[position] > 0){
            int valIndex = puzzle[position]-1;
            int valPos = getPossibilityIndex(valIndex,position);
            int value = puzzle[position];
            if (possibilities[valPos] != 0) return false;
            mark(position,round,value);
            if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::GIVEN, value, position));
        }
    }

    return true;
}

/**
 * Get the difficulty rating.
 */
SudokuBoard::Difficulty SudokuBoard::getDifficulty(){
    if (getGuessCount() > 0) return SudokuBoard::EXPERT;
    if (getBoxLineReductionCount() > 0) return SudokuBoard::INTERMEDIATE;
    if (getPointingPairTripleCount() > 0) return SudokuBoard::INTERMEDIATE;
    if (getHiddenPairCount() > 0) return SudokuBoard::INTERMEDIATE;
    if (getNakedPairCount() > 0) return SudokuBoard::INTERMEDIATE;
    if (getHiddenSingleCount() > 0) return SudokuBoard::EASY;
    if (getSingleCount() > 0) return SudokuBoard::SIMPLE;
    return SudokuBoard::UNKNOWN;
}

/**
 * Get the difficulty rating.
 */
char* SudokuBoard::getDifficultyAsString(){
    SudokuBoard::Difficulty difficulty = getDifficulty();
    switch (difficulty){
        case SudokuBoard::EXPERT: return "Expert"; break;
        case SudokuBoard::INTERMEDIATE: return "Intermediate"; break;
        case SudokuBoard::EASY: return "Easy"; break;
        case SudokuBoard::SIMPLE: return "Simple"; break;
        default: return "Unknown"; break;
    }
}

/**
 * Get the number of cells for which the solution was determined
 * because there was only one possible value for that cell.
 */
int SudokuBoard::getSingleCount(){
    return getLogCount(solveInstructions, LogItem::SINGLE);
}

/**
 * Get the number of cells for which the solution was determined
 * because that cell had the only possibility for some value in
 * the row, column, or section.
 */
int SudokuBoard::getHiddenSingleCount(){
    return getLogCount(solveInstructions, LogItem::HIDDEN_SINGLE_ROW) +
            getLogCount(solveInstructions, LogItem::HIDDEN_SINGLE_COLUMN) +
            getLogCount(solveInstructions, LogItem::HIDDEN_SINGLE_SECTION);
}

/**
 * Get the number of naked pair reductions that were performed
 * in solving this puzzle.
 */
int SudokuBoard::getNakedPairCount(){
    return getLogCount(solveInstructions, LogItem::NAKED_PAIR_ROW) +
            getLogCount(solveInstructions, LogItem::NAKED_PAIR_COLUMN) +
            getLogCount(solveInstructions, LogItem::NAKED_PAIR_SECTION);
}

/**
 * Get the number of hidden pair reductions that were performed
 * in solving this puzzle.
 */
int SudokuBoard::getHiddenPairCount(){
    return getLogCount(solveInstructions, LogItem::HIDDEN_PAIR_ROW) +
            getLogCount