37 - Sudoku Solver

 JAVA

• class Solution {
      private boolean ok;
      private char[][] board;
      private List<Integer> t = new ArrayList<>();
      private boolean[][] row = new boolean[9][9];
      private boolean[][] col = new boolean[9][9];
      private boolean[][][] block = new boolean[3][3][9];
  
      public void solveSudoku(char[][] board) {
          this.board = board;
          for (int i = 0; i < 9; ++i) {
              for (int j = 0; j < 9; ++j) {
                  if (board[i][j] == '.') {
                      t.add(i * 9 + j);
                  } else {
                      int v = board[i][j] - '1';
                      row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                  }
              }
          }
          dfs(0);
      }
  
      private void dfs(int k) {
          if (k == t.size()) {
              ok = true;
              return;
          }
          int i = t.get(k) / 9, j = t.get(k) % 9;
          for (int v = 0; v < 9; ++v) {
              if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
                  row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                  board[i][j] = (char) (v + '1');
                  dfs(k + 1);
                  row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
              }
              if (ok) {
                  return;
              }
          }
      }
  }

C++

• using pii = pair<int, int>;
  
  class Solution {
  public:
      void solveSudoku(vector<vector<char>>& board) {
          bool row[9][9] = {false};
          bool col[9][9] = {false};
          bool block[3][3][9] = {false};
          bool ok = false;
          vector<pii> t;
          for (int i = 0; i < 9; ++i) {
              for (int j = 0; j < 9; ++j) {
                  if (board[i][j] == '.') {
                      t.push_back({i, j});
                  } else {
                      int v = board[i][j] - '1';
                      row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                  }
              }
          }
          function<void(int k)> dfs = [&](int k) {
              if (k == t.size()) {
                  ok = true;
                  return;
              }
              int i = t[k].first, j = t[k].second;
              for (int v = 0; v < 9; ++v) {
                  if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {
                      row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;
                      board[i][j] = v + '1';
                      dfs(k + 1);
                      row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;
                  }
                  if (ok) {
                      return;
                  }
              }
          };
          dfs(0);
      }
  };