#include <iostream>
#include <vector>
#include <fstream>
#include <assert.h>
#include <cmath>
#include <unordered_set>

using namespace std;

struct cell {

  cell(int row, int col, char c) {
    this->row = row;
    this->col = col;

    assert(c == '.' || (c >= '1' && c <= '9'));

    if(c == '.') {
      current_value = '.';
      possible_values = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    } else {
      current_value = c;
      possible_values = {c};
    }
  }

  bool isFree() {
    return current_value == '.';
  }

  void UpdatePossibleValues(const unordered_set<char> &set) {
    vector<char> new_values;
   
    for(int i = 0; i < possible_values.size(); i++) {
      char c = possible_values[i];
      auto it = set.find(c);
      if(it == set.end()) {
	new_values.push_back(c);
      }
    }
    
    possible_values = new_values;
  }

  void Commit(const char c) {
    current_value = c;
  }

  int row, col;
  char current_value;
  vector<char> possible_values;
};

typedef struct cell cell;

struct Grid {

  void LoadFromFile(string filename) {
    ifstream f;
    string line;
    int i;

    i = 0;    
    f.open(filename);
    while(f.is_open() && !f.eof()) {
      getline(f, line);
      
      if(!line.empty()) {
	lines.push_back(line);
	
	vector<cell> v;

	for(int j = 0; j < line.length(); j++) {
	  char c = line[j];
	  // construct cell object accordingly
	  assert(c == '.' || (c >= '1' && c <= '9'));
	  cell ce = cell(i, j, c);

	  v.push_back(ce);	  
	}

	cells.push_back(v);
      }
      
      i++;
    }
  }

  // returns the cells associated with c by being on the same row
  vector<cell> getRow(cell c) const {
    return cells[c.row];
  }

  // returns the cells associated with c by being on the same column
  vector<cell> getColumn(cell c) const {
    vector<cell> res;

    for(int i = 0; i < cells.size(); i++) {
      res.push_back(cells[i][c.col]);
    }
    
    return res;
  }

  // returns the cells associated with c by being on the same square
  vector<cell> getSquare(cell c) const {
    vector<cell> res;
    int s_row, s_col; 

    // compute coordinates of upper-left cell of the square
    s_row = floor(c.row/3) * 3;
    s_col = floor(c.col/3) * 3;

    for(int i = 0; i < 3; i++) {
      for(int j = 0; j < 3; j++) {
	res.push_back(cells[s_row + i][s_col + j]);
      }
    }

    return res;
  }

  void printGrid() {
    cout << "PRINTING BOARD:\n\n";

    for(int i = 0; i < cells.size(); i++) {
      cout << "\t";
      for(int j = 0; j < cells[i].size(); j++) {
	cout << cells[i][j].current_value;
      }
      cout << "\n";
    }

  }

  // 2-d vector of cells
  vector<vector<cell>> cells;
  vector<string> lines;
};


struct Solver {
  
  void solve(Grid grid) {
    vector<cell*> free_cells;
    cell *ce;
    
    // 1. find all available cells left to fill
    free_cells = GetFreeCells(grid);

    // 2. check if we are done
    if(free_cells.size() == 0) {
      cout << "We are DONE! \n";
      grid.printGrid();
      
      return;
    }

    // 3. update possible values
    UpdatePossibleValues(grid, free_cells);
  
    // 4. choose one among them
    ce = free_cells[0];

    // 5. recursively choose a value that has yet to be checked on
    //    that cell, commit that and solve the rest of the board.
    for(char c : ce->possible_values) {
      ce->Commit(c);
      solve(grid);
      
    }
  }

  void UpdatePossibleValues(const Grid &grid, vector<cell*> free_cells) {
    for(cell *ce : free_cells) {
      unordered_set<char> seen_values;
      
      for(cell r : grid.getRow(*ce)) {
	if(!r.isFree()) {
	  seen_values.insert(r.current_value);
	}
      }

      for(cell c : grid.getColumn(*ce)) {
	if(!c.isFree()) {
	  seen_values.insert(c.current_value);
	}
      }

      for(cell s : grid.getSquare(*ce)) {
	if(!s.isFree()) {
	  seen_values.insert(s.current_value);
	}
      }
      
      // update possible values for cell
      ce->UpdatePossibleValues(seen_values);
      
      seen_values.clear();
    }
  }

  // returns a vector of pointers to all cells that are currently free
  // in current grid.
  vector<cell*> GetFreeCells(Grid &grid) {
    vector<cell*> res;

    for(int i = 0; i < grid.cells.size(); i++) {
      for(int j = 0; j < grid.cells[i].size(); j++) {
	if(grid.cells[i][j].isFree()) {
	  res.push_back(&grid.cells[i][j]);
	}
      }
    }
    
    return res;
  }
  
};

int main() {
  Grid grid;
  grid.LoadFromFile("./grid.txt");
  grid.printGrid();
  
  Solver solver;
  solver.solve(grid);

  return 0;
}