Skip to content

Instantly share code, notes, and snippets.

@wojteklu
Created April 11, 2017 20:23
Show Gist options
  • Save wojteklu/c7dd9b21dc706f10028a40657629f1c0 to your computer and use it in GitHub Desktop.
Save wojteklu/c7dd9b21dc706f10028a40657629f1c0 to your computer and use it in GitHub Desktop.
Solving sudoku using constraint propagation
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)"
}
}
}
import Foundation
let grid = "005300000800000020070010500400005300010070006003200080060500009004000030000009700"
let board = Board(grid)
_ = board.solve()
print(board)
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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment