Solving sudoku using constraint propagation

board.swift

class Board {
    fileprivate let kSize = 9 // number of rows and columns
    fileprivate var squares: [Square]
    fileprivate var units: [[[Int]]] = []
    fileprivate var peers: [[Int]] = []

    init(_ string: String) {
        squares = [Square](repeating: Square(0b111111111), count: kSize * kSize)
        
        for index in 0..<(kSize * kSize) {
            units.append(units(of: index))
            peers.append(peers(of: index))
        }
        
        let values = grid.characters.map { Int(String($0)) ?? 0 }
        
        for i in 0..<(kSize * kSize) where values[i] > 0 {
            _ = assign(digit: values[i], to: i)
        }
    }
    
    private func assign(digit: Int, to index: Int) -> [Square]? {
        let otherDigits = squares[index].digits.filter { $0 != digit }
        
        for d in otherDigits {
            if eliminate(digit: d, from: index) == nil {
                return nil // conflict detected
            }
        }
        return squares
    }
    
    private func eliminate(digit: Int, from index: Int) -> [Square]? {
        
        if !squares[index].hasDigit(digit) { // already eliminated
            return squares
        }
        
        squares[index].remove(digit: digit) // eliminate
        
        let count = squares[index].count
        
        if count == 0 { // conflict - removed last value
            return nil
        } else if count == 1 {
            // only one value left - eliminate that value from the peers
            let last = squares[index].digits[0]
            for p in peers[index] {
                if eliminate(digit: last, from: p) == nil { return nil }
            }
        }

        for unit in units[index] {
            var digitPlaces = 0, digitPlacesCount = 0
            for index in unit {
                if squares[index].hasDigit(digit) {
                    digitPlaces = index
                    digitPlacesCount += 1
                }
            }
            if digitPlacesCount == 0 { // conflict - no place for this value
                return nil
            } else if digitPlacesCount == 1 {
                // only one place left in unit - put it there
                if assign(digit: digit, to: digitPlaces) == nil { return nil }
            }
        }
        
        return squares
    }
    
    func solve() -> [Square]? {
        if solved { return squares }
    
        let index = mostConstrainedIndex

        for digit in squares[index].digits {
            let squares = self.squares // save
            if assign(digit: digit, to: index) != nil {
                _ = solve()
            }
            if !solved { self.squares = squares } // restore
        }
        return nil
    }
    
    private var solved: Bool {
        return squares.first(where: { !$0.hasOneDigit }) == nil
    }
    
    private var mostConstrainedIndex: Int {
        return squares.enumerated().min(by: { $0.1.count > $1.1.count })?.0 ?? 0
    }
    
    private func units(of index: Int) -> [[Int]] {
        
        // same row
        var row = index / kSize
        var rowUnits: [Int] = []
        for column in 0..<kSize {
            rowUnits.append(row * kSize + column)
        }
        
        // same column
        var column = index % kSize
        var columnUnits: [Int] = []
        for row in 0..<kSize {
            columnUnits.append(row * kSize + column)
        }
        
        // 3x3 box
        row = 3 * (index / (3 * kSize))
        column = 3 * ((index % kSize) / 3)
        var boxUnits: [Int] = []
        for r in 0..<3 {
            for c in 0..<3 {                
                boxUnits.append((row + r) * kSize + (column + c))
            }
        }
        return [rowUnits, columnUnits, boxUnits]
    }
    
    private func peers(of index: Int) -> [Int] {
        var set = Set(Array(units(of: index).joined()))
        set.remove(index)
        return Array(set)
    }
}

extension Board: CustomStringConvertible {
    
    var description: String {
        return squares.enumerated().reduce("") { result, current in
            var separator = ""
            if current.0 != 0 && current.0 % 9 == 0 {
                separator = "\n"
            }
            return result + separator + " \(current.1.description)"
        }
    }
}

main.swift

import Foundation

let grid = "005300000800000020070010500400005300010070006003200080060500009004000030000009700"
let board = Board(grid)
_ = board.solve()
print(board)

square.swift

struct Square {
    fileprivate var value = UInt16(0)
    
    init(_ value: UInt16 = 0) {
        self.value = value
    }
    
    var digits: [Int] {
        var digits: [Int] = []
        for i in 1...9 {
            if hasDigit(i) {
                digits.append(i)
            }
        }
        return digits
    }
    
    var count: Int {
        return digits.count
    }
    
    mutating func remove(digit: Int) {
        value &= ~toMask(digit)
    }
    
    var hasOneDigit: Bool {
        return count == 1
    }
    
    func hasDigit(_ digit: Int) -> Bool {
        return (value & toMask(digit)) != 0
    }
    
    fileprivate func toMask(_ digit: Int) -> UInt16 {
        return UInt16(1 << (digit - 1))
    }
}

extension Square: CustomStringConvertible {
    var description: String {
        
        guard value != 0 else {
            return "-"
        }
        
        var string = ""
        
        for i in 1...9 where value & (toMask(i)) != 0 {
            string += String(i)
        }
        return string
    }
}