Sudoku solver Pt.1: Value types

1Playground.swift

import PlaygroundSupport
import SwiftUI

Grid.easy // 8ms
Grid.medium // 356ms
Grid.hard // 103ms
Grid.expert // 54,426ms
Grid.empty // 101ms
Grid.solved // 0ms
Grid.unsolvable // 0ms

PlaygroundPage.current.setLiveView(
    GridResultView.all()
    //GridResultView.single(.empty)
)

Examples.swift

extension Grid {
    /// 8ms
    public static let easy = Grid(initial: """
000 904 600
040 050 831
820 613 040

090 832 107
218 745 000
703 006 000

002 000 410
185 429 060
374 000 020
""")
    
    /// 346ms
    public static let medium = Grid(initial: """
800 100 070
020 040 800
060 700 000

000 470 908
240 080 003
038 060 015

080 694 100
900 007 204
005 810 006
""")
    
    /// 100ms
    public static let hard = Grid(initial: """
004 860 030
001 000 090
805 009 060

500 206 001
027 001 009
100 043 006

050 000 000
009 000 400
700 400 015
""")
    
    /// 83,016ms (86s!!)
    /// Reveresed 9...1: 66s
    /// Fixed: 54s
    public static let expert = Grid(initial: """
130 005 000
500 700 002
004 209 000

000 000 000
910 000 087
007 060 010

050 400 000
340 050 000
800 006 305
""")
    
    /// 0ms
    public static let solved = Grid(initial: """
123 456 789
456 789 123
789 123 456

214 365 897
365 897 214
897 214 365

531 642 978
642 978 531
978 531 642
""")
    
    /// 0ms
    public static let unsolvable = Grid(initial: """
023 456 789
100 000 000
000 000 000

000 000 000
000 000 000
000 000 000

000 000 000
000 000 000
000 000 000
""")
    
    /// 97ms
    public static let empty = Grid(initial: """
000 000 000
000 000 000
000 000 000

000 000 000
000 000 000
000 000 000

000 000 000
000 000 000
000 000 000
""")

}

Logic.swift

extension Grid {
    
    public mutating func solveTheRest(from point: Point = .zero) -> Bool {
        let next = point.next()
        switch self[point] { 
        case .given:
            guard let next = next else {
                // Finished
                return true
            }
            let isAllSolved = solveTheRest(from: next)
            return isAllSolved 
            
        case .guess:
            let section = Point(x: point.x/3, y: point.y/3) 
            for i in 1...9 where isValid(i, point, section) {
                self[point] = .guess(i)
                
                guard let next = next else {
                    // Finished
                    return true
                }
                let isAllSolved = solveTheRest(from: next)
                
                if isAllSolved {
                    // Finished
                    return true 
                }
                
                // else, this guess did not lead to a valid conclusion, so we try a different guess and do it all again.
            }
            
            // Not solved, so ignore any guesses
            self[point] = .guess(nil)
            return false
        }
    }
    
    public func isValid(_ i: Int, _ point: Point, _ section: Point) -> Bool {
        for (xIdx, xSection) in theIndicies {
            let sameXSec = xSection == section.x
            for (yIdx, ySection) in theIndicies {
                let sameYSec = ySection == section.y
                let p = Point(x: xIdx, y: yIdx)
                
                // Ignore same cell
                guard p != point else { continue }
                // Same y-axis, x-axis, or section
                guard yIdx == point.y
                    || xIdx == point.x
                    || (sameXSec && sameYSec)
                    else { continue }
                
                if self[p].value == i {
                    return false
                }
            }
        }
        
        // all good!
        return true
    }
    
}

let theIndicies = (0..<9).map { ($0, $0/3) }

Types.swift

public struct Grid: Equatable, Hashable {
    public var rows: [Row] = (0...9).map { _ in Row() }
}
extension Grid: CustomDebugStringConvertible {
    public init(initial: String) {
        rows = initial
            .split(separator: "\n")
            .map(Row.init)
    }
    
    public subscript(point: Point) -> Cell {
        get { rows[point.y].cells[point.x] }
        _modify { yield &rows[point.y].cells[point.x] }
    }
    
    public var debugDescription: String {
        var lines = rows.map { row -> String in  
            let t = row.cells.map { $0.value.map(String.init) ?? "_" }
            return "|  \(t[0]) \(t[1]) \(t[2])  |  \(t[3]) \(t[4]) \(t[5])  |  \(t[6]) \(t[7]) \(t[8])  |"
        }
        lines.insert(String(repeating: "—", count: 11), at: 3)
        lines.insert(String(repeating: "—", count: 11), at: 7)
        return lines.joined(separator: "\n")
    }
}
public struct Row: Equatable, Hashable {
    public var cells: [Cell] = (0...9).map { _ in .guess(nil) }
}
extension Row {
    init(initial: Substring) {
        cells = initial.compactMap(Cell.init)
    }
}
public enum Cell: Equatable, Hashable {
    case given(Int)
    case guess(Int?)
    
    public init?(char: Character) {
        guard let int = Int(String(char)) else { return nil }
        if int != 0 {
            self = .given(int)
        } else {
            self = .guess(nil)
        }
    }
    
    public var value: Int? {
        switch self {
        case .given(let value): return value
        case .guess(let value): return value
        }
    }
}

public struct Point: Equatable, CustomDebugStringConvertible {
    public let x: Int
    public let y: Int
    
    public var debugDescription: String { "(x:\(x), y:\(y))" }
    
    public init(x: Int, y: Int) {
        self.x = x
        self.y = y
    }
    
    public func next() -> Point? {
        guard self != .terminate else { return nil }
        let nextX = (x + 1) % 9
        return Point(
            x: nextX,
            y: nextX == 0 ? y + 1 : y
        )
    }
    public static let zero = Point(x: 0, y: 0)
    public static let terminate = Point(x: 8, y: 8)
}

View.swift

import SwiftUI
import Foundation

let color = (
    line: (
        light: Color(.systemGray5), 
        dark: Color(.systemGray2)
    ),
    background: (
        given: Color(.secondarySystemBackground), 
        guess: Color(.systemBackground)
    ),
    text: (
        given: Color.secondary, 
        guess: Color.primary
    )
)

struct GridView: View {
    let grid: Grid
    var body: some View {
        VStack(spacing: 0) { 
            ForEach(Array(grid.rows.enumerated()), id: \.0) { rIdx, row in
                HStack(spacing: 0) {
                    ForEach(Array(row.cells.enumerated()), id: \.0) { cIdx, cell in
                        self.cell(cell, rIdx: rIdx, cIdx: cIdx)
                    }
                }
            }
        }
        .padding(.init(top: 2, leading: 2, bottom: 0, trailing: 0))
        .background(color.line.dark)
    }
    
    func cell(_ cell: Cell, rIdx: Int, cIdx: Int) -> some View {
        Text(cell.value.map(String.init) ?? " ")
            .font(Font.headline.monospacedDigit())
            .frame(width: 35, height: 35, alignment: .center)
            .foregroundColor(cell.foregroundColor)
            .background(cell.backgroundColor)
        
            .padding(.init(top: 0, leading: 0, bottom: 0, trailing: 2))
            .background(self.borderColor(cIdx))
            .padding(.init(top: 0, leading: 0, bottom: 2, trailing: 0))
            .background(self.borderColor(rIdx))
    }
    
    func borderColor(_ index: Int) -> Color {
        switch index {
        case 2, 5, 8: return color.line.dark
        default: return color.line.light
        }
    }
}

extension Cell {
    var foregroundColor: Color {
        switch self {
        case .given: return color.text.given
        case .guess: return color.text.guess
        }
    }
    var backgroundColor: Color {
        switch self {
        case .given: return color.background.given
        case .guess: return color.background.guess 
        }
    }
}

public struct GridResultView: View {
    let previous: Grid
    @State var solved: (didSolve: Bool, grid: Grid, time: String?)?
    let solve: Bool
    
    public init(_ grid: Grid, solve: Bool) {
        self.previous = grid
        self.solve = solve
    }
    
    public var body: some View {
        VStack(spacing: 8) {
            if solved != nil {
                if solved!.didSolve {
                    Text("🤓 Solved in") + Text(" \(solved!.time!)ms").font(Font.body.italic())
                    GridView(grid: solved!.grid)
                } else {
                    Text("🤯 Cannot be solved 🤯")
                    GridView(grid: previous)
                }
                
            } else {
                Text(solve ? "🤔 Solving..." : "😴 Solver Disabled")
                GridView(grid: previous)
            }
        }
        .onAppear { self.solveTheGrid() }
    }
    
    func solveTheGrid() {
        guard solve else { return }
        DispatchQueue.global(qos: .userInitiated).async {
            var grid = self.previous
            let start = Date()
            let didSolve = grid.solveTheRest()
            
            let stop = Date()
            let formatter = NumberFormatter()
            formatter.maximumFractionDigits = 0
            formatter.numberStyle = .decimal
            let dist = start.distance(to: stop) * 1000
            
            self.solved = (didSolve, grid, formatter.string(for: dist))
        }
    }
    
    static func list(solve: Bool, grids: [(String, Grid)]) -> some View {
        ScrollView {
            VStack(spacing: 16) {
                ForEach(Array(grids.enumerated()), id: \.0) { (idx, grid) in
                    VStack(spacing: 8) {
                        Text("\(idx). \(grid.0)")
                        GridResultView(grid.1, solve: solve)
                    }
                }
            }
            .padding()
        }
    }
}

extension GridResultView {
    public static func single(_ grid: Grid) -> GridResultView {
        GridResultView(grid, solve: true)
    } 
    
    public static func all() -> some View {
        GridResultView.list(
            solve: true, 
            grids: [
                ("Easy", .easy),
                ("Medium", .medium),
                ("Hard", .hard),
                ("Expert", .expert),
                ("Empty", .empty),
                ("Solved", .solved),
                ("Unsolvable", .unsolvable),
            ]
        )
    }
}