Try swift nyc soroush khanlou header

Spontaneous Swift Sudoku Solving

The Swift programming language has an abundance of features to help developers code efficiently. Souroush Khanlou live codes a Sudoku puzzle solver that highlights the sequence and collection protocols framework; Swift error handling; and deep copy using structs.


Introduction

My name is Souroush Khanlou, and I maintain my blog, where I write a lot about programming. You may also know me from the Fatal Error podcast that I host with Chris Dzombak.

Today we’re going to be doing live coding of a Sudoku solver.

sudoku grid

The rules are simple. You are given a 9x9 grid of boxes, and some of them contain a number - any number from one to nine. Your task is to fill in the empty boxes with the numbers one through nine.

Naive Sudoku Solver

To start, our representation of a Sudoku board looks like this:

let boardString = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3.."

We will build a better representation. but first, I will run you through what I already have set up, and then we will get to writing the solver code.

The core modeling component is the Cell. Fundamentally, a cell can be one of many values. Initially, the values will be the numbers one through nine. If the cell is “settled”, that means that we know what the value is. In that case, it’s going to have exactly one value in it. However, it might also have more values in it, because we are not sure what the correct value should be. Instead, the Cell contains information about which values it can and cannot have. Everything else is built on top of this Cell:

import Foundation

public struct Cell: Equatable, CustomStringConvertible {
    
    public let values: [Int]
    
    public var isSettled: Bool {
        return values.count == 1
    }
    
    public static func == (lhs: Cell, rhs: Cell) -> Bool {
        return lhs.values == rhs.values
    }
    
    public var description: String {
        if isSettled, let first = values.first {
            return String(first)
        }
        return "_"
    }
    
    public static func settled(_ value: Int) -> Cell {
        return Cell(values: [value])
    }
    
    public static func anything() -> Cell {
        return Cell(values: Array(1...9))
    }
}

Get more development news like this

A Cell has some helper methods. The description method will print the number value of the cell if it’s settled, otherwise, it will just print an underscore character. There are two convenience initializers. The func settled creates a new settled cell from a single input integer. The other, anything, creates a cell that represents any number in the range one through nine inclusive.

The Board is built from the Cell. The board is an array of cells which represents a row in the board, and then an array of rows is the whole board. The Board contains a method to initialize the grid from that ugly boardString I mentioned earlier. The method looks at each character in the string. If the character is a dot, it’ll return Cell.anything(). If it’s a valid integer, it will create a settled cell at that location. Any other character means malformed input, and in that case, I’ll just crash the app by calling fatalError():

    public init(boardString: String) {
        let characters = Array(boardString.characters)
        self.rows = (0..<9)
            .map({ rowIndex in
                return characters[rowIndex*9..<rowIndex*9+9]
            })
            .map({ rawRow in
                return rawRow.map({ character in
                    if character == "." {
                        return Cell.anything()
                    } else if let value = Int(String(character)) {
                        return Cell.settled(value)
                    } else {
                        fatalError()
                    }
                })
            })
    }

Board also includes a number of helper methods. There is a method to get every cell flattened into a long array, so we don’t have them in the array of arrays representation:

    public var cells: [Cell] {
        return Array(rows.joined())
    }

The Board can print itself using its description method. It has a method which returns true if all of the cells are settled, which means the board is solved:

    public var isSolved: Bool {
        return self.cells.all({ $0.isSettled })
    }

We also have a method row which takes a Cell’s index and returns its row. Note that a Cell’s index is between 0 and 80 (remember that the board is a 9x9 grid of Cells). Similarly, there’s a column method which returns the column for that index. There’s also a minigrid method which returns the mini-grid containing that index.

These three methods are used by canUpdate, and it takes an integer value between 1 and 9, and a Cell’s index. It checks to see if I can update the Cell at that index to that value.

Lastly, an update function which updates the values for a given cell. You can update to an array of possible values. But if you update to exactly one value, it will make sure that it can update that by calling canUpdate.

Solving

The way I solve Sudoku puzzles is run through all of the cells, find an empty cell, and check the row, column, and the mini-grid to see if there’s only one possible value that can be placed there. If that’s the case, I update that to that value. Then I repeat this until the board is solved. This cannot solve every puzzle but is a good place to start.

The solve method has a while loop that runs until board.isSolved returns true. Inside that while loop, it iterates through every cell in the board until it finds one that is not settled. If board.canUpdate returns true, then that number is valid for that cell:

for cell in board.cells {
	if (cell.isSettled) {
		continue
	}
	let possibleValues = (1...9).filter({ value in 
		return board.canUpdate(index: Int, toValue: value)
	})
}
...

The issue with this is that we do not have the index. The easiest way to get at this is to use the enumerated function: for (offset, cell) in board.cells.enumerated(). It returns an offset and a cell. Enumerated is not exactly the right thing to do in this situation.

Enumerated returns a number that starts from zero and increases by one every time. For arrays, it corresponds to the index, but for other types of collections, this is not always the case. If you called enumerated on an ArraySlice, the first element will have an offset of zero, even though its index may be two; wherever that ArraySlice starts.

It’s not exactly right, so I extended Collection to add a method withIndexes. withIndexes returns an index instead of an offset.

The cells can now be updated by index. If the array is empty, then this technique can’t solve this board, so we return from the function immediately:

if possibleValues.isEmpty {
    return
}

The last thing we do is update the board to those values that we found were valid for that index:

try? board.update(index: index, values: possibleValues)

Brute Force Sudoku Solver

The previous technique does not solve every board. Consider this example:

let boardString = "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"

If I let the solver run on this, it will go into an infinite loop. I initially believed that all Sudoku puzzles can be solved this way, and upon doing more research found this post by Peter Norvig about sophisticated strategies for solving Sudoku puzzles.

It highlights a number of strategies, but coding all the different strategies will involve a lot of work. This is why I will write a brute force solver for this problem.

Suppose a given Sudoku board has 60 unset cells. Each of those 60 cells could have one of nine possible values. Typically, brute forcing 9^60 can take hundreds of billions of years, but because we narrowed which values are possible using our first, naive solver, the set of possibleValues is likely less than 9.

The first step in brute forcing is to call the naive solver, and fill in the cells with all of their possible values. In an unsettled cell, pick the first one of those values, and see if the board is solvable. If it is, then that was the correct choice, otherwise, try the second possible value for that cell an so on until the puzzle is solved.

We’re going to try every possible value, with a few optimizations that will be added later. First, we check if the puzzle’s solved by the naive method. If that’s the case, we can just return from the solve method. Once we’ve tried that, we’ll check our cells for the first value that isn’t settled:

let optional = board.cells.first(where: { !$0.isSettled })

At this point, we know that optional is never going to be nil, because the board is still unsolved, so we must have some cell that’s not settled:

guard let cell = optional else { return }

Next, check all the possible values that this cell could be. Grab all the values in the cell with cell.values and for each of those values create a scratch pad to test that the current value is the correct value for this box:

for value in cell.values {
    var copy = board
    try copy.update(index: Int, values: [value])

    ...

Once we have that copy, we can try to update the copy. Update is a throwing function, so we need to wrap it and catch our error. If the error is a consistency error, then continue.

Now we have a new board, and a cell that we’ve updated to something that we think might be right - we still need to solve the rest of the board. The best way to do that is to run the exact same thing again, and see if you generate any consistency errors through recursion:

for value in cell.values {
    var copy = board
    do {
        try copy.update(index: index, values: [value])
        print(copy)
    } catch {
        if error is ConsistencyError {
            continue
        }
    }
    let solver = Solver(board: copy)
    solver.bruteForce()
    if solver.isSolved {
        self.board = solver.board
        return
    }
}

We can make an optimization that will help this code run faster. Suppose you are working with a big tree. The root or top of the tree is the first choice that you make. That first choice has some number of potential options which each represent a branch. Then each of those branches represents the next choice that you will make about which cell you should use.

As you go through this tree, you sometimes update a value to something, and you get a consistency error. This means that everything below that branch cannot be a correct solution, so you throw it away. If we can throw out more of this tree earlier, and higher up, then that solves the problem faster.

Making this improvement does not much effort. Sort the cells according to how many potential values they have, and start with the one with the smallest number:

let optionalTuple = board.cells
    .withIndexes()
    .sorted(by: { left, right in
        return left.1.values.count < right.1.values.count
    })
    .first(where: { !$0.1.isSettled })

This ensures that the first thing that we check has a very small number of potential options, and if one of those options ends up being incorrect then we can throw away a part of that tree, which leads to a faster computation.

You can see that the board is starting to fill in from the bottom, sometimes from the middle, and does not necessarily always fill in from the top. This is how you know the optimized algorithm is working.

Error Handling

I like this problem so much because it takes advantage of a few Swift features that are worth noting, in particular, errors. When you have a system that is synchronous and has failure modes, it can be nice to describe those failure modes with something like our consistency error, and catch those later and deal with them in special ways as needed.

Sequences and Collections

Swift has an excellent sequencing collection system. For example, we can do slicing, flatMapping, mapping, filtering, etc. While there are some rougher edges to Swift, and it’s still a very new language, the sequence and collection handling are very rich and help you solve problems.

Sequences and collections give you all these interesting and useful tools that you can use to solve the problem more easily. And if you were at Playgrounds in Melbourne or try! Swift Tokyo, you saw my talk about sequences and collections and you know how much I love that system in Swift.

Struct Deep Copies

Lastly, I want to bring up Swift’s struct system and the way that it copies values into new references. This makes it easy be able to copy really easily. If you want to do this in Objective-C, you have to implement copyWithZone, and then you’ve got to make a new one, and then you have to allocWithZone, and copy the value into the right-hand side, and then return it. In Swift, it’s simply:

var copy = board.

You can explore the full Sudoku solver source code repository on GitHub.

Next Up: Complete Your Collections Knowledge by Learning Realm Collections

General link arrow white

About the content

This talk was delivered live in September 2017 at try! Swift NYC. The video was recorded, produced, and transcribed by Realm, and is published here with the permission of the conference organizers.

Soroush Khanlou

Soroush Khanlou is a New York-based iOS consultant. He’s written apps for the New Yorker, David Chang’s Ando, Rap Genius, and non-profits like Urban Archive. He blogs about programming at khanlou.com, mostly making fun of view controllers. In his free time, he runs, bakes bread and pastries, and collects suitcases.

4 design patterns for a RESTless mobile integration »

close