Sudoku solver in Swift, on Mac

This is a “Part 2" from my last post. Go read that first.

Running on Mac, with compiler optimisations

After getting a few replies to my blog post on Twitter, I was curious to see just how fast it is on a Mac. On the iPad, it was running in a DEBUG mode while rendering a UI using SwiftUI. I’ve migrated it to a brand new Swift Package on my Mac. I added some tests and used XCTest’s measure(...) API. It will run the block 10 times and take an average in milliseconds.

Source: https://github.com/rjchatfield/sudoku-solver

Remember: My value type implementation was 95% slower than my reference type implementation on the iPad.

1. iPad Playground is the times I recorded on the iPad
2. MAC #RELEASE was the same code, run using swift test -c release and taking the quickest time from measure(...)'s results
3. +Improvements was some clean up I did
4. VAL is the value type implementation
5. REF is the reference type implementation

|        | iPad Playground | MAC #RELEASE | +Improvements  |
|        |   VAL  |   REF  |  VAL  |  REF |  VAL |   REF   |
|--------|--------|--------|-------|------|------|---------|
|   Easy |      5 |      6 |   0.1 |  0.3 |  0.1 |     0.4 |
| Medium |    187 |      9 |   1.5 |  0.5 |  0.3 |     0.5 |
|   Hard |     52 |     12 |   0.5 |  0.7 |  0.2 |     0.9 |
| Expert | 31_551 |  1_486 | 189.0 | 63.0 | 32.0 | 110-1.1 |

😧 Wow! That is pretty fast!

Just by running in #RELEASE mode:

• REF got 96% faster
• VAL got 99.5% faster

Most interestingly, the VAL (which was much slower, and was only brute forcing the solution) was almost as fast as REF. And after a bit of tweaking, it was 99.9% faster. Solving the whole expert game (using simplistic brute-force) in 32ms.

As part of the improvements in REF I started using Set type which meant the brute force technique gave non-deterministic results. Anywhere from 93% to 99.93% faster. Solving the whole expert game in 1ms.

Naked Pairs

Kaan shared this concept of “Naked Pairs”. As he expected, I hadn’t heard of it. The first search result led me to this:

Visualisation of a Naked Pair from https://www.learn-sudoku.com/naked-pairs.html

How it works: Notice there are two squares that both have the same two options. You can conclude that one of them will be 2 and the other will be 3. If that’s the case, we can remove the 2 & 3 pencil marks from the other cells in the same house. Same can be done to the pencil marks in that row.

I tried building that into my algorithm, but nothing I did made the time decrease. Sorry Kaan. But thank you very much for the inspiration.

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