Leetcode36.Valid Sudoku

소스코드

문제

• 36. Valid Sudoku

• 9*9 sudoku 가 유효한지 체크

• 각 row 는 1-9 중복이 없어야 한다

• 각 column 은 1-9 중복이 없어야 한다

• 3*3 sub box 는 1-9 중복이 없어야 한다

• sudoku 에서 채워진 셀은 rule 을 만족해서 유효해야 한다. 그러나 문제를 푸는데 필수적이지 않다?

풀이 (brute-force)

• 1~3 rule 을 적용
• 자세한건 소스에 주석

source

        fun isValidSudoku(board: Array<CharArray>): Boolean {
        val rowSize = board.size
        val colSize = board[0].size

        // rule 1
        for (row in 0 until rowSize) {
            val set = mutableSetOf<Char>()
            for (col in 0 until 9) {
                if (board[row][col] == '.') {
                    continue
                }

                val isNotDuplicate = set.add(board[row][col])
                if (!isNotDuplicate) {
                    return false
                }
            }
        }

        // rule 2
        for (row in 0 until colSize) {
            val set = mutableSetOf<Char>()
            for (col in 0 until 9) {
                if (board[col][row] == '.') {
                    continue
                }

                val isNotDuplicate = set.add(board[col][row])
                if (!isNotDuplicate) {
                    return false
                }
            }
        }

        // Rule 3: 각 3x3 서브박스에 중복된 숫자가 없는지 확인
        // 0, 3, 6 반복
        for (startRow in 0 until rowSize step 3) {
            for (startCol in 0 until colSize step 3) {
                if (!isValidateSubBox(board, startRow, startCol)) {
                    return false
                }
            }
        }
        return true
    }

    fun isValidateSubBox(board: Array<CharArray>, rowIndex: Int, colIndex: Int): Boolean {
        val set = mutableSetOf<Char>()
        for (row in rowIndex until rowIndex + 3) {
            for (col in colIndex until colIndex + 3) {
                if (board[row][col] == '.') {
                    continue
                }
                val isNotDuplicate = set.add(board[row][col])
                if (!isNotDuplicate) {
                    return false
                }
            }
        }
        return true
    }