Solitaire Solver

After spending way too much time playing Shenzhen I/O by Zachtronics, I got hooked on its Solitaire game when that was released as an app. The free version of this game gives you two games before having to wait for new tokens. Now, of course, paying to unlock would have been an option, but I rather enjoyed having limited attempts.

Now, the tricky part is that boards for this game are generated randomly. A small, but significant, number of games are straight up unsolvable. So, I found myself agonizing over difficult games, not daring to make a bad move, trying to figure out if a game was solvable at all.

CLI

To help with understanding what my chances are and whether any given game might be solvable, I started writing this neat little CLI. Pretty quickly, I had a console app that was able to generate random boards:

 _______  _____         _____ _______ _______ _____  ______ _______
 |______ |     | |        |      |    |_____|   |   |_____/ |______
 ______| |_____| |_____ __|__    |    |     | __|__ |    \_ |______

Creating new game

Creating board

Creating random board

Random board based on seed: 423227720
Lockable 1   |Lockable 2   |Lockable 3   |Flower stack |Filing 0     |Filing 1     |Filing 2
             |             |             |             |             |             |
Stack 1      |Stack 2      |Stack 3      |Stack 4      |Stack 5      |Stack 6      |Stack 7      |Stack 8
Black 9      |Red 6        |Black Dragon |Green 7      |Green 3      |Black Dragon |Red 5        |Green Dragon
Red Dragon   |Red Dragon   |Black 3      |Red 9        |Red Dragon   |Flower Flower|Black 1      |Black 2
Red 7        |Green Dragon |Black 8      |Black 4      |Black Dragon |Black 7      |Black 5      |Red 1
Green 1      |Green 9      |Red 8        |Green 8      |Red Dragon   |Red 3        |Black Dragon |Green Dragon
Green 6      |Black 6      |Green Dragon |Red 2        |Green 4      |Green 2      |Green 5      |Red 4

Lockable 1   |Lockable 2   |Lockable 3   |Flower stack |Filing 0     |Filing 1     |Filing 2
             |             |             |             |             |             |
Stack 1      |Stack 2      |Stack 3      |Stack 4      |Stack 5      |Stack 6      |Stack 7      |Stack 8
Black 9      |Red 6        |Black Dragon |Green 7      |Green 3      |Black Dragon |Red 5        |Green Dragon
Red Dragon   |Red Dragon   |Black 3      |Red 9        |Red Dragon   |Flower Flower|Black 1      |Black 2
Red 7        |Green Dragon |Black 8      |Black 4      |Black Dragon |Black 7      |Black 5      |Red 1
Green 1      |Green 9      |Red 8        |Green 8      |Red Dragon   |Red 3        |Black Dragon |Green Dragon
Green 6      |Black 6      |Green Dragon |Red 2        |Green 4      |Green 2      |Green 5      |Red 4

Solver

Next up, I figured out clean ways to represent board states and implemented both a depth and a breadth-first solver. I quickly figured out that the number of board states and possible moves, even with duplicates ignored, is quite large. The breadth-first solver was way easier to optimize with heuristics, so that’s where I went next.

The simple heuristic I used for finding a loss function is the sum of:

With the appropriate weights, this meant breadth-first would explore short solutions with lots of flexibility and progress towards locking in all cards first, and indeed this helped cut the search time down a lot.

After running this solver on thousands of games, I found that about 99% of games are solvable. However, some solutions take more than a thousand steps, and exhaustively proving that a game is not solvable sometimes means exploring millions of boards.

Computer Vision

Entering games into the CLI manually is quite tedious. When I was looking into alternatives, I couldn’t find a good way to get information about games out of the mobile app. The most obvious way, and the only thing that worked in the end, was to take screenshots.

Now, fortunately, Apple has blessed us with the Shortcuts app. So, taking a screenshot and sharing it to a shortcut, which then sends it to a server, was pretty quick to set up.

Identifying boards and cards on the server was challenging due to different screen sizes and slightly different colors across phones. But throwing good old OpenCV pattern recognition into the mix solved it after a bit of iterating. This is not the cleanest solution ever, but collecting a bunch of board screenshots and turning them into unit tests has made me fairly confident.

Unfortunately, this does bloat the final container size for the server a bit, but nothing too dramatic.

End-to-End

Here’s a quick demo of me trying very hard to throw this game. Even after locking up all three dragon slots, in my first three moves, the solver finds a solution, which I promptly ruin to make the game unsolvable.

Check Out the Source!