LeetCode Note Java 00036：Valid Sudoku

辨別輸入的數獨陣列是否有效，無須判斷能否有解答。

題目

Valid Sudoku Medium

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

解法

• 造出 9 + 9 + 9 個新 Array，再判斷這 27 個 Array 是否有重複的數字。
• 建立判斷 Array 是否有重複數字的方法。
• 最難想的是九宮格座標的判斷，腦袋不靈光的人 (如我) 最好多看幾次記住這規律。
  第一組 [i][j]
  00 00
  01 01
  02 02
  03 10
  04 11
  05 12
  06 20
  07 21
  08 22
  第九組 [i][j]
  80 66
  81 67
  82 68
  83 76
  84 77
  85 78
  86 86
  87 87
  88 88

最終會得出此公式：[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3]

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (char[] i : board) { // 判斷 board
          if (!isVaildArray(i)) {
            return false;
          }
        }
        char[][] board2 = new char[9][9];
        char[][] board3 = new char[9][9];
        for (int i = 0; i < 9; i++) {
          for (int j = 0; j < 9; j++) {
            board2[i][j] = board[j][i]; // fill board2
            board3[i][j] = board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3]; // fill board3
          }
        }
        for (int i = 0; i < 9; i++) {
          if (!isVaildArray(board2[i])) { // 判斷 board2
            return false;
          }
          if (!isVaildArray(board3[i])) { // 判斷 board3
            return false;
          }
        }
        return true;
    }
    private boolean isVaildArray(char[] array) {
      int[] ia = new int[9];
      for (int i = 0; i < 9; i++) {
        int value = array[i];
        if (value != '.') {
          ia[value - '1']++;
        }
      }
      for (int i : ia) {
        if (i > 1) {
          return false;
        }
      }
      return true;
    }
}

算是最笨的直觀解法。

參考資料

【LeetCode】36. Valid Sudoku 解题报告（Python）