Full source code is available on github.

There are several major source files for the C++ version of QQWing:

/*
 * qqwing - Sudoku solver and generator
 * Copyright (C) 2006-2014 Stephen Ostermiller http://ostermiller.org/
 * Copyright (C) 2007 Jacques Bensimon (jacques@ipm.com)
 * Copyright (C) 2011 Jean Guillerez (j.guillerez - orange.fr)
 * Copyright (C) 2014 Michael Catanzaro (mcatanzaro@gnome.org)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
#include "config.h"

#include <cstdlib>
#include <iostream>

#include "qqwing.hpp"

namespace qqwing {

    string getVersion(){
        return 1.3.4;
    }

    /**
     * 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;
    };

    void shuffleArray(int* array, int size);
    SudokuBoard::Symmetry getRandomSymmetry();
    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);

    /**
     * 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] ),
        randomBoardArray ( new int[BOARD_SIZE] ),
        randomPossibilityArray ( new int[ROW_COL_SEC_SIZE] ),
        recordHistory ( false ),
        logHistory( false ),
        solveHistory ( new vector<LogItem*>() ),
        solveInstructions ( new vector<LogItem*>() ),
        printStyle ( READABLE ),
        lastSolveRound (0)
    {
        {for (int i=0; i<BOARD_SIZE; i++){
            randomBoardArray[i] = i;
        }}
        {for (int i=0; i<ROW_COL_SEC_SIZE; 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();
    }

    /**
     * Retrieves the puzzle as an unmodifiable array of 81 integers.
     */
    const int* SudokuBoard::getPuzzle(){
        return puzzle;
    }

    /**
     * Retrieves the puzzle's solution as an unmodifiable array of 81 integers.
     */
    const int* SudokuBoard::getSolution(){
        return solution;
    }

    /**
     * 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 (unsigned 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.
     *
     * This method will return SudokuBoard::UNKNOWN unless
     * a puzzle has been generated or set and then the following methods called:
     * setRecordHistory(true), and solve()
     */
    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.
     *
     * This method will return "Unknown" unless
     * a puzzle has been generated or set and then the following methods called:
     * setRecordHistory(true), and solve()
     */
    string SudokuBoard::getDifficultyAsString(){
        SudokuBoard::Difficulty difficulty = getDifficulty();
        switch (difficulty){
            case SudokuBoard::EXPERT: return "Expert";
            case SudokuBoard::INTERMEDIATE: return "Intermediate";
            case SudokuBoard::EASY: return "Easy";
            case SudokuBoard::SIMPLE: return "Simple";
            default: return "Unknown";
        }
    }

    /**
     * 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(solveInstructions, LogItem::HIDDEN_PAIR_COLUMN) +
                getLogCount(solveInstructions, LogItem::HIDDEN_PAIR_SECTION);
    }

    /**
     * Get the number of pointing pair/triple reductions that were performed
     * in solving this puzzle.
     */
    int SudokuBoard::getPointingPairTripleCount(){
        return getLogCount(solveInstructions, LogItem::POINTING_PAIR_TRIPLE_ROW)+
            getLogCount(solveInstructions, LogItem::POINTING_PAIR_TRIPLE_COLUMN);
    }

    /**
     * Get the number of box/line reductions that were performed
     * in solving this puzzle.
     */
    int SudokuBoard::getBoxLineReductionCount(){
        return getLogCount(solveInstructions, LogItem::ROW_BOX)+
            getLogCount(solveInstructions, LogItem::COLUMN_BOX);
    }

    /**
     * Get the number lucky guesses in solving this puzzle.
     */
    int SudokuBoard::getGuessCount(){
        return getLogCount(solveInstructions, LogItem::GUESS);
    }

    /**
     * Get the number of backtracks (unlucky guesses) required
     * when solving this puzzle.
     */
    int SudokuBoard::getBacktrackCount(){
        return getLogCount(solveHistory, LogItem::ROLLBACK);
    }

    void SudokuBoard::shuffleRandomArrays(){
        shuffleArray(randomBoardArray, BOARD_SIZE);
        shuffleArray(randomPossibilityArray, ROW_COL_SEC_SIZE);
    }

    void SudokuBoard::clearPuzzle(){
        // Clear any existing puzzle
        {for (int i=0; i<BOARD_SIZE; i++){
            puzzle[i] = 0;
        }}
        reset();
    }

    bool SudokuBoard::generatePuzzle(){
        return generatePuzzleSymmetry(SudokuBoard::NONE);
    }

    bool SudokuBoard::generatePuzzleSymmetry(SudokuBoard::Symmetry symmetry){

        if (symmetry == SudokuBoard::RANDOM) symmetry = getRandomSymmetry();

        // Don't record history while generating.
        bool recHistory = recordHistory;
        setRecordHistory(false);
        bool lHistory = logHistory;
        setLogHistory(false);

        clearPuzzle();

        // Start by getting the randomness in order so that
        // each puzzle will be different from the last.
        shuffleRandomArrays();

        // Now solve the puzzle the whole way.  The solve
        // uses random algorithms, so we should have a
        // really randomly totally filled sudoku
        // Even when starting from an empty grid
        solve();

        if (symmetry == SudokuBoard::NONE){
            // Rollback any square for which it is obvious that
            // the square doesn't contribute to a unique solution
            // (ie, squares that were filled by logic rather
            // than by guess)
            rollbackNonGuesses();
        }

        // Record all marked squares as the puzzle so
        // that we can call countSolutions without losing it.
        {for (int i=0; i<BOARD_SIZE; i++){
            puzzle[i] = solution[i];
        }}

        // Rerandomize everything so that we test squares
        // in a different order than they were added.
        shuffleRandomArrays();

        // Remove one value at a time and see if
        // the puzzle still has only one solution.
        // If it does, leave it out the point because
        // it is not needed.
        {for (int i=0; i<BOARD_SIZE; i++){
            // check all the positions, but in shuffled order
            int position = randomBoardArray[i];
            if (puzzle[position] > 0){
                int positionsym1 = -1;
                int positionsym2 = -1;
                int positionsym3 = -1;
                switch (symmetry){
                    case ROTATE90:
                        positionsym2 = rowColumnToCell(ROW_COL_SEC_SIZE-1-cellToColumn(position),cellToRow(position));
                        positionsym3 = rowColumnToCell(cellToColumn(position),ROW_COL_SEC_SIZE-1-cellToRow(position));
                    case ROTATE180:
                        positionsym1 = rowColumnToCell(ROW_COL_SEC_SIZE-1-cellToRow(position),ROW_COL_SEC_SIZE-1-cellToColumn(position));
                    break;
                    case MIRROR:
                        positionsym1 = rowColumnToCell(cellToRow(position),ROW_COL_SEC_SIZE-1-cellToColumn(position));
                    break;
                    case FLIP:
                        positionsym1 = rowColumnToCell(ROW_COL_SEC_SIZE-1-cellToRow(position),cellToColumn(position));
                    break;
                    case RANDOM: // NOTE: Should never happen
                    break;
                    case NONE: // NOTE: No need to do anything
                    break;
                }
                // try backing out the value and
                // counting solutions to the puzzle
                int savedValue = puzzle[position];
                puzzle[position] = 0;
                int savedSym1 = 0;
                if (positionsym1 >= 0){
                    savedSym1 = puzzle[positionsym1];
                    puzzle[positionsym1] = 0;
                }
                int savedSym2 = 0;
                if (positionsym2 >= 0){
                    savedSym2 = puzzle[positionsym2];
                    puzzle[positionsym2] = 0;
                }
                int savedSym3 = 0;
                if (positionsym3 >= 0){
                    savedSym3 = puzzle[positionsym3];
                    puzzle[positionsym3] = 0;
                }
                reset();
                if (countSolutions(2, true) > 1){
                    // Put it back in, it is needed
                    puzzle[position] = savedValue;
                    if (positionsym1 >= 0 && savedSym1 != 0) puzzle[positionsym1] = savedSym1;
                    if (positionsym2 >= 0 && savedSym2 != 0) puzzle[positionsym2] = savedSym2;
                    if (positionsym3 >= 0 && savedSym3 != 0) puzzle[positionsym3] = savedSym3;
                }
            }
        }}

        // Clear all solution info, leaving just the puzzle.
        reset();

        // Restore recording history.
        setRecordHistory(recHistory);
        setLogHistory(lHistory);

        return true;

    }

    void SudokuBoard::rollbackNonGuesses(){
        // Guesses are odd rounds
        // Non-guesses are even rounds
        {for (int i=2; i<=lastSolveRound; i+=2){
            rollbackRound(i);
        }}
    }

    void SudokuBoard::setPrintStyle(PrintStyle ps){
        printStyle = ps;
    }

    void SudokuBoard::setRecordHistory(bool recHistory){
        recordHistory = recHistory;
    }

    void SudokuBoard::setLogHistory(bool logHist){
        logHistory = logHist;
    }

    void SudokuBoard::addHistoryItem(LogItem* l){
        if (logHistory){
            l->print();
            cout << endl;
        }
        if (recordHistory){
            solveHistory->push_back(l);
            solveInstructions->push_back(l);
        } else {
            delete l;
        }
    }

    void SudokuBoard::printHistory(vector<LogItem*>* v){
        if (!recordHistory){
            cout << "History was not recorded.";
            if (printStyle == CSV){
                cout << " -- ";
            } else {
                cout << endl;
            }
        }
        {for (unsigned int i=0;i<v->size();i++){
            cout << i+1 << ". ";
            v->at(i)->print();
            if (printStyle == CSV){
                cout << " -- ";
            } else {
                cout << endl;
            }
        }}
        if (printStyle == CSV){
            cout << ",";
        } else {
            cout << endl;
        }
    }

    void SudokuBoard::printSolveInstructions(){
        if (isSolved()){
            printHistory(solveInstructions);
        } else {
            cout << "No solve instructions - Puzzle is not possible to solve." << endl;
        }
    }

    void SudokuBoard::printSolveHistory(){
        printHistory(solveHistory);
    }

    bool SudokuBoard::solve(){
        reset();
        shuffleRandomArrays();
        return solve(2);
    }

    bool SudokuBoard::solve(int round){
        lastSolveRound = round;

        while (singleSolveMove(round)){
            if (isSolved()) return true;
            if (isImpossible()) return false;
        }

        int nextGuessRound = round+1;
        int nextRound = round+2;
        for (int guessNumber=0; guess(nextGuessRound, guessNumber); guessNumber++){
            if (isImpossible() || !solve(nextRound)){
                rollbackRound(nextRound);
                rollbackRound(nextGuessRound);
            } else {
                return true;
            }
        }
        return false;
    }

    bool SudokuBoard::hasNoSolution(){
        return countSolutionsLimited() == 0;
    }

    bool SudokuBoard::hasUniqueSolution(){
        return countSolutionsLimited() == 1;
    }

    bool SudokuBoard::hasMultipleSolutions(){
        return countSolutionsLimited() > 1;
    }

    int SudokuBoard::countSolutions(){
        return countSolutions(false);
    }

    int SudokuBoard::countSolutionsLimited(){
        return countSolutions(true);
    }

    int SudokuBoard::countSolutions(bool limitToTwo){
        // Don't record history while generating.
        bool recHistory = recordHistory;
        setRecordHistory(false);
        bool lHistory = logHistory;
        setLogHistory(false);

        reset();
        int solutionCount = countSolutions(2, limitToTwo);

        // Restore recording history.
        setRecordHistory(recHistory);
        setLogHistory(lHistory);

        return solutionCount;
    }

    int SudokuBoard::countSolutions(int round, bool limitToTwo){
        while (singleSolveMove(round)){
            if (isSolved()){
                rollbackRound(round);
                return 1;
            }
            if (isImpossible()){
                rollbackRound(round);
                return 0;
            }
        }

        int solutions = 0;
        int nextRound = round+1;
        for (int guessNumber=0; guess(nextRound, guessNumber); guessNumber++){
            solutions += countSolutions(nextRound, limitToTwo);
            if (limitToTwo && solutions >=2){
                rollbackRound(round);
                return solutions;
            }
        }
        rollbackRound(round);
        return solutions;
    }

    void SudokuBoard::rollbackRound(int round){
        if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::ROLLBACK));
        {for (int i=0; i<BOARD_SIZE; i++){
            if (solutionRound[i] == round){
                solutionRound[i] = 0;
                solution[i] = 0;
            }
        }}
        {for (int i=0; i<POSSIBILITY_SIZE; i++){
            if (possibilities[i] == round){
                possibilities[i] = 0;
            }
        }}

        while(solveInstructions->size() > 0 && solveInstructions->back()->getRound() == round){
            solveInstructions->pop_back();
        }
    }

    bool SudokuBoard::isSolved(){
        {for (int i=0; i<BOARD_SIZE; i++){
            if (solution[i] == 0){
                return false;
            }
        }}
        return true;
    }

    bool SudokuBoard::isImpossible(){
        for (int position=0; position<BOARD_SIZE; position++){
            if (solution[position] == 0){
                int count = 0;
                for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0) count++;
                }
                if (count == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    int SudokuBoard::findPositionWithFewestPossibilities(){
        int minPossibilities = 10;
        int bestPosition = 0;
        {for (int i=0; i<BOARD_SIZE; i++){
            int position = randomBoardArray[i];
            if (solution[position] == 0){
                int count = 0;
                for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0) count++;
                }
                if (count < minPossibilities){
                    minPossibilities = count;
                    bestPosition = position;
                }
            }
        }}
        return bestPosition;
    }

    bool SudokuBoard::guess(int round, int guessNumber){
        int localGuessCount = 0;
        int position = findPositionWithFewestPossibilities();
        {for (int i=0; i<ROW_COL_SEC_SIZE; i++){
            int valIndex = randomPossibilityArray[i];
            int valPos = getPossibilityIndex(valIndex,position);
            if (possibilities[valPos] == 0){
                if (localGuessCount == guessNumber){
                    int value = valIndex+1;
                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::GUESS, value, position));
                    mark(position, round, value);
                    return true;
                }
                localGuessCount++;
            }
        }}
        return false;
    }

    bool SudokuBoard::singleSolveMove(int round){
        if (onlyPossibilityForCell(round)) return true;
        if (onlyValueInSection(round)) return true;
        if (onlyValueInRow(round)) return true;
        if (onlyValueInColumn(round)) return true;
        if (handleNakedPairs(round)) return true;
        if (pointingRowReduction(round)) return true;
        if (pointingColumnReduction(round)) return true;
        if (rowBoxReduction(round)) return true;
        if (colBoxReduction(round)) return true;
        if (hiddenPairInRow(round)) return true;
        if (hiddenPairInColumn(round)) return true;
        if (hiddenPairInSection(round)) return true;
        return false;
    }

    bool SudokuBoard::colBoxReduction(int round){
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            for (int col=0; col<ROW_COL_SEC_SIZE; col++){
                int colStart = columnToFirstCell(col);
                bool inOneBox = true;
                int colBox = -1;
                {for (int i=0; i<GRID_SIZE; i++){
                    for (int j=0; j<GRID_SIZE; j++){
                        int row = i*GRID_SIZE+j;
                        int position = rowColumnToCell(row, col);
                        int valPos = getPossibilityIndex(valIndex,position);
                        if(possibilities[valPos] == 0){
                            if (colBox == -1 || colBox == i){
                                colBox = i;
                            } else {
                                inOneBox = false;
                            }
                        }

                    }
                }}
                if (inOneBox && colBox != -1){
                    bool doneSomething = false;
                    int row = GRID_SIZE*colBox;
                    int secStart = cellToSectionStartCell(rowColumnToCell(row, col));
                    int secStartRow = cellToRow(secStart);
                    int secStartCol = cellToColumn(secStart);
                    {for (int i=0; i<GRID_SIZE; i++){
                        for (int j=0; j<GRID_SIZE; j++){
                            int row2 = secStartRow+i;
                            int col2 = secStartCol+j;
                            int position = rowColumnToCell(row2, col2);
                            int valPos = getPossibilityIndex(valIndex,position);
                            if (col != col2 && possibilities[valPos] == 0){
                                possibilities[valPos] = round;
                                doneSomething = true;
                            }
                        }
                    }}
                    if (doneSomething){
                        if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::COLUMN_BOX, valIndex+1, colStart));
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool SudokuBoard::rowBoxReduction(int round){
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            for (int row=0; row<ROW_COL_SEC_SIZE; row++){
                int rowStart = rowToFirstCell(row);
                bool inOneBox = true;
                int rowBox = -1;
                {for (int i=0; i<GRID_SIZE; i++){
                    for (int j=0; j<GRID_SIZE; j++){
                        int column = i*GRID_SIZE+j;
                        int position = rowColumnToCell(row, column);
                        int valPos = getPossibilityIndex(valIndex,position);
                        if(possibilities[valPos] == 0){
                            if (rowBox == -1 || rowBox == i){
                                rowBox = i;
                            } else {
                                inOneBox = false;
                            }
                        }

                    }
                }}
                if (inOneBox && rowBox != -1){
                    bool doneSomething = false;
                    int column = GRID_SIZE*rowBox;
                    int secStart = cellToSectionStartCell(rowColumnToCell(row, column));
                    int secStartRow = cellToRow(secStart);
                    int secStartCol = cellToColumn(secStart);
                    {for (int i=0; i<GRID_SIZE; i++){
                        for (int j=0; j<GRID_SIZE; j++){
                            int row2 = secStartRow+i;
                            int col2 = secStartCol+j;
                            int position = rowColumnToCell(row2, col2);
                            int valPos = getPossibilityIndex(valIndex,position);
                            if (row != row2 && possibilities[valPos] == 0){
                                possibilities[valPos] = round;
                                doneSomething = true;
                            }
                        }
                    }}
                    if (doneSomething){
                        if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::ROW_BOX, valIndex+1, rowStart));
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool SudokuBoard::pointingRowReduction(int round){
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            for (int section=0; section<ROW_COL_SEC_SIZE; section++){
                int secStart = sectionToFirstCell(section);
                bool inOneRow = true;
                int boxRow = -1;
                for (int j=0; j<GRID_SIZE; j++){
                    {for (int i=0; i<GRID_SIZE; i++){
                        int secVal=secStart+i+(ROW_COL_SEC_SIZE*j);
                        int valPos = getPossibilityIndex(valIndex,secVal);
                        if(possibilities[valPos] == 0){
                            if (boxRow == -1 || boxRow == j){
                                boxRow = j;
                            } else {
                                inOneRow = false;
                            }
                        }
                    }}
                }
                if (inOneRow && boxRow != -1){
                    bool doneSomething = false;
                    int row = cellToRow(secStart) + boxRow;
                    int rowStart = rowToFirstCell(row);

                    {for (int i=0; i<ROW_COL_SEC_SIZE; i++){
                        int position = rowStart+i;
                        int section2 = cellToSection(position);
                        int valPos = getPossibilityIndex(valIndex,position);
                        if (section != section2 && possibilities[valPos] == 0){
                            possibilities[valPos] = round;
                            doneSomething = true;
                        }
                    }}
                    if (doneSomething){
                        if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::POINTING_PAIR_TRIPLE_ROW, valIndex+1, rowStart));
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool SudokuBoard::pointingColumnReduction(int round){
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            for (int section=0; section<ROW_COL_SEC_SIZE; section++){
                int secStart = sectionToFirstCell(section);
                bool inOneCol = true;
                int boxCol = -1;
                {for (int i=0; i<GRID_SIZE; i++){
                    for (int j=0; j<GRID_SIZE; j++){
                        int secVal=secStart+i+(ROW_COL_SEC_SIZE*j);
                        int valPos = getPossibilityIndex(valIndex,secVal);
                        if(possibilities[valPos] == 0){
                            if (boxCol == -1 || boxCol == i){
                                boxCol = i;
                            } else {
                                inOneCol = false;
                            }
                        }
                    }
                }}
                if (inOneCol && boxCol != -1){
                    bool doneSomething = false;
                    int col = cellToColumn(secStart) + boxCol;
                    int colStart = columnToFirstCell(col);

                    {for (int i=0; i<ROW_COL_SEC_SIZE; i++){
                        int position = colStart+(ROW_COL_SEC_SIZE*i);
                        int section2 = cellToSection(position);
                        int valPos = getPossibilityIndex(valIndex,position);
                        if (section != section2 && possibilities[valPos] == 0){
                            possibilities[valPos] = round;
                            doneSomething = true;
                        }
                    }}
                    if (doneSomething){
                        if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::POINTING_PAIR_TRIPLE_COLUMN, valIndex+1, colStart));
                        return true;
                    }
                }
            }
        }
        return false;
    }

    int SudokuBoard::countPossibilities(int position){
        int count = 0;
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            int valPos = getPossibilityIndex(valIndex,position);
            if (possibilities[valPos] == 0) count++;
        }
        return count;
    }

    bool SudokuBoard::arePossibilitiesSame(int position1, int position2){
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            int valPos1 = getPossibilityIndex(valIndex,position1);
            int valPos2 = getPossibilityIndex(valIndex,position2);
            if ((possibilities[valPos1] == 0 || possibilities[valPos2] == 0) && (possibilities[valPos1] != 0 || possibilities[valPos2] != 0)){
                return false;
            }
        }
        return true;
    }

    bool SudokuBoard::removePossibilitiesInOneFromTwo(int position1, int position2, int round){
        bool doneSomething = false;
        for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            int valPos1 = getPossibilityIndex(valIndex,position1);
            int valPos2 = getPossibilityIndex(valIndex,position2);
            if (possibilities[valPos1] == 0 && possibilities[valPos2] == 0){
                possibilities[valPos2] = round;
                doneSomething = true;
            }
        }
        return doneSomething;
    }

    bool SudokuBoard::hiddenPairInColumn(int round){
        for (int column=0; column<ROW_COL_SEC_SIZE; column++){
            for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                int r1 = -1;
                int r2 = -1;
                int valCount = 0;
                for (int row=0; row<ROW_COL_SEC_SIZE; row++){
                    int position = rowColumnToCell(row,column);
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0){
                        if (r1 == -1 || r1 == row){
                            r1 = row;
                        } else if (r2 == -1 || r2 == row){
                            r2 = row;
                        }
                        valCount++;
                    }
                }
                if (valCount==2){
                    for (int valIndex2=valIndex+1; valIndex2<ROW_COL_SEC_SIZE; valIndex2++){
                        int r3 = -1;
                        int r4 = -1;
                        int valCount2 = 0;
                        for (int row=0; row<ROW_COL_SEC_SIZE; row++){
                            int position = rowColumnToCell(row,column);
                            int valPos = getPossibilityIndex(valIndex2,position);
                            if (possibilities[valPos] == 0){
                                if (r3 == -1 || r3 == row){
                                    r3 = row;
                                } else if (r4 == -1 || r4 == row){
                                    r4 = row;
                                }
                                valCount2++;
                            }
                        }
                        if (valCount2==2 && r1==r3 && r2==r4){
                            bool doneSomething = false;
                            for (int valIndex3=0; valIndex3<ROW_COL_SEC_SIZE; valIndex3++){
                                if (valIndex3 != valIndex && valIndex3 != valIndex2){
                                    int position1 = rowColumnToCell(r1,column);
                                    int position2 = rowColumnToCell(r2,column);
                                    int valPos1 = getPossibilityIndex(valIndex3,position1);
                                    int valPos2 = getPossibilityIndex(valIndex3,position2);
                                    if (possibilities[valPos1] == 0){
                                        possibilities[valPos1] = round;
                                        doneSomething = true;
                                    }
                                    if (possibilities[valPos2] == 0){
                                        possibilities[valPos2] = round;
                                        doneSomething = true;
                                    }
                                }
                            }
                            if (doneSomething){
                                if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_PAIR_COLUMN, valIndex+1, rowColumnToCell(r1,column)));
                                return true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }

    bool SudokuBoard::hiddenPairInSection(int round){
        for (int section=0; section<ROW_COL_SEC_SIZE; section++){
            for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                int si1 = -1;
                int si2 = -1;
                int valCount = 0;
                for (int secInd=0; secInd<ROW_COL_SEC_SIZE; secInd++){
                    int position = sectionToCell(section,secInd);
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0){
                        if (si1 == -1 || si1 == secInd){
                            si1 = secInd;
                        } else if (si2 == -1 || si2 == secInd){
                            si2 = secInd;
                        }
                        valCount++;
                    }
                }
                if (valCount==2){
                    for (int valIndex2=valIndex+1; valIndex2<ROW_COL_SEC_SIZE; valIndex2++){
                        int si3 = -1;
                        int si4 = -1;
                        int valCount2 = 0;
                        for (int secInd=0; secInd<ROW_COL_SEC_SIZE; secInd++){
                            int position = sectionToCell(section,secInd);
                            int valPos = getPossibilityIndex(valIndex2,position);
                            if (possibilities[valPos] == 0){
                                if (si3 == -1 || si3 == secInd){
                                    si3 = secInd;
                                } else if (si4 == -1 || si4 == secInd){
                                    si4 = secInd;
                                }
                                valCount2++;
                            }
                        }
                        if (valCount2==2 && si1==si3 && si2==si4){
                            bool doneSomething = false;
                            for (int valIndex3=0; valIndex3<ROW_COL_SEC_SIZE; valIndex3++){
                                if (valIndex3 != valIndex && valIndex3 != valIndex2){
                                    int position1 = sectionToCell(section,si1);
                                    int position2 = sectionToCell(section,si2);
                                    int valPos1 = getPossibilityIndex(valIndex3,position1);
                                    int valPos2 = getPossibilityIndex(valIndex3,position2);
                                    if (possibilities[valPos1] == 0){
                                        possibilities[valPos1] = round;
                                        doneSomething = true;
                                    }
                                    if (possibilities[valPos2] == 0){
                                        possibilities[valPos2] = round;
                                        doneSomething = true;
                                    }
                                }
                            }
                            if (doneSomething){
                                if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_PAIR_SECTION, valIndex+1, sectionToCell(section,si1)));
                                return true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }

    bool SudokuBoard::hiddenPairInRow(int round){
        for (int row=0; row<ROW_COL_SEC_SIZE; row++){
            for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                int c1 = -1;
                int c2 = -1;
                int valCount = 0;
                for (int column=0; column<ROW_COL_SEC_SIZE; column++){
                    int position = rowColumnToCell(row,column);
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0){
                        if (c1 == -1 || c1 == column){
                            c1 = column;
                        } else if (c2 == -1 || c2 == column){
                            c2 = column;
                        }
                        valCount++;
                    }
                }
                if (valCount==2){
                    for (int valIndex2=valIndex+1; valIndex2<ROW_COL_SEC_SIZE; valIndex2++){
                        int c3 = -1;
                        int c4 = -1;
                        int valCount2 = 0;
                        for (int column=0; column<ROW_COL_SEC_SIZE; column++){
                            int position = rowColumnToCell(row,column);
                            int valPos = getPossibilityIndex(valIndex2,position);
                            if (possibilities[valPos] == 0){
                                if (c3 == -1 || c3 == column){
                                    c3 = column;
                                } else if (c4 == -1 || c4 == column){
                                    c4 = column;
                                }
                                valCount2++;
                            }
                        }
                        if (valCount2==2 && c1==c3 && c2==c4){
                            bool doneSomething = false;
                            for (int valIndex3=0; valIndex3<ROW_COL_SEC_SIZE; valIndex3++){
                                if (valIndex3 != valIndex && valIndex3 != valIndex2){
                                    int position1 = rowColumnToCell(row,c1);
                                    int position2 = rowColumnToCell(row,c2);
                                    int valPos1 = getPossibilityIndex(valIndex3,position1);
                                    int valPos2 = getPossibilityIndex(valIndex3,position2);
                                    if (possibilities[valPos1] == 0){
                                        possibilities[valPos1] = round;
                                        doneSomething = true;
                                    }
                                    if (possibilities[valPos2] == 0){
                                        possibilities[valPos2] = round;
                                        doneSomething = true;
                                    }
                                }
                            }
                            if (doneSomething){
                                if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_PAIR_ROW, valIndex+1, rowColumnToCell(row,c1)));
                                return true;
                            }
                        }
                    }
                }
            }
        }
        return false;
    }

    bool SudokuBoard::handleNakedPairs(int round){
        for (int position=0; position<BOARD_SIZE; position++){
            int possibilities = countPossibilities(position);
            if (possibilities == 2){
                int row = cellToRow(position);
                int column = cellToColumn(position);
                int section = cellToSectionStartCell(position);
                for (int position2=position; position2<BOARD_SIZE; position2++){
                    if (position != position2){
                        int possibilities2 = countPossibilities(position2);
                        if (possibilities2 == 2 && arePossibilitiesSame(position, position2)){
                            if (row == cellToRow(position2)){
                                bool doneSomething = false;
                                for (int column2=0; column2<ROW_COL_SEC_SIZE; column2++){
                                    int position3 = rowColumnToCell(row,column2);
                                    if (position3 != position && position3 != position2 && removePossibilitiesInOneFromTwo(position, position3, round)){
                                        doneSomething = true;
                                    }
                                }
                                if (doneSomething){
                                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::NAKED_PAIR_ROW, 0, position));
                                    return true;
                                }
                            }
                            if (column == cellToColumn(position2)){
                                bool doneSomething = false;
                                for (int row2=0; row2<ROW_COL_SEC_SIZE; row2++){
                                    int position3 = rowColumnToCell(row2,column);
                                    if (position3 != position && position3 != position2 && removePossibilitiesInOneFromTwo(position, position3, round)){
                                        doneSomething = true;
                                    }
                                }
                                if (doneSomething){
                                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::NAKED_PAIR_COLUMN, 0, position));
                                    return true;
                                }
                            }
                            if (section == cellToSectionStartCell(position2)){
                                bool doneSomething = false;
                                int secStart = cellToSectionStartCell(position);
                                {for (int i=0; i<GRID_SIZE; i++){
                                    for (int j=0; j<GRID_SIZE; j++){
                                        int position3=secStart+i+(ROW_COL_SEC_SIZE*j);
                                        if (position3 != position && position3 != position2 && removePossibilitiesInOneFromTwo(position, position3, round)){
                                            doneSomething = true;
                                        }
                                    }
                                }}
                                if (doneSomething){
                                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::NAKED_PAIR_SECTION, 0, position));
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
        return false;
    }

    /**
     * Mark exactly one cell which is the only possible value for some row, if
     * such a cell exists.
     * This method will look in a row for a possibility that is only listed
     * for one cell.  This type of cell is often called a "hidden single"
     */
    bool SudokuBoard::onlyValueInRow(int round){
        for (int row=0; row<ROW_COL_SEC_SIZE; row++){
            for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                int count = 0;
                int lastPosition = 0;
                for (int col=0; col<ROW_COL_SEC_SIZE; col++){
                    int position = (row*ROW_COL_SEC_SIZE)+col;
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0){
                        count++;
                        lastPosition = position;
                    }
                }
                if (count == 1){
                    int value = valIndex+1;
                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_SINGLE_ROW, value, lastPosition));
                    mark(lastPosition, round, value);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Mark exactly one cell which is the only possible value for some column, if
     * such a cell exists.
     * This method will look in a column for a possibility that is only listed
     * for one cell.  This type of cell is often called a "hidden single"
     */
    bool SudokuBoard::onlyValueInColumn(int round){
        for (int col=0; col<ROW_COL_SEC_SIZE; col++){
            for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                int count = 0;
                int lastPosition = 0;
                for (int row=0; row<ROW_COL_SEC_SIZE; row++){
                    int position = rowColumnToCell(row,col);
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0){
                        count++;
                        lastPosition = position;
                    }
                }
                if (count == 1){
                    int value = valIndex+1;
                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_SINGLE_COLUMN, value, lastPosition));
                    mark(lastPosition, round, value);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Mark exactly one cell which is the only possible value for some section, if
     * such a cell exists.
     * This method will look in a section for a possibility that is only listed
     * for one cell.  This type of cell is often called a "hidden single"
     */
    bool SudokuBoard::onlyValueInSection(int round){
        for (int sec=0; sec<ROW_COL_SEC_SIZE; sec++){
            int secPos = sectionToFirstCell(sec);
            for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                int count = 0;
                int lastPosition = 0;
                {for (int i=0; i<GRID_SIZE; i++){
                    for (int j=0; j<GRID_SIZE; j++){
                        int position = secPos + i + ROW_COL_SEC_SIZE*j;
                        int valPos = getPossibilityIndex(valIndex,position);
                        if (possibilities[valPos] == 0){
                            count++;
                            lastPosition = position;
                        }
                    }
                }}
                if (count == 1){
                    int value = valIndex+1;
                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::HIDDEN_SINGLE_SECTION, value, lastPosition));
                    mark(lastPosition, round, value);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Mark exactly one cell that has a single possibility, if such a cell exists.
     * This method will look for a cell that has only one possibility.  This type
     * of cell is often called a "single"
     */
    bool SudokuBoard::onlyPossibilityForCell(int round){
        for (int position=0; position<BOARD_SIZE; position++){
            if (solution[position] == 0){
                int count = 0;
                int lastValue = 0;
                for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
                    int valPos = getPossibilityIndex(valIndex,position);
                    if (possibilities[valPos] == 0){
                        count++;
                        lastValue=valIndex+1;
                    }
                }
                if (count == 1){
                    mark(position, round, lastValue);
                    if (logHistory || recordHistory) addHistoryItem(new LogItem(round, LogItem::SINGLE, lastValue, position));
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Mark the given value at the given position.  Go through
     * the row, column, and section for the position and remove
     * the value from the possibilities.
     *
     * @param position Position into the board (0-80)
     * @param round Round to mark for rollback purposes
     * @param value The value to go in the square at the given position
     */
    void SudokuBoard::mark(int position, int round, int value){
        if (solution[position] != 0) throw ("Marking position that already has been marked.");
        if (solutionRound[position] !=0) throw ("Marking position that was marked another round.");
        int valIndex = value-1;
        solution[position] = value;

        int possInd = getPossibilityIndex(valIndex,position);
        if (possibilities[possInd] != 0) throw ("Marking impossible position.");

        // Take this value out of the possibilities for everything in the row
        solutionRound[position] = round;
        int rowStart = cellToRow(position)*ROW_COL_SEC_SIZE;
        for (int col=0; col<ROW_COL_SEC_SIZE; col++){
            int rowVal=rowStart+col;
            int valPos = getPossibilityIndex(valIndex,rowVal);
            //cout << "Row Start: " << rowStart << " Row Value: " << rowVal << " Value Position: " << valPos << endl;
            if (possibilities[valPos] == 0){
                possibilities[valPos] = round;
            }
        }

        // Take this value out of the possibilities for everything in the column
        int colStart = cellToColumn(position);
        {for (int i=0; i<ROW_COL_SEC_SIZE; i++){
            int colVal=colStart+(ROW_COL_SEC_SIZE*i);
            int valPos = getPossibilityIndex(valIndex,colVal);
            //cout << "Col Start: " << colStart << " Col Value: " << colVal << " Value Position: " << valPos << endl;
            if (possibilities[valPos] == 0){
                possibilities[valPos] = round;
            }
        }}

        // Take this value out of the possibilities for everything in section
        int secStart = cellToSectionStartCell(position);
        {for (int i=0; i<GRID_SIZE; i++){
            for (int j=0; j<GRID_SIZE; j++){
                int secVal=secStart+i+(ROW_COL_SEC_SIZE*j);
                int valPos = getPossibilityIndex(valIndex,secVal);
                //cout << "Sec Start: " << secStart << " Sec Value: " << secVal << " Value Position: " << valPos << endl;
                if (possibilities[valPos] == 0){
                    possibilities[valPos] = round;
                }
            }
        }}

        //This position itself is determined, it should have possibilities.
        {for (int valIndex=0; valIndex<ROW_COL_SEC_SIZE; valIndex++){
            int valPos = getPossibilityIndex(valIndex,position);
            if (possibilities[valPos] == 0){
                possibilities[valPos] = round;
            }
        }}
    }

    /**
     * print the given BOARD_SIZEd array of ints
     * as a sudoku puzzle.  Use print options from
     * member variables.
     */
    void SudokuBoard::print(int* sudoku){
        for(int i=0; i<BOARD_SIZE; i++){
            if (printStyle == READABLE){
                cout << " ";
            }
            if (sudoku[i]==0){
                cout << '.';
            } else {
                cout << sudoku[i];
            }
            if (i == BOARD_SIZE-1){
                if (printStyle == CSV){
                    cout << ",";
                } else {
                    cout << endl;
                }
                if (printStyle == READABLE || printStyle == COMPACT){
                    cout << endl;
                }
            } else if (i%ROW_COL_SEC_SIZE==ROW_COL_SEC_SIZE-1){
                if (printStyle == READABLE || printStyle == COMPACT){
                    cout << endl;
                }
                if (i%SEC_GROUP_SIZE==SEC_GROUP_SIZE-1){
                    if (printStyle == READABLE){
                        cout << "-------|-------|-------" << endl;
                    }
                }
            } else if (i%GRID_SIZE==GRID_SIZE-1){
                if (printStyle == READABLE){
                    cout << " |";
                }
            }
        }
    }

    /**
     * Print the sudoku puzzle.
     */
    void SudokuBoard::printPuzzle(){
        print(puzzle);
    }

    /**
     * Print the sudoku solution.
     */
    void SudokuBoard::printSolution(){
        print(solution);
    }

    SudokuBoard::~SudokuBoard(){
        clearPuzzle();
        delete[] puzzle;
        delete[] solution;
        delete[] possibilities;
        delete[] solutionRound;
        delete[] randomBoardArray;
        delete[] randomPossibilityArray;
        delete solveHistory;
        delete solveInstructions;
    }

    LogItem::LogItem(int r, LogType t){
        init(r,t,0,-1);
    }

    LogItem::LogItem(int r, LogType t, int v, int p){
        init(r,t,v,p);
    }

    void LogItem::init(int r, LogType t, int v, int p){
        round = r;
        type = t;
        value = v;
        position = p;
    }

    LogItem::~LogItem(){
    }

    int LogItem::getRound(){
        return round;
    }

    /**
     * Get the type of this log item.
     */
    LogItem::LogType LogItem::getType(){
        return type;
    }

    /**
     * Print the current log item.  The message used is
     * determined by the type of log item.
     */
    void LogItem::print(){
        cout << "Round: " << getRound() << " - ";
        switch(type){
            case GIVEN:{
                cout << "Mark given";
            } break;
            case ROLLBACK:{
                cout << "Roll back round";
            } break;
            case GUESS:{
                cout << "Mark guess (start round)";
            } break;
            case HIDDEN_SINGLE_ROW:{
                cout << "Mark single possibility for value in row";
            } break;
            case HIDDEN_SINGLE_COLUMN:{
                cout << "Mark single possibility for value in column";
            } break;
            case HIDDEN_SINGLE_SECTION:{
                cout << "Mark single possibility for value in section";
            } break;
            case SINGLE:{
                cout << "Mark only possibility for cell";
            } break;
            case NAKED_PAIR_ROW:{
                cout << "Remove possibilities for naked pair in row";
            } break;
            case NAKED_PAIR_COLUMN:{
                cout << "Remove possibilities for naked pair in column";
            } break;
            case NAKED_PAIR_SECTION:{
                cout << "Remove possibilities for naked pair in section";
            } break;
            case POINTING_PAIR_TRIPLE_ROW: {
                cout << "Remove possibilities for row because all values are in one section";
            } break;
            case POINTING_PAIR_TRIPLE_COLUMN: {
                cout << "Remove possibilities for column because all values are in one section";
            } break;
            case ROW_BOX: {
                cout << "Remove possibilities for section because all values are in one row";
            } break;
            case COLUMN_BOX: {
                cout << "Remove possibilities for section because all values are in one column";
            } break;
            case HIDDEN_PAIR_ROW: {
                cout << "Remove possibilities from hidden pair in row";
            } break;
            case HIDDEN_PAIR_COLUMN: {
                cout << "Remove possibilities from hidden pair in column";
            } break;
            case HIDDEN_PAIR_SECTION: {
                cout << "Remove possibilities from hidden pair in section";
            } break;
            default:{
                cout << "!!! Performed unknown optimization !!!";
            } break;
        }
        if (value > 0 || position > -1){
            cout << " (";
            bool printed = false;
            if (position > -1){
                if (printed) cout << " - ";
                cout << "Row: " << cellToRow(position)+1 << " - Column: " << cellToColumn(position)+1;
                printed = true;
            }
            if (value > 0){
                if (printed) cout << " - ";
                cout << "Value: " << value;
                printed = true;
            }
            cout << ")";
        }
    }

    /**
     * Given a vector of LogItems, determine how many
     * log items in the vector are of the specified type.
     */
    int getLogCount(vector<LogItem*>* v, LogItem::LogType type){
        unsigned int count = 0;
        {for (unsigned int i=0; i<v->size(); i++){
            if(v->at(i)->getType() == type) count++;
        }}
        return count;
    }

    /**
     * Shuffle the values in an array of integers.
     */
    void shuffleArray(int* array, int size){
        {for (int i=0; i<size; i++){
            int tailSize = size-i;
            int randTailPos = rand()%tailSize+i;
            int temp = array[i];
            array[i] = array[randTailPos];
            array[randTailPos] = temp;
        }}
    }

    SudokuBoard::Symmetry getRandomSymmetry(){
        switch (rand()%4){
            case 0: return SudokuBoard::ROTATE90;
            case 1: return SudokuBoard::ROTATE180;
            case 2: return SudokuBoard::MIRROR;
            case 3: return SudokuBoard::FLIP;
        }
        return SudokuBoard::ROTATE90; // NOTE: default action
    }

    /**
     * Given the index of a cell (0-80) calculate
     * the column (0-8) in which that cell resides.
     */
    static inline int cellToColumn(int cell){
        return cell%ROW_COL_SEC_SIZE;
    }

    /**
     * Given the index of a cell (0-80) calculate
     * the row (0-8) in which it resides.
     */
    static inline int cellToRow(int cell){
        return cell/ROW_COL_SEC_SIZE;
    }

    /**
     * Given the index of a cell (0-80) calculate
     * the section (0-8) in which it resides.
     */
    static inline int cellToSection(int cell){
        return (cell/SEC_GROUP_SIZE*GRID_SIZE)
                + (cellToColumn(cell)/GRID_SIZE);
    }

    /**
     * Given the index of a cell (0-80) calculate
     * the cell (0-80) that is the upper left start
     * cell of that section.
     */
    static inline int cellToSectionStartCell(int cell){
        return (cell/SEC_GROUP_SIZE*SEC_GROUP_SIZE)
                + (cellToColumn(cell)/GRID_SIZE*GRID_SIZE);
    }

    /**
     * Given a row (0-8) calculate the first cell (0-80)
     * of that row.
     */
    static inline int rowToFirstCell(int row){
        return ROW_COL_SEC_SIZE*row;
    }

    /**
     * Given a column (0-8) calculate the first cell (0-80)
     * of that column.
     */
    static inline int columnToFirstCell(int column){
        return column;
    }

    /**
     * Given a section (0-8) calculate the first cell (0-80)
     * of that section.
     */
    static inline int sectionToFirstCell(int section){
        return (section%GRID_SIZE*GRID_SIZE)
                + (section/GRID_SIZE*SEC_GROUP_SIZE);
    }

    /**
     * Given a value for a cell (0-8) and a cell (0-80)
     * calculate the offset into the possibility array (0-728).
     */
    static inline int getPossibilityIndex(int valueIndex, int cell){
        return valueIndex+(ROW_COL_SEC_SIZE*cell);
    }

    /**
     * Given a row (0-8) and a column (0-8) calculate the
     * cell (0-80).
     */
    static inline int rowColumnToCell(int row, int column){
        return (row*ROW_COL_SEC_SIZE)+column;
    }

    /**
     * Given a section (0-8) and an offset into that section (0-8)
     * calculate the cell (0-80)
     */
    static inline int sectionToCell(int section, int offset){
        return sectionToFirstCell(section)
                + ((offset/GRID_SIZE)*ROW_COL_SEC_SIZE)
                + (offset%GRID_SIZE);
    }
}