/*
 * Title: Assignment four (Sudoku Solver)
 * Author: Andrey Gavel
 * Function:
 * Input:
 * Output:
 *
 * Created on October 02, 2011, 12:53 PM
 * Last modified on October 08, 2011, 12:53 PM, by Andrey Gavel
 * Copyright Andrey Gavel 2011
 */

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void set_cell_contents(vector<short>&, short);
string get_cell_char(vector<short>);
bool try_read_file(string, string&);
bool is_single_digit(char);
string cells_to_str(vector<short>[9][9]);
static int vector_contains_short(vector<short>, short);
static bool vector_remove_short(vector<short>&, short);
static bool vector_remove_cell(vector<vector<short>>&, vector<short>);
static vector<short> vector_remove_shorts(vector<short>, vector<short>);
static vector<vector<short>> vector_remove_cells(vector<vector<short>>, vector<short>);
bool ReadData(vector<short>[9][9]);
void PrintData(vector<short>[9][9]);
bool CheckColumn(vector<short>[9][9], int, int);
bool CheckRow(vector<short>[9][9], int, int);
bool CheckSubSquare(vector<short>[9][9], int, int);
void SolvePuzzle(vector<short>[9][9]);

int main(int argc, char** argv)
{
    int i, j;
    vector<short> oCells[9][9];
    for (i = 0; i < 9; ++i) //for each row
    {
        for (j = 0; j < 9; j++) //set each cell to "0" content
        {
            set_cell_contents(oCells[i][j], 0);
        }
    }
    if (ReadData(oCells))
    {
        SolvePuzzle(oCells);
        PrintData(oCells);
    }
    else
    {
        cout << "Could not open the file!" << endl;
    }
    system("PAUSE");

    return 0;
}

void set_cell_contents(vector<short>& oVector, short iValue)
{
    if (iValue < 1 || iValue > 9)
    {
        for (int i = 1; i < 10; i++)
        {
            oVector.push_back(i);
        }
    }
    else
    {
        oVector.push_back(iValue);
    }
}

string get_cell_char(vector<short> oValues)
{
    string sOut = "0";
    if (oValues.size() == 1)
    {
        char oChar[2];
        sOut = itoa(oValues[0], oChar, 10);
        sOut = sOut;
    }
    return sOut;
}

bool try_read_file(string sFileName, string &sContent) //function used for testing on Windows 7; now obsolete
{
    int iLength;
    char * oBuffer;

    ifstream is;
    is.open(sFileName, ios::binary);

    //get length of file
    is.seekg (0, ios::end);
    iLength = is.tellg();

    if (iLength < 0)
    {
        delete[] oBuffer;
        return false;
    }
    else if (iLength == 0)
    {
        sContent = "";
        delete[] oBuffer;
        return true;
    }

    is.seekg (0, ios::beg);

    //allocate memory
    oBuffer = new char[iLength];

    //read data as a block
    is.read(oBuffer, iLength);
    is.close();

    sContent = oBuffer;

    delete[] oBuffer;

    return true;
}

bool is_single_digit(char oChar)
{
    return (oChar >= '0' && oChar <= '9');
}

string cells_to_str(vector<short> oCells[9][9])
{
    string sOut = "";
    int i, j;
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            sOut += get_cell_char(oCells[i][j]);
            if (j + 1 < 9)
            {
                sOut += " ";
            }
        }
        sOut += "\n";
    }
    return sOut;
}

static int vector_contains_short(vector<short> iInput, short iValue)
{
    for (int i = 0; i < iInput.size(); i++)
    {
        if (iInput[i] == iValue)
        {
            return i;
        }
    }
    return -1;
}

static bool vector_remove_short(vector<short>& oVector, short iValue)
{
    for (int i = 0; i < oVector.size(); i++)
    {
        if (oVector[i] == iValue)
        {
            oVector.erase(oVector.begin() + i);
            return true;
        }
    }
    return false;
}

static bool vector_remove_cell(vector<vector<short>>& oVector, vector<short> oValue)
{
    for (int i = 0; i < oVector.size(); i++)
    {
        if (oVector[i] == oValue)
        {
            oVector.erase(oVector.begin() + i);
            return true;
        }
    }
    return false;
}

static vector<short> vector_remove_shorts(vector<short> iInput, vector<short> iPositions)
{
    vector<short> oOut;
    for (int i = 0; i < iInput.size(); i++)
    {
        if (vector_contains_short(iPositions, i) < 0)
        {
            oOut.push_back(iInput[i]);
        }
    }
    return oOut;
}

static vector<vector<short>> vector_remove_cells(vector<vector<short>> oInput, vector<short> iPositions)
{
    vector<vector<short>> oOut;
    for (int i = 0; i < oInput.size(); i++)
    {
        if (vector_contains_short(iPositions, i) < 0)
        {
            oOut.push_back(oInput[i]);
        }
    }
    return oOut;
}

bool ReadData(vector<short> oCells[9][9])
{
    string sInput;
    short iChar = 0;
    if (try_read_file("Project4_input2.in", sInput))
    {
        //remove all non-digit chars
        string sTmp = "";
        for (int i = 0; i < sInput.length(); i++)
        {
            if(is_single_digit(sInput[i]))
            {
                sTmp += sInput[i];
            }
        }
        sInput = sTmp;

        //build cells
        char * oChar = new char[1];
        for (int i = 0; i < 9; i++) //for each row
        {
            for (int j = 0; j < 9; j++) //for each column
            {
                oChar[0] = sInput[i * 9 + j]; //get corresponding char in string
                iChar = atoi(oChar); //convert char to int
                if (iChar > 0) //if cell content isn't zero, set new content
                {
                    oCells[i][j].clear();
                    oCells[i][j].push_back(iChar);
                }
            }
        }

        delete [] oChar;

        return true;
    }
    return false;
}

void PrintData(vector<short> oCells[9][9])
{
    cout << cells_to_str(oCells).c_str();
}

bool CheckColumn(vector<short> oCells[9][9], int iRow, int iCol)
{
    bool bRemovedPossible = false;
    for (int i = 0; i < 9; i++) //for each row in cell's column
    {
        if (i != iRow && oCells[i][iCol].size() == 1 && vector_remove_short(oCells[iRow][iCol], oCells[i][iCol][0])) //if cell has 1 possible value and we removed it from input cell
        {
            bRemovedPossible = true; //mark flag for "removed possible value"
        }
    }
    return bRemovedPossible;
}

bool CheckRow(vector<short> oCells[9][9], int iRow, int iCol)
{
    bool bRemovedPossible = false;
    for (int i = 0; i < 9; i++) //for each column in cell's row
    {
        if (i != iCol && oCells[iRow][i].size() == 1 && vector_remove_short(oCells[iRow][iCol], oCells[iRow][i][0])) //if cell has 1 possible value and we removed it from input cell
        {
            bRemovedPossible = true; //mark flag for "removed possible value"
        }
    }
    return bRemovedPossible;
}

bool CheckSubSquare(vector<short> oCells[9][9], int iRow, int iCol)
{
    int iSqrRow = floor((double)iRow / (double)3); //find corresponding square row
    int iSqrCol = floor((double)iCol / (double)3); //find corresponding square column
    bool bRemovedPossible = false;
    for (int i = iSqrRow * 3; i < iSqrRow * 3 + 3; i++) //for each row in cell's square
    {
        for (int j = iSqrCol * 3; j < iSqrCol * 3 + 3; j++) //for each column in cell's square
        {
            if (i != iRow && j != iCol && oCells[i][j].size() == 1 && vector_remove_short(oCells[iRow][iCol], oCells[i][j][0])) //if cell has 1 possible value and we removed it from input cell
            {
                bRemovedPossible = true; //mark flag for "removed possible value"
            }
        }
    }
    return bRemovedPossible;
}

void SolvePuzzle(vector<short> oCells[9][9])
{
    vector<vector<short>> oToSolve; //vector of cells that need solving
    vector<short> iToRemove; //reused vector of cell indeces, to remove from "oToSolve" later
    vector<short> iToSolveX; //keep track of what column each cell in "oToSolve" is in
    vector<short> iToSolveY; //keep track of what row each cell in "oToSolve" is in
    int iPos = -1;
    int i, j;

    //find all the cells that originally need to be solved
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            if (oCells[i][j].size() > 1)
            {
                iToSolveY.push_back(i);
                iToSolveX.push_back(j);
                oToSolve.push_back(oCells[i][j]);
            }
        }
    }

    //start the loop to solve cells
    for (i = 0; i < 100; i++) //run through 100 times? could improve stopping condition later
    {
        if (oToSolve.size() == 0) //if oToSolve is empty, return; we are done
        {
            return;
        }

        //check each cell's column for "possible values" to remove
        iToRemove.clear();
        for (j = 0; j < oToSolve.size(); j++)
        {
            if (CheckColumn(oCells, iToSolveY[j], iToSolveX[j]) && oCells[iToSolveY[j]][iToSolveX[j]].size() == 1) //if some value(s) were removed from cell and it now has only 1 possible value
            {
                iToRemove.push_back(j); //cell no longer needs to be solved; add it's position to oToRemove, to later remove from oToSolve
            }
        }

        oToSolve = vector_remove_cells(oToSolve, iToRemove);
        iToSolveY = vector_remove_shorts(iToSolveY, iToRemove);
        iToSolveX = vector_remove_shorts(iToSolveX, iToRemove);

        //check each cell's row for "possible values" to remove
        //same procedure as column check
        iToRemove.clear();
        for (j = 0; j < oToSolve.size(); j++)
        {
            if (CheckRow(oCells, iToSolveY[j], iToSolveX[j]) && oCells[iToSolveY[j]][iToSolveX[j]].size() == 1)
            {
                iToRemove.push_back(j);
            }
        }

        oToSolve = vector_remove_cells(oToSolve, iToRemove);
        iToSolveY = vector_remove_shorts(iToSolveY, iToRemove);
        iToSolveX = vector_remove_shorts(iToSolveX, iToRemove);

        //check each cell's square for "possible values" to remove
        //same procedure as column check
        iToRemove.clear();
        for (j = 0; j < oToSolve.size(); j++)
        {
            if (CheckSubSquare(oCells, iToSolveY[j], iToSolveX[j]) && oCells[iToSolveY[j]][iToSolveX[j]].size() == 1)
            {
                iToRemove.push_back(j);
            }
        }

        oToSolve = vector_remove_cells(oToSolve, iToRemove);
        iToSolveY = vector_remove_shorts(iToSolveY, iToRemove);
        iToSolveX = vector_remove_shorts(iToSolveX, iToRemove);
    }
}