Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9 grid with numbers in such a way that each column, each row, and each of the nine 3 × 3 sub-grids that compose the grid all contain all of the numbers from 1 to 9 one time.

Implement an algorithm that will check whether the given grid of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid does not have to be solvable.

Example

• For

  grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'],
          ['.', '.', '6', '.', '.', '.', '.', '.', '.'],
          ['.', '.', '.', '.', '.', '.', '.', '.', '.'],
          ['.', '.', '1', '.', '.', '.', '.', '.', '.'],
          ['.', '6', '7', '.', '.', '.', '.', '.', '9'],
          ['.', '.', '.', '.', '.', '.', '8', '1', '.'],
          ['.', '3', '.', '.', '.', '.', '.', '.', '6'],
          ['.', '.', '.', '.', '.', '7', '.', '.', '.'],
          ['.', '.', '.', '5', '.', '.', '.', '7', '.']]
  
  

  the output should be

  solution(grid) = true;

• For

  grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'],
          ['.', '.', '.', '.', '6', '.', '.', '.', '.'],
          ['7', '1', '.', '.', '7', '5', '.', '.', '.'],
          ['.', '7', '.', '.', '.', '.', '.', '.', '.'],
          ['.', '.', '.', '.', '8', '3', '.', '.', '.'],
          ['.', '.', '8', '.', '.', '7', '.', '6', '.'],
          ['.', '.', '.', '.', '.', '2', '.', '.', '.'],
          ['.', '1', '.', '2', '.', '.', '.', '.', '.'],
          ['.', '2', '.', '.', '3', '.', '.', '.', '.']]
  
  

  the output should be

  solution(grid) = false.

  The given grid is not correct because there are two **1**s in the second column. Each column, each row, and each 3 × 3 subgrid can only contain the numbers 1 through 9 one time.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.array.char grid

  A 9 × 9 array of characters, in which each character is either a digit from '1' to '9' or a period '.'.

• [output] boolean

  Return true if grid represents a valid Sudoku puzzle, otherwise return false.

풀이

boolean solution(char[][] grid) {
    for (int i = 0; i < grid.length; i ++) {
        HashMap <Character, Integer> map = new HashMap<>();
        
        // 행 확인
        for (int j = 0; j < grid[i].length; j ++) {
            char c = grid[i][j];
            
            if (c != '.') {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }
        
        // 한 행에 각 숫자는 1 개씩 존재
        for (char c : map.keySet()) {
            if (map.get(c) > 1) return false;
        }
        
        map.clear();
        
        // 열 확인
        for (int j = 0; j < grid[i].length; j ++) {
            char c = grid[j][i];
            
            if (c != '.') {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }
        
        // 한 열에 각 숫자는 1 개씩 존재
        for (char c : map.keySet()) {
            if (map.get(c) > 1) return false;
        }
        
        // 섹터 확인 (1, 4, 7) 행
        if (i % 3 == 1) {
            // 섹터 중심점 기준 순회 (1, 4, 7) 열
            for (int j = 1; j < grid[i].length; j += 3) {
                HashMap <Character, Integer> _map = new HashMap<>();
                
                // 중심점 기준 3 * 3 탐색
                // 정사각형 9개는 서로 다른 숫자가 존재해야 함
                for (int k = i - 1; k < i + 2; k ++) {
                    for (int l = j - 1; l < j + 2; l ++) {
                        char c = grid[k][l];
                        if (c != '.') _map.put(c, _map.getOrDefault(c, 0) + 1);
                    }
                }
                
                for (char c : _map.keySet()) {
                    if (_map.get(c) > 1) return false;
                }
            }
        }
    }
    
    return true;
}