2239번: 스도쿠 - Kotlin(백트래킹)

2239번: 스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

나의 풀이

이 문제는 우리가 평소에 풀던 스도쿠 문제를 코드로 구현하는 문제입니다. 우리가 스도쿠 문제를 풀 때는 기본적으로 한 자리에 해당하는 숫자는 하나인 경우가 많습니다. 하지만 이 문제에서 주어지는 스도쿠 문제는 해당하는 자리에 임의의 숫자를 넣고 진행해야 하는 경우가 많기 때문에 우리가 실제로 스도쿠를 풀듯이 접근하면 해결할 수 없습니다. 

 

그래서 이 문제는 재귀함수와 백트래킹을 사용해야 합니다. 재귀함수를 돌리면서 가능한 숫자를 전부 탐색하고 백트래킹으로 다른 가짓수도 탐색할 수 있게 합니다. 그리고 행, 열, 박스 모양를 체크해 숫자가 해당 자리에 들어갈 수 있으면 다음으로 이동합니다.

 

처음에 스도쿠에 빈 칸을 전부 하나의 list에 넣고 해당 리스트의 index가 리스트의 마지막에 도달하면 스도쿠 판을 출력하게 해 주었습니다. 가능한 경우의 수가 하나가 아니기에 exitProcess()를 사용해 가장 처음 출력을 한 다음엔 프로그램에 종료되게 해서 문제에서 주어진 "답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. " 조건을 만족했습니다.

 

import kotlin.system.exitProcess

val dx = arrayOf(0, 1, 0, -1)
val dy = arrayOf(1, 0, -1, 0)

lateinit var sudoku: Array<IntArray>
val blank = mutableListOf<Pair<Int, Int>>()

fun main() = with(System.`in`.bufferedReader()) {
    sudoku = Array(9) { readLine().toCharArray().map { it.toString().toInt() }.toIntArray() }

    for (i in 0 until 9) {
        for (j in 0 until 9) {
            if (sudoku[i][j] == 0) {
                blank.add(i to j)
            }
        }
    }

    recursion(0)
}

fun recursion(index: Int) {
    if (index == blank.size) {
        sudoku.forEach {
            println(it.joinToString(""))
        }
        exitProcess(0)
    }

    val x = blank[index].first
    val y = blank[index].second
    for (k in 1..9) {
        if (check(x, y, k)) {
            sudoku[x][y] = k
            recursion(index + 1)
            sudoku[x][y] = 0
        }
    }
}

fun check(x: Int, y: Int, target: Int): Boolean {
    if (!checkRow(x, y, target)) return false
    if (!checkColumn(x, y, target)) return false
    if (!checkBox(x, y, target)) return false

    return true
}

fun checkRow(x: Int, y: Int, target: Int): Boolean {
    for (i in 0 until 9) {
        if (sudoku[x][i] == target) return false
    }
    return true
}

fun checkColumn(x: Int, y: Int, target: Int): Boolean {
    for (i in 0 until 9) {
        if (sudoku[i][y] == target) return false
    }
    return true
}

fun checkBox(x: Int, y: Int, target: Int): Boolean {
    val tempX = x / 3 * 3
    val tempY = y / 3 * 3

    for (i in tempX until tempX + 3) {
        for (j in tempY until tempY + 3) {
            if (sudoku[i][j] == target) return false
        }
    }
    return true
}