Sudoku - Solver
This article is part of a series in which a Sudoku game is implemented. As a third step, a solver is built.
The SudokuGenerator is modified and includes a new updateAllowedNumbers function. The SudokuModel is adjusted with new properties to hold state for the solving process.
class SudokuModel: ObservableObject {
static let DIM = 9
@Published var cells: [[Int]] = Array(repeating: Array(repeating: 0, count: DIM), count: DIM)
@Published var cellsFixed: [[Bool]] = Array(repeating: Array(repeating: true, count: DIM), count: DIM)
@Published var cellsError: [[Bool]] = Array(repeating: Array(repeating: false, count: DIM), count: DIM)
@Published var allowedNumbers: [[[Int]]] = Array(repeating: Array(repeating: Array(1...DIM), count: DIM), count: DIM)
@Published var isSolved: Bool = false
func reset() {
cells = Array(repeating: Array(repeating: 0, count: SudokuModel.DIM), count: SudokuModel.DIM)
cellsFixed = Array(repeating: Array(repeating: true, count: Self.DIM), count: Self.DIM)
cellsError = Array(repeating: Array(repeating: false, count: Self.DIM), count: Self.DIM)
allowedNumbers = Array(repeating: Array(repeating: Array(1...Self.DIM), count: Self.DIM), count: Self.DIM)
}
func text(row: Int, col: Int) -> String {
let v = cells[row][col]
return v == 0 ? "" : "\(v)"
}
func allowedText(row: Int, col: Int) -> String {
let v = allowedNumbers[row][col]
return v.map({ String($0) }).joined(separator: " ")
}
func isFilled(row: Int, col: Int) -> Bool {
return cells[row][col] != 0
}
func colorIndex(row: Int, col: Int) -> Int {
let subgridRow = row / 3
let subgridCol = col / 3
return ((subgridRow + subgridCol) % 2 == 0) ? 1 : 2
}
func foregroundColorIndex(row: Int, col: Int) -> Int {
return cellsFixed[row][col] == true ? 1 : 2
}
func checkIsSolved() {
isSolved = cells.allSatisfy({ $0.allSatisfy({ $0 != 0 }) }) && cellsError.allSatisfy({ $0.allSatisfy({ $0 == false }) })
}
}
class SudokuGenerator {
func generate(model: SudokuModel) {
model.reset()
_ = fill(0, 0, model: model)
}
func makeGaps(model: SudokuModel, count: Int) {
var indices = Array(0 ..< SudokuModel.DIM*SudokuModel.DIM)
indices.shuffle()
for i in 0 ..< min(count, indices.count) {
let idx = indices[i]
let row = idx / SudokuModel.DIM
let col = idx % SudokuModel.DIM
model.cells[row][col] = 0
model.cellsFixed[row][col] = false
}
}
private func fill(_ row: Int, _ col: Int, model: SudokuModel) -> Bool {
if row == SudokuModel.DIM {
return true
}
let nextRow = (col == SudokuModel.DIM - 1) ? row + 1 : row
let nextCol = (col + 1) % SudokuModel.DIM
let nums = Array(1 ... SudokuModel.DIM).shuffled()
for num in nums {
if canPlace(num, atRow: row, col: col, in: model.cells) {
model.cells[row][col] = num
if fill(nextRow, nextCol, model: model) {
return true
}
model.cells[row][col] = 0
}
}
return false
}
func canPlace(_ num: Int, atRow row: Int, col: Int, in cells: [[Int]]) -> Bool {
for i in 0 ..< SudokuModel.DIM {
if cells[row][i] == num || cells[i][col] == num {
return false
}
}
let boxRow = (row / 3) * 3
let boxCol = (col / 3) * 3
for i in 0..<3 {
for j in 0..<3 {
if cells[boxRow + i][boxCol + j] == num {
return false
}
}
}
return true
}
func updateAllowedNumbers(model: SudokuModel) {
for row in 0 ..< SudokuModel.DIM {
for col in 0 ..< SudokuModel.DIM {
if model.cells[row][col] != 0 {
model.allowedNumbers[row][col] = []
continue
}
var allowed: [Int] = []
for num in 1 ... SudokuModel.DIM {
if canPlace(num, atRow: row, col: col, in: model.cells) {
allowed.append(num)
}
}
model.allowedNumbers[row][col] = allowed
}
}
}
}
