题解 | #Sudoku#

Swift有限穷举+递归题解

import Foundation

struct Node {
    let i: Int
    let j: Int
}

var array = [[Int]]()
for _ in 0 ..< 9 {
    let rows = (readLine() ?? "").components(separatedBy: " ").map{ Int($0) ?? 0 }
    array.append(rows)
}
let initialArray = array
var tryCount = 0
while !fillValueInPlace(&array, &tryCount) {//递归
    tryCount += 1
    if tryCount > 100 {//如果尝试了100次还是不行，那就重新开始（有限穷举）
        array = initialArray
        tryCount = 0
    }
}
for sub in array {
    for (index, val) in sub.enumerated() {
        print("\(val)", terminator: index == 8 ? "\n" : " ")
    }
}

func fillValueInPlace(_ array: inout [[Int]], _ tryCount: inout Int) -> Bool {
    var nodes = [Node]()
    for i in 0 ..< 9 {
        for j in 0 ..< 9 {
            if array[i][j] == 0 {
                nodes.append(.init(i: i, j: j))
            }
        }
    }
    if nodes.count == 0 {
        return true
    }
    for node in nodes {
        var set = Set<Int>()
        let row = node.i
        let col = node.j
        let smallRow = row / 3 * 3
        let smallCol = col / 3 * 3
        for i in smallRow ..< (smallRow + 3) {
            for j in smallCol ..< (smallCol + 3) {
                set.insert(array[i][j])
            }
        }
        for i in 0 ..< 9 {
            set.insert(array[row][i])
            set.insert(array[i][col])
        }
        var excludes = Set<Int>()
        for i in 1...9 {
            if !set.contains(i) {
                excludes.insert(i)
            }
        }
        if excludes.count > 0 {
            if excludes.count == 1 {//唯一确定的值，直接填入
                array[row][col] = excludes.randomElement()!
            } else {
                if tryCount > 10 {//如果尝试了10次还是不行，就换一个
                    array[row][col] = excludes.randomElement()!
                    tryCount = 0
                }
            }
        }
    }
    return false
}