Sudoku - Generator

by Annett Schwarze | 2025-08-29

This article is part of a series in which a Sudoku game is implemented. As a first step, a generator is built, which is used to create random Sudokus.

A class SudokuGenerator is implemented, which fills a model class SudokuModel with random numbers for a correct sudoku field. A random selection of cells is chosen to be cleared. This approach ensures, that a solution for the sudoku exists.

        
class SudokuModel: ObservableObject {
    static let DIM = 9
    @Published var cells: [[Int]] = Array(repeating: Array(repeating: 0, count: DIM), count: DIM)

    func reset() {
        cells = Array(repeating: Array(repeating: 0, count: SudokuModel.DIM), count: SudokuModel.DIM)
    }

    func text(row: Int, col: Int) -> String {
        let v = cells[row][col]
        return v == 0 ? "" : "\(v)"
    }

    func colorIndex(row: Int, col: Int) -> Int {
        let subgridRow = row / 3
        let subgridCol = col / 3
        return ((subgridRow + subgridCol) % 2 == 0) ? 1 : 2
    }
}

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
        }
    }

    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
    }

    private 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
    }
}