Skip to content

Instantly share code, notes, and snippets.

@rjchatfield
Created January 21, 2020 10:33
Show Gist options
  • Save rjchatfield/99bd88f196f23a8ca31058e4de912df2 to your computer and use it in GitHub Desktop.
Save rjchatfield/99bd88f196f23a8ca31058e4de912df2 to your computer and use it in GitHub Desktop.
Sudoku solver Pt.2: reference types
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 // 🤯
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
""")
}
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
}
}
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)
}
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),
]
)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment