Java solution using cache


  • 0
    B

    A similar solution to the top rated one, except that this uses cache to track whether a block/row/column has already a number.

    public class Solution {
    
      public void solveSudoku(char[][] board) {
        boolean[][][] blockCache = new boolean[3][3][9];
        boolean[][] rowCache = new boolean[9][9];
        boolean[][] columnCache = new boolean[9][9];
        for (int i = 0; i < 9; ++i) {
          for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
              int k = board[i][j] - '0';
              blockCache[i / 3][j / 3][k - 1] = true;
              rowCache[i][k - 1] = true;
              columnCache[j][k - 1] = true;
            }
          }
        }
        solveSudoku(board, blockCache, rowCache, columnCache);
      }
    
      public boolean solveSudoku(char[][] board, boolean[][][] blockCache, boolean[][] rowCache, boolean[][]
          columnCache) {
        for (int i = 0; i < 9; ++i) {
          for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
              for (int k = 0; k < 9; ++k) {
                if (!blockCache[i / 3][j / 3][k] && !rowCache[i][k] && !columnCache[j][k]) {
                  board[i][j] = (char) ((k + 1) + '0');
                  blockCache[i / 3][j / 3][k] = true;
                  rowCache[i][k] = true;
                  columnCache[j][k] = true;
                  if (solveSudoku(board, blockCache, rowCache, columnCache)) {
                    return true;
                  }
                  board[i][j] = '.';
                  blockCache[i / 3][j / 3][k] = false;
                  rowCache[i][k] = false;
                  columnCache[j][k] = false;
                }
              }
              return false;
            }
          }
        }
    
        return true;
      }
    

Log in to reply
 

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