36.valid-sudoku.md

36. Valid Sudoku

We will check if the number exists in the row and column first.

For the rule "Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.", we will break the 9x9 board into 3x3 board, so the index will divided by 3.

      0       1       2
    0 1 2 | 3 4 5 | 6 7 8
  0
0 1
  2     A

  3 
1 4           B
  5

  6
2 7                C 
  8

A: (2, 2) => (2/2, 2/3) = (0, 0)
B: (4, 4) => (4/3, 4/3) = (1, 1)
C: (7, 6) => (7/3, 6/3) = (2, 2)

fun isValidSudoku(board: Array<CharArray>): Boolean {
    val rows = Array<HashSet<Int>>(9) { hashSetOf<Int>() }
    val cols = Array<HashSet<Int>>(9) { hashSetOf<Int>() }
    // For rule 3, we store check the 3x2 board and use (x, y) as key
    val squares = HashMap<Pair<Int, Int>, HashSet<Int>>()

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            squares[i to j] = hashSetOf<Int>()
        }
    }
    for (r in 0 until 9) {
        for (c in 0 until 9) {
            if (board[r][c] != '.') {
                val v = board[r][c] - '1'
                if (rows[r].contains(v) || cols[c].contains(v) || squares[r / 3 to c / 3]!!.contains(v)) return false

                rows[r].add(v)
                cols[c].add(v)
                squares[r / 3 to c / 3]!!.add(v)
            }
        }
    }
    return true
}