P169 判断数独的有效性

描述#

这个题目说的是，给你一个 9 x 9 的填充了一部分数字的数独，你要判断它是否有效。

注意，有效的数独不一定有解。你只需要判断已经填充的数字满足以下 3 条规则即可：

• 每一行只能包含数字 1-9，并且不能重复。
• 每一列只能包含数字 1-9，并且不能重复。
• 每个 3 x 3 的小正方形只能包含数字 1-9，并且不能重复。

其中，第三条中说的小正方形，指的是将 9 x 9 的大正方形平均分成 9 个 3 x 3 的小正方形。而不是指任意 3 x 3 的小正方形。代码中使用一个 9 x 9 的二维字符数组来表示数独，数组中只包含字符 1 到 9 和字符点号，点号表示这个位置没有填充数字。

代码#

public class AlgoCasts {

  public boolean isValidSudokuBruteForce(char[][] board) {
    Set<Character> set = new HashSet<>();
    for (int i = 0; i < 9; ++i) {
      set.clear();
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.') continue;
        if (!set.add(board[i][j])) return false;
      }
      set.clear();
      for (int j = 0; j < 9; ++j) {
        if (board[j][i] == '.') continue;
        if (!set.add(board[j][i])) return false;
      }
      set.clear();
      for (int j = 0; j < 9; ++j) {
        int r = 3*(i/3) + j/3, c = 3*(i%3) + j%3;
        if (board[r][c] == '.') continue;
        if (!set.add(board[r][c])) return false;
      }
    }
    return true;
  }

  public boolean isValidSudoku2DArray(char[][] board) {
    boolean[][] rowSeen = new boolean[9][9];
    boolean[][] colSeen = new boolean[9][9];
    boolean[][] boxSeen = new boolean[9][9];
    for (int i = 0; i < 9; ++i) {
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.') continue;
        int x = board[i][j] - '1';
        int k = (i/3) * 3 + j/3;
        if (rowSeen[i][x] || colSeen[j][x] || boxSeen[k][x])
          return false;
        rowSeen[i][x] = true;
        colSeen[j][x] = true;
        boxSeen[k][x] = true;
      }
    }
    return true;
  }

}