Monthly Archives: December 2016

Number Place and Swift 3 (3)

backtrack

The graph shows the value of the index when the recursive function dropNum(index: Int) is called. Note that initially there are 52 empty places to be filled.

    func dropNum(index: Int) {
        var place = emptyPlaces[index]
        for num in 1...9 {
            if isSafeForNum(place: place, num: num) {
                table[place.row][place.col] = num
                putCount += 1
                if putCount == nplaces { return }
                dropNum(index: index+1)
                if putCount != nplaces {
                    place = emptyPlaces[index]
                    table[place.row][place.col] = 0
                    putCount -= 1
                }
            }
        }
    }

You can try the program at the site, IBM Swift Sandbox, by doing copy and paste the following 95 lines.

backtrack2

struct Place {
    var row: Int = -1
    var col: Int = -1
}

class NumBoard {
    var table       = [[Int]]()
    var emptyPlaces = [Place]()
    var place       = Place()
    let nplaces : Int
    var putCount: Int

    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 {
                    place.row = rr
                    place.col = cc
                    emptyPlaces.append(place)
                 }
            }
        }
        putCount = 0
        nplaces  = emptyPlaces.count
        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 isSafeForNum(place: Place, num: Int) -> Bool {
        for rr in 0...8 {
            if num == table[rr][place.col] { return false }
        }
        for cc in 0...8 {
            if num == table[place.row][cc] { return false }
        }
        let rowBase = (place.row / 3) * 3
        let colBase = (place.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 dropNum(index: Int) {
        var place = emptyPlaces[index]
        for num in 1...9 {
            if isSafeForNum(place: place, num: num) {
                table[place.row][place.col] = num
                putCount += 1
                if putCount == nplaces { return }
                dropNum(index: index+1)
                if putCount != nplaces {
                    place = emptyPlaces[index]
                    table[place.row][place.col] = 0
                    putCount -= 1
                }
            }
        }
    }

    func play() {
        dropNum(index: 0)
        myprint(table: table)
    }
}

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

Number Place and Swift 3 (2)

numberplace2

The code should always be simple, but still not in that stage.

struct Place {
    var row: Int = -1
    var col: Int = -1
}

class NumBoard {
    var table       = [[Int]]()
    var emptyPlaces = [Place]()
    var place       = Place()
    let nplaces : Int
    var putCount: Int

    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 {
                    place.row = rr
                    place.col = cc
                    emptyPlaces.append(place)
                 }
            }
        }
        putCount = 0
        nplaces = emptyPlaces.count
        myprint(table: table)
    }

    func myprint(table: [[Int]]) {
        print("-----------------")
        for rr in 0...8 {
            for cc in 0...8 {
                print(table[rr][cc], terminator: " ")
            }
            print("")
        }
        print("-----------------")
    }
    
    func isSafeForNum(place: Place, num: Int) -> Bool {
        for rr in 0...8 {
            if num == table[rr][place.col] { return false }
        }
        for cc in 0...8 {
            if num == table[place.row][cc] { return false }
        }
        let rowBase = (place.row / 3) * 3
        let colBase = (place.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 dropNum(index: Int) {
        /* could be better */
    }

    func play() {
        dropNum(index: 0)
        myprint(table: table)
    }
}

let myboard = NumBoard()
myboard.play()

By the way, you may not like the lines such as:

let rowBase = (place.row / 3) * 3
let colBase = (place.col / 3) * 3
  for rr in 0...2 {
    for cc in 0...2 {
      if num == table[rowBase+rr][colBase+cc] { return false }
    }
  }

In my opinion, this is much easier on the eyes than replacing 3 with blockSize and 2 with blockSize-1.