[백준/코틀린] 9663번: N-Queen

링크

9663번: N-Queen

풀이

퀸을 배치하기 위해서는 다음 조건을 만족해야 합니다.

• 같은 행과 열에 다른 퀸이 없어야 합니다.
• 두 개의 대각선에 다른 퀸이 없어야 합니다.

즉, 하나의 행, 열, 대각선에는 하나의 퀸만 존재할 수 있습니다.

출처: Wikipedia: Eight Queens Puzzle

행, 열, 대각선의 방문 여부를 관리하며,
백트래킹으로 N개의 퀸을 체스판에 배치합니다.

코드

val n = readln().toInt()
val colVisited = BooleanArray(n)
val diagVisited1 = BooleanArray(2 * n)
val diagVisited2 = BooleanArray(2 * n)
var ans = 0

fun backtrack(m: Int) {
    if (n == m) return run { ans++ }

    for (j in 0 until n) {
        if (!colVisited[j] &&
            !diagVisited1[j + m] &&
            !diagVisited2[n + j - m]
        ) {
            colVisited[j] = true
            diagVisited1[j + m] = true
            diagVisited2[n + j - m] = true

            backtrack(m + 1)

            colVisited[j] = false
            diagVisited1[j + m] = false
            diagVisited2[n + j - m] = false
        }
    }
}

fun main() {
    backtrack(0)

    println(ans)
}