Evening Projects - Coding Up A Solitaire Solver
After getting in deep with the Zachtronics Solitaire Collection, I got it into my head that it must be easy enough to solve with a bit of recursive programming - Try a move, check if it's good, see what moves are possible, etc, etc.
So after work today I gave it a crack, and now 6 hours later I have a Python script that... just kind of works? I don't really know what to do with this.
I've got dozens of these "how hard could it be?" coding projects sitting on my hard drive, all of them started with the best of intentions and left hanging like my head, disheartened. I genuinely stopped expecting these things to do what I tell them, fully expecting them to collapse in a sea of complexity.
I think this one worked because I approached it starting from the idea that I knew it'd be hard to debug, so I'd best start with the ability to visualise things. I wrote a couple of tidying functions to show the board state (in colour!) without any of the cruft my algorithm relies on - just the letters. This meant I could spot weird looping behaviour just by watching it solve, and this let me stamp out a couple of bugs in minutes rather than hours.
| This is not the code of an organised mind
Not to say this is good code! It's trash, and absolute mess. The last problem I had to solve - a deep recursion of not-quite-identical states the algorithm kept trying - was put to bed by just randomising the order of the moves it tries. This took it from an infinite loop that couldn't move forward to an extremely messy process that kind of can't miss if a solution is possible.
It solves randomly generated deals (if they can be solved) in a minute or so, and the one board from the game that I tried solves in under a second - I suspect they ranked the random seeds they made in difficulty and only put the easiest ones in the game.
I have a couple of other things I want to do with this before I post about the code itself:
- Process screenshots for input using an OCR library
- Come up with some heuristics to estimate difficulty, then test them against the algorithm's solve time.
- I'd like a way to visualise all the different moves the model tried, and attempt to show depth and "richness" of solutions with it. I have some ideas, but that's a ways off for now.