My 6 ms C++ Solution Using Backtracking


  • 0
    W
    class Solution {
    private:
      struct Block {
        int row, column;
        bitset<9> eliminate;
        Block(int row, int column, bitset<9> eliminate) : row(row), column(column), eliminate(eliminate) {}
      };
    
      bool validate(vector<vector<char>>& checkMatrix, vector<int>& record, Block** minBlock) {
        int minPossible = INT_MAX;
    
        for (int row = 0; row != 9; row++) {
          for (int column = 0; column != 9; column++) {
            if (checkMatrix[row][column] != '.') {
              continue;
            }
            bitset<9> eliminate;
            for (int i = 0; i != 9; i++) {
              if (checkMatrix[i][column] != '.') {
                eliminate[checkMatrix[i][column] - '1'] = 1;
              }
              if (checkMatrix[row][i] != '.') {
                eliminate[checkMatrix[row][i] - '1'] = 1;
              }
              int innerRow = (row / 3) * 3 + (i / 3),
                innerColumn = (column / 3) * 3 + i % 3;
    
              if (checkMatrix[innerRow][innerColumn] != '.') {
                eliminate[checkMatrix[innerRow][innerColumn] - '1'] = 1;
              }
            }
            int choices = 0;
            for (int i = 0; i != 9; i++) {
              choices += eliminate[i] ? 0 : 1;
            }
            if (choices == 1) {
              for (int i = 0; i != 9; i++) {
                if (!eliminate[i]) {
                  checkMatrix[row][column] = '1' + i;
                  record.push_back(row * 9 + column);
                  *minBlock = NULL;
                  return validate(checkMatrix, record, minBlock);
                }
              }
            }
            else {
              if (choices == 0) {
                if (*minBlock) delete *minBlock;
                return false;
              }
              if (choices < minPossible){
                minPossible = choices;
                if (*minBlock) delete *minBlock;
                *minBlock = new Block(row, column, eliminate);
              }
            }
          }
        }
        return true;
      }
    
      void recover(vector<vector<char>>& checkMatrix, vector<int>& record) {
        for (vector<int>::iterator it = record.begin(); it != record.end(); it++) {
          checkMatrix[*it / 9][*it % 9] = '.';
        }
      }
    
      int getTestIndex(Block* block) {
        int i = 0;
        for (; i != 9; i++) {
          if (!block->eliminate[i]) {
            block->eliminate[i] = true;
            break;
          }
        }
        return i == 9 ? -1 : i;
      }
    
    public:
    
      void solveSudoku(vector<vector<char>>& board) {
        Block* block;
        vector<pair<Block*, vector<int>>> st;
        do {
          block = NULL;
          vector<int> record;
          if (validate(board, record, &block)){
            if (block == NULL)  {
              for (vector<pair<Block*, vector<int>>>::iterator it = st.begin(); it != st.end(); it++){
                delete it->first;
              }
              return;
            }
            st.push_back(make_pair(block, record));
            board[block->row][block->column] = '1' + getTestIndex(block);
          }
          else {
            recover(board, record);
            while (st.size()) {
              vector<pair<Block*, vector<int>>>::iterator last = --st.end();
              int index = getTestIndex(last->first);
              if (index == -1) {
                recover(board, last->second);
                board[last->first->row][last->first->column] = '.';
                delete last->first;
                st.pop_back();
              }
              else {
                board[last->first->row][last->first->column] = '1' + index;
                break;
              }
            }
            if (!st.size()) return;
          }
        } while (true);
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.