Sudoku solver in Swift, while on vacation

This is a “Part 1”. Find the follow up about running this in RELEASE mode in my next post. But read this first.

Today I’m coming back from a 4 week holiday through 5 countries, seeing friends and family, Christmas, New Years, a Punjabi Wedding. In my down time I wrote a sudoku solver with nothing but Swift Playgrounds on my iPad.

It’s an interesting problem to solve because once you have a solve that works, you can always make it faster. Assuming all things equal, the only way to take less time is to reduce the number of instructions it needs to make.

This article is a brain dump of what I did to solve sudoku and the optimisations I made. Much like the code, this too was written on a mobile device and may have typos and miss things. Let me know if you have any questions. The source can be found here:

• Part 1: Value types https://gist.github.com/rjchatfield/649e46e4255c8e75255bd3ce7990a342
• Part2:Reference types https://gist.github.com/rjchatfield/99bd88f196f23a8ca31058e4de912df2

Opening notes

- Not timed in RELEASE Mode
- No concurrency or parallelism
- Just basic Array methods (No Accelerate.framework)
- Visualisation is in SwiftUI
- You must disable results in Swift Playground…

Swift Playgrounds won’t handle it

1. Data source

First step of getting this to work is inventing a format for the data source and a parser to convert it into our data structure. I downloaded a free Sudoku app and wrote down the initial state of the game in easy, medium, hard & expert difficulties. The format I settled on was a String where:

• 0 meant blank
• every other Int was the “given” number
• white spaces were ignored

Example

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
“””)

2. Everything as a struct

🧐 When I first visualised this problem, I imagined using value types with pure functions.

• struct Grid: has Rows
• struct Row: has Cells
• enum Cell: held an Int, either “given” or “guess”

Making copies of all of those values in all those nested for-loops may have had a penalty, so I was quick to use mutating functions.

I used a brute force approach, which means I tried every combination of 1-9 in every cell and stopped when I found the first solution. It went something like:

1. Put a 1 in the first cell
2. Are there any 1’s in the same row?
3. Are there any 1’s in the same column?
4. Are there any 1’s in the same section?
5. Can the rest of the puzzle be solved with this 1 here?
6. If so, we’re done!
7. If something failed, we try 2 and repeat steps 2–7, trying each number from 1-9

That is how we guess each number, however if it has any hardcoded given values then we can just do Step 5 and continue solving the rest of the puzzle.

3. Lifting calculations out of the for-loop

The most expensive computation at this point was knowing for any given cell:

- calculating the row index
- calculating the column index
- the section index
- the coordinates of the “next” cell

🤑 All 4 of those:

- used Integer division and modulo arithmetic
- were calculated when needed, then forgotten if we go out of scope
- were deterministic and immutable for the entire game

So the next logical move was to compute all 4 of those values once at init time and store them for the life of the game.

After a few smaller tweaks I’d refactored as much heavy computation out of the for-loops as I could find, but I still wasn’t impressed with the speed. 😩 The Expert game was taking up to 54 seconds to finish.

Times:

Grid.easy       //      8ms
Grid.medium     //    356ms
Grid.hard       //    103ms
Grid.expert     // 54,426ms 😩
Grid.empty      //    101ms
Grid.solved     //      0ms

I thought about computing things in parallel, but decided to go in the opposite direction and use reference types…

4. Everything as a class

I proudly started this code using values and functions, avoiding references and shared mutable state. But all of this implementation was private and single threaded, so I though it would be safe to experiment with using classes.

I switched every struct and enum to class and removed some mutating keywords, but it wasn’t that simple. The Playground would crash every time. The problem was that my SwiftUI @State was changing in-place on a background thread while rendering, and not triggering the didSet when it finished. It wasn’t safe to call methods on the original copy, so I had to implement a copy(). Already, this was grosser than the functional approach I initially imagined.

😐 This change made no improvement to the total time. But unlocked some interesting options.

Side note: I miss git. Iterating on an algorithm with no version control is painful. At this point, I duplicated the playground and kept the struct-based implementation as a base reference.

Now we have reference types that can be passed and stored independently of the data, let’s take advantage of this in the algorithm.

5. Grouping

One problem with our algorithm is that in order to check if a guess is allowed, we have to traverse all 81 cells, checking if the coordinates match the same row, column or section. We should aim to only check 27 cells max.

Instead of keeping a Row type and calculating the column and section, I implemented an arbitrary Group class to hold references to 9x cells. Inversely, each cell belonged (and held a reference) to 3x groups.

In total, there were:

- 9x row groups
- 9x column groups
- 9x section groups

By giving each Cell a reference to the groups it belonged to, we could check if the existence of a number in all 3 without traversing all 81 cells. This was a wonderful speed improvement.

6. Initial valid guesses

🤔 Imagine you have a section like this:

1x Section example:

[ ]7 6
 5 4 3
 2 1[ ]

Where all of those numbers were hardcoded given numbers and we only needed to solve the first and last cells. The solve is 8 or 9 can fit into either cell. This should solve pretty quickly, but let’s step through what happens:

- Try 1
- Does that exist in the Row? No
- Does that exist in the Cell? No
- Does that exist in the Section? Yes 😵
- Try 2
- …
- Try 8
- Success! We found our first valid option. Let’s solve the last square…
- Try 1
- …
- Try 9
- Success!

That took 8 loops in the first cell + 9 loops in the last cell to find a valid solve.

Why did we have to check 17 numbers when we kind of knew there were only 2 numbers?

Now imagine that we try solve the next section where the only valid number is 8.

2x Section example:

[8]7 6 |[ ]2 1
 5 4 3 | 9 6 7
 2 1[9]| 3 4 5

However we already guessed an 8 in the top row. So we’ve guessed the wrong number… 🙎🏻‍♂️ Let’s step through the algorithm and find out.

So our algorithm will:

- guess 9 times = validate each guess 3 times
- must fail and roll all the way back to the first cell and increment the guess from `8` up to `9`.
- Start all over again!!
- Check if `9` is valid
- then repeat the 8x checks of the bottom cell
- then repeat the 8x checks of the right cell

That is the nature of brute forcing this puzzle. But since we were given 7 of the 9 cells in that first section at init time, we can calculate a set of possible guesses filtering out the given values. That means there are only 2 valid numbers for the first cell and 2 valid numbers for the bottom cell.

What’s the point?

Calculating the above 2 Section example:

Checking all 1–9 values
= No initial checks + 43 runtime checks
= 43 checks total

Checking filtered set of initial valid guesses
= 27 initial checks + 7 run time checks
= 34 checks total

Noice! And while this only shows 3 cells, the optimisation is exponential every cell you need to guess.

7. Implicitly given value

In that last example, when we looked at the second section, we can see with our amazing pattern-matching brain that 8 is the only valid option for that cell. We should be able to figure that out at init time.

In the Cell, we have two ivars: given and guess. Let’s add a 3rd in between called onlyValidOption. While we calculate the set of initial valid guesses, if the array has only one element, we can use that as the official value for that cell and avoid any further guessing. Almost has an “implicitly given value”.

What’s the point?

At init time, we can set the right cell to the value 8 immediately. Now when we try guess the first cell reduced the number of valid options from two to just one. And when we come to guess the bottom cell, there is again only one remaining guess for that cell too. Magic!

Capturing implicit given values (single pass)
= 27 initial checks + 3 runtime checks
= 30 total checks

😇 Pretty good. But now that we have these new “implicit given values” perhaps we could do another pass re-calculating all of the sets of initial valid guesses making the sets smaller, and hopefully finding the only valid guess.

Capturing implicit given values (multi pass)
= 30 initial checks + 0 runtime checks
= 30 total checks

This may look equivalent, but remember that the runtime checks try solve all numbers where as this only build a set of possible numbers. This is a smidge faster.

In practice I found the easier sudoku levels could be solved entirely at init time without any guessing — just by using the given values to find the implicitly given values. However, the Expert level (now only 7 seconds — 88% faster than without implicitly given values) still needed to use brute force guessing.

8. Sorted cells

We’ve done a lot of improvements that have made our algorithm much faster. 😕 But that Expert level was taking 46x longer to finish than the Hard level?!

Earlier I commented about the exponential nature of this brute force approach. It was made worse if the earlier cells have many valid guesses. For example, if every cell had only one valid guess, it’s solved. If every cell had two valid guesses, you try the first value else you try the other. If all the cells have 9 guesses then there are lots of values to try. Lots!

So what if we solved the cells in order of how many valid guesses it has?

The smaller number of guesses first (probability of getting it right first time is much higher and won’t require re-looping over the subsequent cells) with the cells with the highest number of guesses last (probability is the lowest).

As a lover of value types it pains me to say it, but this approach is only viable because our data structure leverages reference types. But so long as we hold onto the ordered list (for rendering later) we can hold onto a second sorted list.

🥳 I re-ran the Expert level puzzle and it solved in 1.9s. That’s 3.6x faster! I’m happy with that.

9. Conclusion

Times:

// 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)

So after a few lazy afternoons and some weird late night epiphanies, I’m pretty happy with where I got to. It was fun to use Swift Playgrounds and code on my iPad. SwiftUI just worked!

I really missed git. I don’t know how beginners can enjoy programming with the fear of breaking everything looming over head. So many times I tried a crazy idea like caching some calculation, made everything complicated with lookups and didSets, and realised it actually made things slower. I wish I could have reverted to an earlier commit. Even if it worked like Time Machine or iWork’s Versions feature — I don’t think I needed full branches and remotes.

Side note: After all this work, I demo’d it to a friend I went to university with whom reminded me that I’d written a sudoku solver for a first year assignment. 🤦🏻‍♂️ Might be interesting to compare my first year Java with this Swift code.

Thank you for reading. If you enjoyed this, please like, share, read my other rants, and follow me on Twitter.