Number Place（数独）とSwift 3 （４）

もちろん、私たちは次に埋めるべき場所をランダムにもしくは順番に選んだりはしません。手間を節約するためにもっと工夫をします。１つの方法は、可能性が最も少ない場所を選択することです。

    func findPosition(table: [[Int]]) -> Position {
        var workPlaces   = [Place]()
        var sortedPlaces = [Place]()
        var position = Position()
        var place = Place()
            for cc in 0...8 {
                for rr in 0...8 {
                if table[rr][cc] == 0 {
                    position.row = rr
                    position.col = cc
                    place.position = position
                    place.val    = eval(position: position, table: table)
                    workPlaces.append(place)
                }
            }
        }
        sortedPlaces = workPlaces.sorted( by: { $0.val < $1.val } )
        place = sortedPlaces[0]
        position = place.position
        return position
    }

実際には、毎回全ての場所を再評価する必要はありません。直前の動きで影響を受ける場所だけを考慮すれば良いのです。

再帰的関数dropNumは、同じ問題に対して、今や139回しか呼ばれません。

struct Position {
    var row: Int = -1
    var col: Int = -1
}
struct Place {
    var position = Position()
    var val: Int = 0
}

class NumBoard {
    var table         = [[Int]]()
    var emptyPlaces   = [Place]()
    var sortedPlaces  = [Place]()
    var putPositions  = [Position]()
    var position      = Position()
    var place         = Place()
    var nplaces : Int = 0
    
    init() {
        table = [[7,0,3, 0,0,0, 0,0,0],
                 [0,5,1, 3,7,0, 4,0,0],
                 [6,0,0, 0,1,0, 0,2,0],
                 [0,0,4, 6,0,0, 0,0,0],
                 [0,0,0, 0,0,7, 0,8,0],
                 [5,0,0, 2,3,1, 9,0,0],
                 [3,0,0, 0,2,4, 0,9,1],
                 [0,0,0, 0,0,0, 8,4,0],
                 [0,0,7, 0,9,0, 2,0,0]]

        for rr in 0...8 {
            for cc in 0...8 {
                if table[rr][cc] == 0 {
                    nplaces += 1
                }
            }
        }
        myprint(table: table)
        print("nplaces = \(nplaces)")
    }
    
    func myprint(table: [[Int]]) {
        print("-----------------")
        for rr in 0...8 {
            for cc in 0...8 {
                if table[rr][cc] == 0 {
                    print(".", terminator: " ")
                } else {
                    print(table[rr][cc], terminator: " ")
                }
            }
            print("")
        }
        print("-----------------")
    }
    
    func eval(position: Position, table: [[Int]]) -> Int {
        var count = 0
        for num in 1...9 {
            if isSafeForNum(position: position, num: num) {
                count += 1
            }
        }
        return count
    }
    
    func isSafeForNum(position: Position, num: Int) -> Bool {
        for rr in 0...8 {
            if num == table[rr][position.col] { return false }
        }
        for cc in 0...8 {
            if num == table[position.row][cc] { return false }
        }
        let rowBase = (position.row / 3) * 3
        let colBase = (position.col / 3) * 3
        for rr in 0...2 {
            for cc in 0...2 {
                if num == table[rowBase+rr][colBase+cc] { return false }
            }
        }
        return true
    }

    func findPosition(table: [[Int]]) -> Position {
        var workPlaces   = [Place]()
        var sortedPlaces = [Place]()
        var position = Position()
        var place = Place()
            for cc in 0...8 {
                for rr in 0...8 {
                if table[rr][cc] == 0 {
                    position.row = rr
                    position.col = cc
                    place.position = position
                    place.val    = eval(position: position, table: table)
                    workPlaces.append(place)
                }
            }
        }
        sortedPlaces = workPlaces.sorted( by: { $0.val < $1.val } )
        place = sortedPlaces[0]
        position = place.position
        return position
    }
    
    func dropNum(index: Int) {
        position = findPosition(table: table)
        for num in 1...9 {
            if isSafeForNum(position: position, num: num) {
                table[position.row][position.col] = num
                putPositions.append(position)
                if putPositions.count == nplaces { return }
                dropNum(index: index+1)
                if putPositions.count != nplaces {
                    position = putPositions[putPositions.count - 1]
                    table[position.row][position.col] = 0
                    putPositions.removeLast()
                }
            }
        }
    }
    
    func play() {
        dropNum(index: 0)
        myprint(table: table)
    }
}

// main program
let myboard = NumBoard()
myboard.play()