[LeetCode] 36. Valid Sudoku with java

Problem

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

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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.

Example 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

---

Solution

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            HashSet<Character> rows = new HashSet<Character>();
            HashSet<Character> colums = new HashSet<Character>();
            HashSet<Character> cube = new HashSet<Character>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && rows.add(board[i][j]) == false)
                    return false;
                if (board[j][i] != '.' && colums.add(board[j][i]) == false)
                    return false;
                int rowIndex = 3 * (i / 3);
                int colIndex = 3 * (i % 3);
                if (board[rowIndex + j / 3][colIndex + j % 3] != '.' && cube.add(board[rowIndex + j / 3][colIndex + j % 3]) == false)
                    return false;
            }
        } return true;
    }
}

Explanation

• 문제에서는 다음과 같은 조건을 제시하고 있다.

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

• 각 열에서, 각 행에서, 3 x 3 크기 박스 9개안에서의 같은 숫자의 중복을 금지하는데, 중복을 금지하는 것에서 자료구조 Set을 떠올릴 수 있다.
• 중복을 3곳에서 금지하기 때문에 Set을 3개를 선언한다.

  HashSet<Character> rows = new HashSet<Character>();
  HashSet<Character> colums = new HashSet<Character>();
  HashSet<Character> cube = new HashSet<Character>();
  

• 수도쿠를 나타내는 배열 board의 모든 요소를 각각 비교해야 하기 때문에, for 반복문을 2개 선언하여 포인터 2개를 활용한 비교를 할 수 있도록 한다.
• 이 때, 앞서 만들어둔 자료구조 Set은 각 열 및 각 행, 3 x 3 크기 박스 9개에서 초기화 되면서 진행되어야 하므로, 첫 번째 for 반복문속에 선언한다.

  for (int i = 0; i < 9; i++) {
    HashSet<Character> rows = new HashSet<Character>();
    HashSet<Character> colums = new HashSet<Character>();
    HashSet<Character> cube = new HashSet<Character>();
    for (int j = 0; j < 9; j++) {
    }
  }
  

• 각 열과 각 행의 중복을 검사하는 if 조건문을 작성한다.

  if (board[i][j] != '.' && rows.add(board[i][j]) == false)
    return false;
  if (board[j][i] != '.' && colums.add(board[j][i]) == false)
    return false;
  

• 3 x 3크기 박스 9개의 중복을 검사하기 위해, 포인터가 가리켜야 하는 인덱스는 다음과 같다.

  [0, 0] -> [0, 1] -> [0, 2] ->
  [1, 0] -> [1, 1] -> [1, 2] ->
  [2, 0] -> [2, 1] -> [2, 2] ->
  [0, 3] -> [0, 4] -> [0, 5] -> 
  ...
  

• 위와 같은 인덱스를 나타내기 위해 변수 rowIndex와 colIndex를 선언하고 if 조건문을 작성한다.

  int rowIndex = 3 * (i / 3);
  int colIndex = 3 * (i % 3);
  if (board[rowIndex + j / 3][colIndex + j % 3] != '.' && cube.add(board[rowIndex + j / 3][colIndex + j % 3]) == false)
    return false;
  

• for 반복문을 빠져나오면 유효한 수도쿠가 되므로 true를 반환하도록 한다.

  return true;