[백준, BackTracking, Kotlin] P.2580 스도쿠

 

import java.util.*

var isComplete = false

class ZeroArea(
    var row: Int,
    var col: Int,
    var visited: Array<Boolean> = Array(9) { false }
)

val map = Array<Array<Int>>(9) {
    Array<Int>(9) {
        0
    }
}

fun main() {
    val scr = Scanner(System.`in`)
    val zeroAreas = mutableListOf<ZeroArea>()

    for (i in 0 until 9) {
        for (j in 0 until 9) {
            map[i][j] = scr.nextInt()

            if (map[i][j] == 0) {
                zeroAreas.add(ZeroArea(i, j))
            }
        }
    }

    for (zeroArea in zeroAreas) {
        checkRow(zeroArea)
        checkCol(zeroArea)
        checkSquare(zeroArea)
    }

    val zeroAreasSize = zeroAreas.size

    makeSudoku(zeroAreas, 0, zeroAreasSize)

    printlnResult()
}

fun printlnResult() {
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            print("${map[i][j]} ")
        }
        println()
    }
}

fun checkRow(element: ZeroArea) {
    for (i in 0..8) {
        if (map[i][element.col] != 0) {
            element.visited[map[i][element.col] - 1] = true
        }
    }
}

fun checkCol(element: ZeroArea) {
    for (i in 0..8) {
        if (map[element.row][i] != 0) {
            element.visited[map[element.row][i] - 1] = true
        }
    }
}

fun checkSquare(element: ZeroArea) {
    val r = if (element.row in 0..2) {
        0
    } else if (element.row in 3..5) {
        3
    } else if (element.row in 6..8) {
        6
    } else {
        -1
    }

    val c = if (element.col in 0..2) {
        0
    } else if (element.col in 3..5) {
        3
    } else if (element.col in 6..8) {
        6
    } else {
        -1
    }

    for (i in 0..2) {
        for (j in 0..2) {
            if (map[r + i][c + j] != 0) {
                element.visited[map[r + i][c + j] - 1] = true
            }
        }
    }
}

fun checkValidRow(element: ZeroArea, value: Int): Boolean {
    for (i in 0..8) {
        if (map[i][element.col] == value) {
            return false
        }
    }

    return true
}

fun checkValidCol(element: ZeroArea, value: Int): Boolean {
    for (i in 0..8) {
        if (map[element.row][i] == value) {
            return false
        }
    }

    return true
}

fun checkValidSquare(element: ZeroArea, value: Int): Boolean {
    val r = when (element.row) {
        in 0..2 -> {
            0
        }
        in 3..5 -> {
            3
        }
        in 6..8 -> {
            6
        }
        else -> {
            -1
        }
    }

    val c = when (element.col) {
        in 0..2 -> {
            0
        }
        in 3..5 -> {
            3
        }
        in 6..8 -> {
            6
        }
        else -> {
            -1
        }
    }

    for (i in 0..2) {
        for (j in 0..2) {
            if (map[r + i][c + j] == value) {
                return false
            }
        }
    }

    return true
}

fun makeSudoku(zeroAreas: MutableList<ZeroArea>, index: Int, zeroAreasSize: Int) {
    if (index >= zeroAreasSize) {
        isComplete = true
        return
    }

    val zeroArea = zeroAreas[index]

    for (i in 0..8) {
        if (!zeroArea.visited[i]) {
            if (checkValidCol(zeroArea, i + 1) && checkValidRow(zeroArea, i + 1) && checkValidSquare(zeroArea, i + 1)) {
                map[zeroArea.row][zeroArea.col] = i + 1
                makeSudoku(zeroAreas, index + 1, zeroAreasSize)
                if (isComplete) {
                    return
                } else {
                    map[zeroArea.row][zeroArea.col] = 0
                }
            }
        }
    }
}

1) 9 X 9의 2차원 배열에 스도쿠 값을 입력받으면서 0 값일 경우 zeroAreas라는 리스트에 빈 값에 대한 객체를 만들어 저장합니다.
2) zeroAreas를 순회하면서 행, 열, 3X3 영역을 체크하여 정답이 될 수 있는 값들을 추려냅니다.
3) 추려낸 값들을 기반으로 스도쿠를 만들어 나갑니다.

3-1) zeroAreas의 0번째 인덱스 부터 시작하며 인덱스가 zeroAreas의 크기와 같거나 크면 스도쿠를 완성한 것이므로
완성 상태를 알리기 위한 isComplete를 true로 업데이트 하고 리턴합니다.

3-2) 3-1를 충족하지 않을 경우, 
   <1> zeroArea의 값이 될 수 있는 visited를 순회하면서 아직 방문하지 않은(스도쿠 안의 내용을 채울 수 있는) index일 경우,
   행, 열, 3X3영역 체크를 통해 해당 위치에 해당 값이 스도쿠를 만들기에 적합한 값인지 검증합니다.

   <2> 적합한 값일 경우 map의 해당 위치에 값으로 업데이트를 하고 다음 인덱스로 makeSudoku를 재귀로 다시 진입합니다.

   <3> makeSudoku를 끝낸 후에 isComplete 상태 값을 확인하여 true일 경우, 스도쿠 완성이 된 것이므로 return으로 종료합니다. 
          false일 경우, 스도쿠 완성이 되지 않았으며 해당 값으로는 스도쿠를 완성할 수 없기에, <2>에서 수정한 map을 0값으로 되돌립니다.
          그 후, for문의 다음 i값으로 연산을 진행합니다.

위의 과정을 반복하면 원하는 스도쿠를 만들어 낼 수 있습니다.

10번 정도 틀리고 시행 착오를 겪으면서 풀었습니다... 그래도 이번에는 오랜만에 구글링의 도움을 받지 않고 풀었던것 같아

뿌듯합니다. 혹시 중간에 불필요한 연산이 있다면 알려주시면 감사하겠습니다.