#include <iostream>
/* 
  fstream is a header file that is used to read and write to a given file.
  It defines three types including ifstream, ofstream and fstream.
  ifstream is used to read from a given file, ofstream is used to write to a given file
  and fstream is used to both read and write to a given file.
  These types are inherited from the iostream types so any operators that can be used with 
  cin and cout (eg. >> and <<) can be used with the ifstream, ofstream and fstream types.
*/
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <stack>

using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::ifstream;
using std::ofstream;
using std::fstream;
using std::vector;
using std::stack;

/*
  This program solves a Sudoku puzzle using recursive backtracking
*/

class MissingValue {
  public:
    MissingValue() = default;
    MissingValue(int r, int c): row(r), col(c) { }
    
    int getRow();
    int getCol();
    int getNumPotSols();
    vector<int> getPotSols();
    void calcPotSols();
    void print();
    void setPotSols(vector<int> &list);
    void setNumPotSols(vector<int>::size_type value);
    
  private:
    int row;
    int col;
    vector<int> potenSols;
    int numPotSols;
};

void MissingValue::print() {
  cout << "missing value with row = " << row << " col = " << col << endl;
  if (potenSols.size() > 0) {
    cout << "potential solutions: ";
    for (int i = 0; i < potenSols.size(); ++i) cout << potenSols[i] << " ";
    cout << endl;
  }
  else {
    cout << "The potential solutions are empty!" << endl;
  }
}

int MissingValue::getRow() {
  return row;
}

int MissingValue::getCol() {
  return col;
}

int MissingValue::getNumPotSols() {
  return numPotSols;
}

vector<int> MissingValue::getPotSols() {
  return potenSols;
}

void MissingValue::setPotSols(vector<int> &list) {
  potenSols = list;
}

void MissingValue::setNumPotSols(vector<int>::size_type value) {
  numPotSols = value;
}

class Sudoku {
  public:
    Sudoku() = default;
    // set the data members of the object using the argument to the function
    void setPuzzle(int array2D[9][9]);
    // print the puzzle to the screen
    void printPuzzle();
    // get all the missing row and column positions in the puzzle
    void getMissingPos();
    // get all the potential solutions of each position in the puzzle
    bool getPotSol();
    
    // print the vector data members
    void printVectors();
    
    // set a single missing value in the puzzle and update the effected missing values in the same row, column or 3x3 grid
    bool setMissingValue(MissingValue &val);

    // solve the puzzle 
    void solve();
    
  private:
    int puzzle[9][9];
    int numMissingPos = 0;
    vector<MissingValue> missingVals;
};

bool Sudoku::setMissingValue(MissingValue &val) {
  bool potSolsExist;
  do{
    cout << "Filling position " << "(" << val.getRow() << ", " << val.getCol() << ") " << "with value " << val.getPotSols().back() << endl;
    // check how many potential solutions are there for the missing value, break the loop if there are zero 
    if (val.getPotSols().size() == 0) {
      break;
    }
    // fill in the specified position in the puzzle with the specified value
    puzzle[val.getRow()][val.getCol()] = val.getPotSols().back();
    // remove the last element in the potential solutions vector belonging to the missing value
    val.getPotSols().pop_back();
    // recalculate the potential solutions of all the remaining missing values in the puzzle
    potSolsExist = getPotSol();
    // print the current state of the puzzle
    cout << "puzzle state: " << endl;
    printPuzzle();
    // check if there are any missing values with zero potential solutions
  }
  while (!potSolsExist);
  return potSolsExist;
}

void Sudoku::solve() {
  // algorithms steps:
  // 1) select a missing number in the puzzle
  // 2) fill in the missing value using a number from the associated potential solutions
  // 3) recalculate the potential solutions of all missing values in the same row, column and 3x3 grid as the missing value that was just filled in
  // 4) ensure all of the updated missing values have at least one potential solution
  //    5) if 4) is not true then go back to 2) and select a different potential solution
  //    6) if 5) is not possible because all potential solutions are exhausted then go back to step 1) and select a different missing value
  //    7) if 6) is not possible because all remaining missing values are exhausted then pop the stack and go to step 1)
  //    8) if 7) is not possible then it means the puzzle doesn't have a solution!
  // 7) if 4) is true then push the missing value onto the stack
  // 8) go back to step 1) and continue until all missing values are filled in
  
  cout << endl;
  cout << endl;
  cout << "Start the solving process: " << endl;
  
  // create two vectors to hold the processed and unprocessed missing values
  vector<MissingValue> unproMissVals(missingVals);
  vector<MissingValue> proMissVals;
  
  
}

void Sudoku::setPuzzle(int array2D[9][9]) {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      puzzle[i][j] = array2D[i][j];
    }
  }
  return;
}

void Sudoku::printPuzzle() {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      cout << puzzle[i][j];
    }
    cout << endl;
  }
}

void Sudoku::getMissingPos() {
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      if (puzzle[i][j] == 0) {
        missingVals.push_back(MissingValue(i, j));
      }
    }
  }
  numMissingPos = missingVals.size();
}

bool Sudoku::getPotSol() {
  bool potSolsExist = true;
  for (int i = 0; i < numMissingPos; ++i) {
    // find the potential solutions by looking at the same row that the missing value is in
    vector<int> rowSols = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (int j = 0; j < 9; ++j) {
      if (puzzle[missingVals[i].getRow()][j] != 0) {
        int compareTo = puzzle[missingVals[i].getRow()][j];
        auto findIter = find_if(rowSols.cbegin(), rowSols.cend(), [compareTo] (const int &val) {return val == compareTo;});
        rowSols.erase(findIter);
      }
    }
    
    // find the potential solutions by looking at the same column that the missing value is in
    vector<int> colSols = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (int k = 0; k < 9; ++k) {
      if (puzzle[k][missingVals[i].getCol()] != 0) {
        int compareTo = puzzle[k][missingVals[i].getCol()];
        auto findIter = find_if(colSols.cbegin(), colSols.cend(), [compareTo] (const int &val) {return val == compareTo;});
        colSols.erase(findIter);
      }
    }
    
    // find the potential solutions by looking at the 3x3 square that the missing value is in
    vector<int> gridSols = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    // find the 3x3 grid that the missing value is located in 
    int gridRow = missingVals[i].getRow() / 3;
    int gridCol = missingVals[i].getCol() / 3;
    for (int m = 0; m < 3; ++m) {
      for (int n = 0; n < 3; ++n) {
        if (puzzle[3*gridRow + m][3*gridCol + n] != 0) {
          int compareTo = puzzle[3*gridRow + m][3*gridCol + n];
          auto findIter = find_if(gridSols.cbegin(), gridSols.cend(), [compareTo] (const int &val) {return val == compareTo;});
          gridSols.erase(findIter);
        }
      }
    }
    
    // the potential solution at the missing location are the values that are common to rowSols, colSols and gridSols
    // find the intersection of all three sequences 
    vector<int> tempSols(9, 0);         // temporary variable
    vector<int> potSols(9, 0);          // this vector will hold the final result of the potential solutions to the missing values in the puzzle
    // find the intersection between rowSols and colSols, store the result in tempSols
    set_intersection(rowSols.cbegin(), rowSols.cend(), colSols.cbegin(), colSols.cend(), tempSols.begin());                 // set_intersection finds the intersection of the first and second sequences and stores the result in the destination sequence, note that the destination sequence must be long enough to contain the result 
    // get rid of the remaining zeros after the intersection operation
    auto tempSolsIter = partition(tempSols.begin(), tempSols.end(), [] (const int &val) {return val != 0;});                
    tempSols.erase(tempSolsIter, tempSols.end());
    // find the intersection between tempSols and gridSols, store the result in potSols
    set_intersection(tempSols.cbegin(), tempSols.cend(), gridSols.cbegin(), gridSols.cend(), potSols.begin());
    // get rid of the remaining zeros after the intersection operation 
    auto potSolsIter = partition(potSols.begin(), potSols.end(), [] (const int &val) {return val != 0;});
    potSols.erase(potSolsIter, potSols.end());
    
    missingVals[i].setPotSols(potSols);
    missingVals[i].setNumPotSols(potSols.size());
    
    potSolsExist = potSolsExist && (potSols.size() > 0);
  }
  return potSolsExist;
}

void Sudoku::printVectors() {
  for (int i = 0; i < numMissingPos; ++i) {
    missingVals[i].print();
  }
}

int main() 
{
  string fileName = "single_sudoku.txt";
  /*
    When reading or writing to a file we need to create a file stream object.
    After defining the file stream object we need to associate it with a file.
    This can be done by either using the open function which is a member of each file stream class.
    Or by passing a file name as a string when creating the file stream. If a file name is given
    when creating the object it will automatically call the open function.
    Each stream has an associated file mode that represents how the file may be used.
  */
  //ifstream readStrm(fileName);           // creates a fstream and binds the file provided as argument to the stream, this also opens the file
  ifstream readStrm;                    // creates an unbound fstream
  cout << "File stream is ... ";
  if (readStrm.is_open()) {             // if_open() returns true if the file associated with the stream was successfully opened
    cout << "open." << endl;
  }
  else {
    cout << "closed." << endl;
  }
  readStrm.open(fileName);              // opens the file given as argument and binds the file to the fstream
  cout << "File stream is ... ";
  if (readStrm.is_open()) {
    cout << "open." << endl;
  }
  else {
    cout << "closed." << endl;
  }
  
  ofstream writeStrm;                               // create an unbound ofstream
  string fileName2 = "sudokuSolved.txt";            // filename of the output file
  writeStrm.open(fileName2);         // app is the file mode that specifies that the program must go to the end of the file before adding new content
  writeStrm << "Vedant" << endl;
  
  /*
    The IO library uses a machine independant IO type that it uses to convey information about 
    the state of the stream. This type is called iostate and it represents a collection of bits.
    The IO classes also define 4 constexpr of type iostate that represent particular bit patterns.
    The value of the constexpr's represent different conditions of the IO stream. 
    List of constexpr of type iostate:
      > badbit: value used to indicate that the stream is corrupted
      > failbit: value used to indicate that an IO operation failed
      > eofbit: value used to indicate the end of file
      > goodbit: value used to indicate that the stream is not in an error state, always 0
    The IO library also defines a set of functions to check the state of a stream.
      > good(): returns true is none of the other error bits are set
      > bad(), fail(), eof(): returns true if the corresponding bits are set
    The correct way to determine the overall state of a stream is to use the good() or fail() functions. 
  */
  
  string line;
  int lineNum = -1;
  int puzzle[9][9] = {0};
  while (readStrm.good()) {                   // check if the stream is valid and hasn't reached the end-of-file
    // the getline function requires an input stream and string as parameters
    // it reads the input stream upto and including the newline and stores what it read, excluding the newline, into the string argument
    getline(readStrm, line);
    ++lineNum;
    if (lineNum % 10 == 0) {                  // check for the "Grid ..." line in the textfile
      if (lineNum != 0) {
        // save the puzzle from the last 9 lines into a Sudoku object
        Sudoku s;
        s.setPuzzle(puzzle);                  // calling the function by value
        s.printPuzzle();
        s.getMissingPos();
        s.getPotSol();
        s.printVectors();
        s.solve();
      }
      cout << "Processing: ";
      cout << line << endl;
    }
    else {
      auto it = line.begin();                 // define an iterator for the string line
      for (int col = 0; col < 9; ++col) {
        // save the characters from the input stream into a 2D array called puzzle
        // since the input stream is a character, convert to an interger by subtracting by 48 because the character '0' is the 48th character is ASCII
        puzzle[(lineNum % 10) - 1][col] = int(*(it + col)) - 48;
      }
    }
  }
  return 0;
}