백준 2239번 스도쿠 - 스위프트(Swift) 풀이

1. 차례로 빈칸을 찾아 1-9중에 가능한 숫자를 전부 넣어본다.
2. 마지막 빈칸까지 다 채우면 전체 탐색을 종료한다.

---

1. 차례로 빈칸을 찾아 1-9중에 가능한 숫자를 전부 넣어본다.

 결국 모든 빈칸을 다 채워야 하므로, 빈칸을 채울 순서를 정한 뒤 차례로 빈칸을 채워보면 되는 백트래킹 문제이다. 빈칸에 들어갈 수 있는 숫자 1-9 중에, 채울 수 있는 숫자들로만 채워본다. (만약 같은 행 또는 열 또는 블록에 같은 숫자가 있으면 채울 수 없다.) 만약 해가 여러 개라면 사전식으로 앞서는 것을 출력해야 하므로, 작은 수인 1부터 9까지 차례로 넣어준다.

 해당 빈칸을 채웠으면, 다음 차례 칸을 채우는 함수를 또 재귀적으로 호출한다. 아래 코드에서는 각 칸에 row*9+col로 번호를 매겨 순서를 정했다.

 주의해야 할 것은, 만약 스도쿠 상태를 전역으로 선언해서 채워나가고 있다면, 현재 빈칸에 1-9를 다 넣어본 뒤에는 다시 빈칸(0) 상태로 돌려놓고 return을 해야 한다는 것이다. 만약 빈칸으로 돌려놓지 않으면 (탐색 상황을 트리로 나타냈을 때) 조상에서 해당 칸을 빈칸으로 인지하지 못하는 오류가 생긴다.

 

2. 마지막 빈칸까지 다 채우면 전체 탐색을 종료한다.

 만약 마지막 빈칸까지 다 채우면 스도쿠를 출력한다. 해가 여러 개라면 출력이 여러 번 될 수 있다. 따라서 이미 해를 찾은 적이 있는지를 저장해두었다가, 매 탐색 시작 전 해를 찾은 이력이 있으면 곧바로 return으로 탐색을 종료시키는 조건문을 두었다.

 

---

import Foundation

var findSolution = false
var state = [[Int]]()

func sudoku(index: Int) {
    if findSolution { return }
    
    for i in index..<81 {
        let row = i / 9
        let col = i % 9
        
        if state[row][col] == 0 {
            for n in 1...9 {
                if checkPossible(row: row, col: col, num: n, state: state) {
                    state[row][col] = n
                    sudoku(index: i+1)
                }
            }
            
            state[row][col] = 0
            return
        }
    }
    
    findSolution = true
    printSudoku()
}

func checkPossible(row: Int, col: Int, num: Int, state: [[Int]]) -> Bool {
    let blockRow = row / 3 * 3
    let blockCol = col / 3 * 3
    
    for i in 0..<9 {
        if state[row][i] == num { return false }            // 같은 행 검사
        if state[i][col] == num { return false }            // 같은 열 검사
        let dr = i / 3
        let dc = i % 3
        if state[blockRow+dr][blockCol+dc] == num { return false }    // 같은 블록 검사
    }
    
    return true
}

func printSudoku() {
    for i in 0..<9 {
        for j in 0..<9 {
            print(state[i][j], terminator: "")
        }
        print()
    }
}

func solution() {
    for _ in 0..<9 {
        state.append(readLine()!.map{ Int(String($0))! })
    }
    
    sudoku(index: 0)
}

solution()