Dopcn's Blog

life and work

复合数据分层设计求数独解的例子

Posted at — Nov 13, 2015

由编程语言自带的数据结构种类有限,在解决实际问题中设计适和的复合数据类型更有利于程序的组织和迭代。复合数据的分层设计一般可以分为三层:最底层是复合数据的实现,上层是复合数据的使用方法,最上层是复合数据使用方法的应用。

在这个例子中,最底层使用数组作为数独数据的实现,在上层使用 struct 的初始化函数、subscript 中的 getter 和 setter,最后基于getter和setter实现数独求解的各个步骤。

enum SudokuError: ErrorType {
    case initDataError
    case invalidSudoku
    case subscriptOutOfRange
}

struct Sudoku: CustomStringConvertible {
    
    private var data = Array<Int>()
    
    init(array: Array<Int>) throws {
        guard array.count == 81 else { throw SudokuError.initDataError }
        data = array
    }
    
    func isRangeValid(row: Int, column: Int) -> Bool {
        return 0 <= row && row < 9 && 0 <= column && column < 9
    }
    
    subscript(row: Int, column: Int) -> Int {
        get {
            return data[row*9+column]
        }
        set {
            data[row*9+column] = newValue
        }
    }
    
    mutating func solve() throws {
        var emptyCells = Array<(Int, Int)>()
        for i in 0...8 {
            for j in 0...8 {
                if self[i, j] == 0 {
                    emptyCells.append((i, j))
                }
            }
        }
        
        var index = 0
        while index < emptyCells.count {
            let (a, b) = emptyCells[index]
            if self[a, b] < 9 {
                self[a, b]++
                if isSafe(a, y: b) {
                    index++
                }
            } else {
                self[a, b] = 0
                index--
            }
            if index < 0 { throw SudokuError.invalidSudoku }
        }
    }
    
    func isSafe(x: Int, y: Int) -> Bool {
        return isRowSafe(x, y: y) && isColumnSafe(x, y: y) && isCellSafe(x, y: y)
    }
    
    private func isRowSafe(x: Int, y: Int) -> Bool {
        for i in 0...8 {
            if i != y && self[x, y] == self[x, i] { return false }
        }
        return true
    }
    
    private func isColumnSafe(x: Int, y: Int) -> Bool {
        for i in 0...8 {
            if i != x && self[x, y] == self[i, y] { return false }
        }
        return true
    }
    
    private func isCellSafe(x: Int, y: Int) -> Bool {
        let a = x/3, b = y/3
        for i in 3*a...(3*a+2) {
            for j in 3*b...(3*b+2) {
                if i != x && j != y && self[x, y] == self[i, j] { return false }
            }
        }
        return true
    }
    
    var description: String {
        var output = ""
        for i in 0...8 {
            for j in 0...8 {
                output.appendContentsOf("\(self[i,j]) ")
                if j == 8 {output.appendContentsOf("\n")}
            }
        }
        return output
    }
}

do {
    let data = [0,9,0,4,2,0,0,7,0,
                0,4,0,0,0,7,0,0,2,
                0,0,7,0,0,0,1,0,6,
                7,0,0,0,0,2,0,0,0,
                0,0,0,6,0,5,0,0,0,
                0,0,0,3,0,0,0,0,4,
                4,0,1,0,0,0,5,0,0,
                9,0,0,2,0,0,0,1,0,
                0,6,0,0,3,9,0,2,0]
    var theSudoku = try Sudoku(array: data)
    try theSudoku.solve()
    print(theSudoku)
} catch SudokuError.initDataError {
    print("The count of init array isn't 81")
} catch SudokuError.invalidSudoku {
    print("This is not a valid sudoku")
}

对比以前写过的版本,这个实现多出了 subscript 中的 getter setter 方法,增加这两个方法隔离开了解数独的过程和实现数独数据的具体细节,假如要换一种数独的实现方式,只需要修改其中的构造函数和 subscript 其他函数例如 solve() 完全不需要改动,这就是复合数据抽象的好处。