Sudoku solver Pt.2: reference types

1Playground.swift

import PlaygroundSupport
import SwiftUI

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

// Times:     "copy+solve solve (val solve)"
Grid.easy //        6ms     0ms (     8ms)
Grid.medium //      9ms     0ms (   356ms)
Grid.hard //       11ms     0ms (   103ms)
Grid.expert //  1,951ms 1,938ms (54,426ms)
Grid.empty //      49ms    19ms (   101ms)
Grid.solved //      2ms     0ms (     0ms)
Grid.unsolvable // 🤯

Examples.swift

extension Grid {
    
    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
""")
    
    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
""")
    
    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
""")
    
    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
""")
    
    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
""")
    
    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
""")
    
    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 func solveTheRest(from idx81: Int = 0) -> Bool {
        guard idx81 < 81 else { return true }
        let cell = sortedCells[idx81]
        let next = idx81 + 1
        // 1. Is given?
        guard cell.needsGuess else { 
            return solveTheRest(from: next)
        }
        
        // 2. Guess, from 1-9 where valid
        for i in cell.initialValidGuesses {
            // Maybe its no longer valid
            guard !cell.groupsContain(i) else { continue }
            
            cell.guess = i
            
            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
        cell.guess = nil
        return false
    }
    
}

Types.swift

public class Grid {
    let orderedCells: [Cell]
    var sortedCells: [Cell]
    let groups: [Group]
    let rows: [[Cell]]
    
    init(initial: String) {
        // All cells
        let rows = initial
            .split(separator: "\n")
            .enumerated()
            .map({ (rowIdx, rows) -> [Cell] in 
                rows
                    .compactMap { Int(String($0)) }
                    .enumerated()
                    .map({ (colIdx, given) in
                        return Cell(
                            row: rowIdx, 
                            column: colIdx, 
                            given: given
                        )
                    })
            })
        let cells = rows.flatMap { $0 }
        self.orderedCells = cells
        self.sortedCells = cells
        self.rows = rows
        
        // Groups for checking
        groups = (0..<9).flatMap { i -> [Group] in 
            [
                Group(cells) { $0.row == i },
                Group(cells) { $0.column == i },
                Group(cells) { $0.section == i },
            ]
        }
        
        // Calculate all valid guesses for each cell
        var changed = true
        while changed {
            changed = false
            for cell in self.sortedCells {
                if cell.calculateValidGuesses() {
                    changed = true
                }
            }
            sortedCells.sort {
                $0.initialValidGuesses.count < $1.initialValidGuesses.count
            }
        }
    }
    
    func initialAsString() -> String {
        rows
            .map({ row in 
                row
                    .map { cell in cell.given.map(String.init) ?? "0" } 
                    .joined()
            })
            .joined(separator: "\n")
    }
}

class Group {
    let cells: [Cell]
    init(_ cells: [Cell], predicate: (Cell) -> Bool) {
        // Filter
        self.cells = cells.filter(predicate)
        // Link
        for cell in self.cells {
            cell.groups.append(self)
        }
    }
    func contains(_ i: Int) -> Bool {
        cells.contains { $0.value == i }
    }
}

class Cell {
    
    let row: Int
    let column: Int
    let section: Int
    
    var value: Int?
    let given: Int?
    var onlyOneValidGuess: Int? { didSet { updateValue() }}
    var guess: Int? { didSet { updateValue() }}
    
    var groups: [Group]
    var initialValidGuesses: [Int]
    var hasCalculatedValidGuesses: Bool = false
    
    /// Fast enough to stay a computed property
    var needsGuess: Bool { given == nil && onlyOneValidGuess == nil }
    
    public init(row: Int, column: Int, given: Int) {
        self.row = row
        self.column = column
        self.section = ((row / 3) * 3) + (column / 3)
        self.given = (given != 0) ? given : nil
        self.onlyOneValidGuess = nil
        self.guess = nil
        self.groups = []
        self.initialValidGuesses = []
        updateValue()
    }
    
    func groupsContain(_ i: Int) -> Bool {
        groups.contains { $0.contains(i) }
    }
    
    /// This was a computed property, but this is faster
    private func updateValue() {
        value = given ?? onlyOneValidGuess ?? guess
    }
    
    /// true if changed
    fileprivate func calculateValidGuesses() -> Bool {
        // 1. check we dont already have a number
        guard needsGuess else { 
            return false 
        }
        
        // 2. Check each 1...9
        let existing = initialValidGuesses
        initialValidGuesses = Array.oneToNine.filter { i in
            // 2.1 If we've excluded it before, keep excluding it
            if hasCalculatedValidGuesses, !existing.contains(i) { return false }
            // 2.2 If any group already contains it, exclude it
            if groupsContain(i) { return false }
            // 2.3 Keep it
            return true
        }
        
        /// 3. Optimisation if there is "only 1 valid guess"
        if initialValidGuesses.count == 1 {
            // Only one valid option
            onlyOneValidGuess = initialValidGuesses.first
        } else {
            onlyOneValidGuess = nil
        }
        
        // 4. Toggle a flag
        let firstAttempt = !self.hasCalculatedValidGuesses
        self.hasCalculatedValidGuesses = true
        
        // 5. Did something change?
        return firstAttempt 
            || initialValidGuesses != existing
    }
    
}

extension Array where Element == Int {
    static let oneToNine = Array(1...9)
}

Views.swift

import SwiftUI
import Foundation

let color = (
    line: (
        light: Color(.systemGray5), 
        dark: Color(.systemGray2)
    ),
    background: (
        given: Color(.secondarySystemBackground), 
        guess: Color(.systemBackground)
    ),
    text: (
        given: Color(UIColor.tertiaryLabel), 
        onlyGuess: 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.enumerated()), id: \.0) { (cIdx, cell) in
                        self.cellView(cell)
                    }
                }
            }
        }
        .padding(.init(top: 2, leading: 2, bottom: 0, trailing: 0))
        .background(color.line.dark)
    }
    
    func cellView(_ cell: Cell) -> 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(cell.column))
            .padding(.init(top: 0, leading: 0, bottom: 2, trailing: 0))
            .background(self.borderColor(cell.row))
    }
    
    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 {
        given != nil 
            ? color.text.given
            : onlyOneValidGuess != nil 
            ? color.text.onlyGuess
            : color.text.guess
    }
    var backgroundColor: Color {
        given != nil 
            ? color.background.given
            : color.background.guess 
    }
}

public struct GridResultView: View {
    let previous: Grid
    @State var solved: (
    didSolve: Bool, 
    grid: Grid, 
    time1: String?,
    time2: 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!.time1!)ms").font(Font.body.italic()) + Text(" (\(solved!.time2!)ms)").foregroundColor(.secondary)
                    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 {
            let str = self.previous.initialAsString()
            let start1 = Date()
            let grid = Grid(initial: str)
            let start2 = Date()
            let didSolve = grid.solveTheRest()
            let stop = Date()
            
            let formatter = NumberFormatter()
            //formatter.usesGroupingSeparator = true
            //formatter.groupingSeparator = ","
            formatter.maximumFractionDigits = 0
            formatter.numberStyle = .decimal
            let dist1 = start1.distance(to: stop) * 1000
            let dist2 = start2.distance(to: stop) * 1000
            self.solved = (
                didSolve, 
                grid, 
                formatter.string(for: dist1),
                formatter.string(for: dist2)
            )
        }
    }
    
    static func list(solve: Bool, grids: [(String, Grid)]) -> some View {
        ScrollView {
            VStack(spacing: 32) {
                ForEach(Array(grids.enumerated()), id: \.0) { (idx, grid) in
                    VStack(spacing: 8) {
                        Text("\(idx + 1). \(grid.0)").font(.title)
                        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),
            ]
        )
    }
}