Simple Sudoku solver. #cpp #cli

sudoku.cpp

//
// The MIT License (MIT)
//
// Copyright (c) 2013 Max Truxa
//
// Permission is hereby granted, free of charge, to any person obtaining a copy of
// this software and associated documentation files (the "Software"), to deal in
// the Software without restriction, including without limitation the rights to
// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
// the Software, and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//

// TODO:
//   - There is a bug somewhere. See "evil" test puzzle in `main`.
//   - Replace bool[][] `Sudoku::possibilities` with bit map.

#include <iostream>
#include <string>
#include <assert.h>


class Exception
{
public:
    Exception() { }
};

class NotInitializedException : Exception
{
public:
    NotInitializedException() { }
};

class InvalidLengthException : Exception
{
public:
    InvalidLengthException() { }
};

class BadCharacterException : Exception
{
public:
    BadCharacterException() { }
};

class BadLogicException : Exception
{
public:
    BadLogicException() { }
};

class SolverStuckException : Exception
{
public:
    SolverStuckException() { }
};

class Sudoku
{
    enum InternalErrorCode
    {
        NO_ERROR,
        ERROR_SOLVER_ALREADY_DONE,
        ERROR_SOLVER_STUCK
    };
public:
    Sudoku() : initialized(false) { }
    
    Sudoku(std::string const& str) : initialized(true)
    {
        // Check length
        if(str.length() != 81)
            throw InvalidLengthException();
        // Check used characters
        for(int i = 0; i < 81; i++)
        {
            if(str[i] < '0' || str[i] > '9')
                throw BadCharacterException();
        }
        // Check logic
        for(int row = 0; row < 9; row++)
        {
            for(int col = 0; col < 9; col++)
            {
                // Horizontal
                for(int colcheck = col + 1; colcheck < 9; colcheck++)
                {
                    if(str[row * 9 + colcheck] == '0')
                        continue;
                    if(str[row * 9 + col] == str[row * 9 + colcheck])
                        throw BadLogicException();
                }
                // Vertical
                for(int rowcheck = row + 1; rowcheck < 9; rowcheck++)
                {
                    if(str[rowcheck * 9 + col] == '0')
                        continue;
                    if(str[row * 9 + col] == str[rowcheck * 9 + col])
                        throw BadLogicException();
                }
                // Group
                int grouprow = row - (row % 3);
                int groupcol = col - (col % 3);
                int startrow = ((col + 1) % 3 == 0) ? (row + 1) : (row);
                int startcol = ((col + 1) % 3 == 0) ? (col - 2) : (col + 1);
                for(int rowcheck = startrow; rowcheck < grouprow + 3; rowcheck++)
                {
                    for(int colcheck = startcol; colcheck < groupcol + 3; colcheck++)
                    {
                        if(str[rowcheck * 9 + colcheck] == '0')
                            continue;
                        if(str[row * 9 + col] == str[rowcheck * 9 + colcheck])
                            throw BadLogicException();
                    }
                    startcol = groupcol;
                }
            }
        }
        // Copy string to internal buffer
        for(int i = 0; i < 81; i++)
        {
            this->data[i] = str[i];
            this->dataApplied[i] = false;
            if(str[i] == '0')
            {
                for(int j = 0; j < 9; j++)
                    this->possibilities[i][j] = true;
            }
            else
            {
                for(int j = 0; j < 9; j++)
                    this->possibilities[i][j] = (j == str[i] - '1') ? (true) : (false);
            }
        }
    }
    
    std::string Get() const
    {
        if (!this->initialized)
            throw NotInitializedException();
        return std::string(this->data, this->data + sizeof(this->data));
    }
    
    // This function exists for debugging purposes only.
    void DumbPossibilities() const
    {
        if (!this->initialized)
            throw NotInitializedException();
        for(int row = 0; row < 9; row++)
        {
            for(int col = 0; col < 9; col++)
            {
                std::cout << "[" << row << ", " << col << "] ";
                for(int i = 0; i < 9; i++)
                {
                    if(this->possibilities[row * 9 + col][i])
                        std::cout << (char)(i + '1');
                    else
                        std::cout << '-';
                }
                std::cout << std::endl;
            }
        }
    }
    
    // ret:
    //  true  -> More to do
    //  false -> Solved
    bool SolveNextField()
    {
        if (!this->initialized)
            throw NotInitializedException();
        return this->_SolveNextField();
    }
    
    void SolveAllFields()
    {
        if (!this->initialized)
            throw NotInitializedException();
        while (this->_SolveNextField()) { }
    }
    
private:
    // ret:
    //  true  -> More to do
    //  false -> Solved
    bool _SolveNextField()
    {
        int res = this->_TryToSolveNextFieldFromPossibilities();
        if(res == NO_ERROR || res == ERROR_SOLVER_ALREADY_DONE)
            return (res == NO_ERROR);
        while(true)
        {
            int res2 = this->_TryToApplyDataToPossibilities();
            if(res2 == ERROR_SOLVER_STUCK && res == ERROR_SOLVER_STUCK)
                throw SolverStuckException();
            res = this->_TryToSolveNextFieldFromPossibilities();
            if(res == NO_ERROR) // Field solved
                return true;
        }
    }
    
    // ret:
    //  NO_ERROR
    //  ERROR_SOLVER_ALREADY_DONE
    //  ERROR_SOLVER_STUCK
    InternalErrorCode _TryToSolveNextFieldFromPossibilities()
    {
        bool emptyFieldFound = false;
        for(int row = 0; row < 9; row++)
        {
            for(int col = 0; col < 9; col++)
            {
                if(this->data[row * 9 + col] != '0')
                    continue;
                if(!emptyFieldFound)
                    emptyFieldFound = true;
                int possibilityCount = 0;
                char lastChecked = 'X';
                for(int i = 0; i < 9; i++)
                {
                    if(this->possibilities[row * 9 + col][i])
                    {
                        possibilityCount++;
                        if(possibilityCount == 2)
                            break;
                        lastChecked = i + '1';
                    }
                }
                if(possibilityCount == 1)
                {
                    this->data[row * 9 + col] = lastChecked;
                    return NO_ERROR;
                }
                assert(possibilityCount != 0);
                for(int i = 0; i < 9; i++)
                {
                    bool otherPossibilityFound = false;
                    // Horizontal
                    for(int colcheck = 0; colcheck < 9; colcheck++)
                    {
                        if(colcheck == col)
                            continue;
                        if(this->possibilities[row * 9 + colcheck][i])
                        {
                            otherPossibilityFound = true;
                            break;
                        }
                    }
                    if(!otherPossibilityFound)
                    {
                        this->data[row * 9 + col] = i + '1';
                        for(int j = 0; j < 9; j++)
                            this->possibilities[row * 9 + col][j] = (j == i) ? (true) : (false);
                        return NO_ERROR;
                    }
                    otherPossibilityFound = false;
                    // Vertical
                    for(int rowcheck = 0; rowcheck < 9; rowcheck++)
                    {
                        if(rowcheck == row)
                            continue;
                        if(this->possibilities[rowcheck * 9 + col][i])
                        {
                            otherPossibilityFound = true;
                            break;
                        }
                    }
                    if(!otherPossibilityFound)
                    {
                        this->data[row * 9 + col] = i + '1';
                        for(int j = 0; j < 9; j++)
                            this->possibilities[row * 9 + col][j] = (j == i) ? (true) : (false);
                        return NO_ERROR;
                    }
                    otherPossibilityFound = false;
                    // Group
                    int grouprow = row - (row % 3);
                    int groupcol = col - (col % 3);
                    for(int rowcheck = grouprow; rowcheck < grouprow + 3; rowcheck++)
                    {
                        for(int colcheck = groupcol; colcheck < groupcol + 3; colcheck++)
                        {
                            if(rowcheck == row && colcheck == col)
                                continue;
                            if(this->possibilities[rowcheck * 9 + colcheck][i])
                            {
                                otherPossibilityFound = true;
                                break;
                            }
                        }
                        if(otherPossibilityFound)
                            break;
                    }
                    if(!otherPossibilityFound)
                    {
                        this->data[row * 9 + col] = i + '1';
                        for(int j = 0; j < 9; j++)
                            this->possibilities[row * 9 + col][j] = (j == i) ? (true) : (false);
                        return NO_ERROR;
                    }
                }
            }
        }
        if(!emptyFieldFound)
            return ERROR_SOLVER_ALREADY_DONE;
        return ERROR_SOLVER_STUCK;
    }
    
    // ret:
    //  NO_ERROR
    //  ERROR_SOLVER_STUCK
    InternalErrorCode _TryToApplyDataToPossibilities()
    {
        for(int row = 0; row < 9; row++)
        {
            for(int col = 0; col < 9; col++)
            {
                if(this->data[row * 9 + col] == '0' || this->dataApplied[row * 9 + col])
                    continue;
                // Horizontal
                for(int colcheck = 0; colcheck < 9; colcheck++)
                {
                    if(colcheck == col)
                        continue;
                    this->possibilities[row * 9 + colcheck][this->data[row * 9 + col] - '1'] = false;
                }
                // Vertical
                for(int rowcheck = 0; rowcheck < 9; rowcheck++)
                {
                    if(rowcheck == row)
                        continue;
                    this->possibilities[rowcheck * 9 + col][this->data[row * 9 + col] - '1'] = false;
                }
                // Group
                int grouprow = row - (row % 3);
                int groupcol = col - (col % 3);
                for(int rowcheck = grouprow; rowcheck < grouprow + 3; rowcheck++)
                {
                    for(int colcheck = groupcol; colcheck < groupcol + 3; colcheck++)
                    {
                        if(rowcheck == row && colcheck == col)
                            continue;
                        this->possibilities[rowcheck * 9 + colcheck][this->data[row * 9 + col] - '1'] = false;
                    }
                }
                this->dataApplied[row * 9 + col] = true;
                return NO_ERROR;
            }
        }
        return ERROR_SOLVER_STUCK;
    }
    
    bool initialized;
    char data[81];
    bool dataApplied[81];
    bool possibilities[81][9];
};


void PrintSudoku(Sudoku const& sudoku)
{
    std::string data = sudoku.Get();
    for(int i = 0; i < 81; i++)
    {
        std::cout << (data[i] != '0' ? data[i] : ' ');
        if(i % 9 == 8)
            std::cout << std::endl;
        else if(i % 3 == 2)
            std::cout << "|";
        else
            std::cout << " ";
        if(i % 27 == 26 && i != 80)
            std::cout << "-----+-----+-----" << std::endl;
    }
}

int main(int argc, char const** argv)
{
    /* Easy */
    //std::string puzzle = "420000000001274000007100009064701350075403690019605780100007800000352400000000037";
    //std::string puzzle = "108600503970000012032981000090060000060203080000050030000839420310000058809004306";
    /* Intermediate */
    //std::string puzzle = "000041609000002500809005013560000400000000000004000061630500104002600000405370000";
    //std::string puzzle = "670000051230000809009400006050079000002000600000380090900001200403000075720000068";
    /* Hard */
    //std::string puzzle = "056301004000080009004005000170000300020000090008000076000900500800010000700403920";
    //std::string puzzle = "000000370070300900004000008140065000590403081000970043300000100002009050016000000";
    /* Evil */
    //std::string puzzle = "080004000002300056040270000000400009008020500200007000000058090910002300000700040"; // Doesn't work yet.

    if(argc < 2)
    {
        std::string exe = argv[0];
        size_t sep = exe.find_last_of("/\\");
        if (sep != std::string::npos)
            exe = exe.substr(sep + 1);
        std::cout << "Usage:" << std::endl;
        std::cout << "  " << exe << " PUZZLE" << std::endl;
        std::cout << "  where PUZZLE is a string consisting of 81 digits." << std::endl;
        return 1;
    }
    std::string puzzle = argv[1];

    Sudoku sudoku;
    try {
        sudoku = puzzle;
    } catch (InvalidLengthException const&) {
        std::cout << "Puzzle has invalid length (" << puzzle.length() << ", expected 81)." << std::endl;
        return 1;
    } catch (BadCharacterException const&) {
        std::cout << "Bad character in puzzle." << std::endl;
        return 1;
    } catch (BadLogicException const&) {
        std::cout << "Bad logic in puzzle." << std::endl;
        return 1;
    }
    
    try {
        do
        {
            PrintSudoku(sudoku);
            std::cout << std::endl;
        }
        while(sudoku.SolveNextField());
    } catch (SolverStuckException const&) {
        std::cout
            << "Solver got stuck, sorry." << std::endl
            << "Remaining possibilities:" << std::endl;
            sudoku.DumbPossibilities();
            std::cout << std::endl;
        return 1;
    }
    
    std::cout << "Success!" << std::endl;
    return 0;
}