#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <string>
#include <sstream>
using std::cout;
using std::ifstream;
using std::set;
using std::vector;
using std::string;
using std::stringstream;

int solution[81];

void remove_invalid_numbers_from_grid( vector< set<int> >& grid, int cell, int number ) {
   // Remove all other entries from this cell
   grid[cell].clear();
   grid[cell].insert( number );

   // Remove this number from cells in the same row
   for (int index=cell/9*9, end=index+9; index < end; ++index)
      if (index != cell)
         grid[index].erase( number );

   // Remove this number from cells in the same column
   for (int index=cell%9, row=0; row < 9; index += 9, ++row)
      if (index != cell)
         grid[index].erase( number );

   // Remove this number from neighbors in the containing "9 cell box"
   int top_row = cell / 9 / 3 * 3,   bottom_row = top_row + 3;
   int left_col = cell % 9 / 3 * 3,  right_col = left_col + 3;
   for (int i = top_row; i < bottom_row; ++i)
      for (int j = left_col; j < right_col; ++j)
         if (i*9+j != cell)
            grid[i*9+j].erase( number );
}

bool find_solution( vector< set<int> >& grid, int i ) {
   // The end has been reached, and a solution exists
   if (i == 80  &&  grid[80].size() > 0) {
      solution[80] = *(grid[80].begin());
      return true;

   // The current cell location has no number to try
   } else if (i == 80  ||  grid[i].size() == 0)
      return false;

   // Iterate through all possible numbers for this cell
   set<int>::iterator it = grid[i].begin();
   for ( ; it != grid[i].end(); ++it) {
      // Create a copy of the grid that can be thrown away at the end of this loop
      vector< set<int> > local( grid );
      // Change the copy of the grid to reflect the choice of this number
      remove_invalid_numbers_from_grid( local, i, *it );
      // Use recursion to go to the next cell in pursuit of the solution
      if (find_solution( local, i+1 )) {
         // A solution was found - remember this number, and unwind the recursion
         solution[i] = *it;
         return true;
   }  }

   // No solution was found after trying all possible numbers for this cell
   return false;
}
     
int main( void ) {
   vector< set<int> > grid(81);   // Use "set" because it's easy to "erase"
   ifstream ifs( "one.dat" );     // Use "vector" because it acts like an array
   string line;
   int arr[] = { 1,2,3,4,5,6,7,8,9 };
   copy( arr, arr+9, inserter( grid[0], grid[0].end() ) );   // Init row 0
   for (int i=1; i < 81; ++i)
      grid[i] = grid[0];                // Copy row 0 to the other 80 rows
   for (int i=0, number; i < 9; ++i) {
      getline( ifs, line );             // Read the puzzle's starting position
      cout << line << '\n';
      stringstream ss;
      ss << line;
      for (int j=0; j < 9; ++j) {
         ss >> number;                  // Tokenize the line just read
         if (number != 0)
            remove_invalid_numbers_from_grid( grid, i*9+j, number );
   }  }
   // Report the number of possible numbers for each cell
   cout << '\n';
   for (int i=0, col=0; i < 81; i += 1, col = (col+1) % 9)
      cout << grid[i].size() << (col < 8 ? ' ' : '\n');

   find_solution( grid, 0 );

   cout << '\n';
   for (int i=0, col=0; i < 81; i += 1, col = (col+1) % 9)
      cout << solution[i] << (col < 8 ? ' ' : '\n');
}

/************
7 0 0 5 1 0 0 0 0
5 0 0 8 0 9 0 0 0
4 6 1 0 0 0 0 0 0
0 0 0 0 9 0 0 8 2
0 1 0 0 0 0 0 4 0
2 4 0 0 3 0 0 0 0
0 0 0 0 0 0 1 7 3
0 0 0 3 0 7 0 0 9
0 0 0 0 8 5 0 0 6

1 4 4 1 1 4 6 4 2
1 2 2 1 4 1 5 4 3
1 1 1 2 2 2 6 4 3
2 3 4 4 1 3 4 1 1
4 1 6 3 4 3 5 1 2
1 1 5 3 1 3 4 4 3
3 4 6 4 3 3 1 1 1
3 3 5 1 3 1 4 2 1
3 4 5 4 1 1 2 1 1

7 9 8 5 1 6 2 3 4
5 3 2 8 4 9 7 6 1
4 6 1 2 7 3 5 9 8
3 5 7 4 9 1 6 8 2
8 1 9 6 5 2 3 4 7
2 4 6 7 3 8 9 1 5
6 8 5 9 2 4 1 7 3
1 2 4 3 6 7 8 5 9
9 7 3 1 8 5 4 2 6
************/