class Solution {

 public:

     bool isValidSudoku(vector<vector<char> > &board) {

         int n;

         for (int i = ; i < ; ++i) {

             vector<bool> contained(, false);

             for (int j = ; j < ; ++j) {

                 if (board[i][j] == '.') continue;

                 n = board[i][j] - '' - ;

                 if (contained[n]) return false;

                 contained[n] = true;

             }

         }

         for (int i = ; i < ; ++i) {

             vector<bool> contained(, false);

             for (int j = ; j < ; ++j) {

                 if (board[j][i] == '.') continue;

                 n = board[j][i] - '' - ;

                 if (contained[n]) return false;

                 contained[n] = true;

             }

         }

         for (int i = ; i < ; ++i) {

             for (int j = ; j < ; ++j) {

                 vector<bool> contained(, false);

                 for (int k = ; k < ; ++k) {

                     for (int m = ; m < ; ++m) {

                         if (board[i*+k][j*+m] == '.') continue;

                         n = board[i*+k][j*+m] - '' - ;

                         if (contained[n]) return false;

                         contained[n] = true;

                     }

                 }

             }

         }

         return true;

     }

 };

 class Solution {

 public:

     void solveSudoku(vector<vector<char> > &board) {

         list<int> unsolved;

         getUnsolved(board, unsolved);

         recursive(board, unsolved);

     }

     bool recursive(vector<vector<char> > &board, list<int> &unsolved) {

         if (unsolved.empty()) return true;

         int loc = unsolved.front();

         int row = loc / ;

         int col = loc % ;

         vector<bool> contained(, false);

         int n;

         for (int i = ; i < ; ++i) {

             if (board[row][i] != '.') {

                 contained[board[row][i] - '' - ] = true;

             }

             if (board[i][col] != '.') {

                 contained[board[i][col] - '' - ] = true;

             }

         }

         row = row / ; col = col / ;

         for (int i = ; i < ; ++i) {

             for (int j = ; j < ; ++j) {

                 if (board[row *  + i][col *  + j] != '.') {

                     contained[board[row *  + i][col *  + j] - '' - ] = true;

                 }

             }

         }

         row = loc / ; col = loc % ;

         for (int i = ; i < ; ++i) {

             if (!contained[i]) {

                 board[row][col] = i +  + '';

                 unsolved.pop_front();

                 if (recursive(board, unsolved)) return true;

                 board[row][col] = '.';

                 unsolved.push_front(loc);

             }

         }

         return false;

     }

     void getUnsolved(vector<vector<char> > &board, list<int> &unsolved) {

         for (int i = ; i < ; i++) {

             for (int j = ; j < ; ++j) {

                 if (board[i][j] == '.') {

                     unsolved.push_back(i *  + j);

                 }

             }

         }

     }

 };