“Captain Literal”.NET

I’ve been obsessed since Adrian (ps1.soapyfrog.com) posted his Sudoku solving PowerShell script a couple of weeks ago. When I first read his post on the subject, I pulled down his script and ran it - at the time he didn’t know how long it would take to solve the harder of the two puzzles he posted - after about an hour PowerShell had crashed on my computer! Since then Adrian has posted saying that his script takes 1.2 days to solve his harder puzzle!

Having peeked at his script I quickly discovered that it works on a brute-force principle (i.e. if you don’t know what number you should have in a square, guess), this seemed to work well for the easier of his samples (solved in less than a second). I decided that I’d see if I could do better and learn a few things along the way. And so started my obsession with implementing a speedy Sudoku solver in PowerShell – this shouldn’t have taken two weeks, but work, life and a couple of other things got in the way. I swear, I don’t know how people play with technology and constantly post about it.

To start with, I had no idea how to solve a Sudoku puzzle with a computer, yet alone in PowerShell – Enter a trusty search engine to the rescue. I quickly found Andrew’s Sudoku solver. Now, what’s interesting about Andrew’s site is that he not only solves Sudoku, he shows you step by step how to do it and he’s published over 30 different strategies for solving Sudoku, complete with pictures. J

Armed with details of how to solve Sudoku, I set about scripting it and making it perform better than the couple of minutes it took when I first solved the problem. In the end I got the script to solve Adrian’s hard puzzle in 12 seconds – not bad! For a comparison I ported the script into C# and got it to solve the same puzzle in less than 0.1 seconds. Now, I know that PowerShell isn’t designed for processing performance, but rather admin performance, but it’s important to know the limits of a piece of software so you can get the right tool out of the toolbox when you need it. The C# port was written as a static and I just invoked it directly from within PowerShell and has the exact same output as from a .ps1 script – I could just have easily written this as a cmdlet.

Fortunately, I only had to implement a few of the “basic” strategies described on Andrew’s site to solve the harder puzzle – some of the advanced strategies didn’t look like they’d be fun to implement. I’ve taken this script as far as I want to take it and learnt a lot about PowerShell and the way it works. My lessons and observations will form the thesis of a blog post to follow in the next few days.

In the meantime, here’s my solve-sudoku script, Adrian’s original simple puzzle and his original hard puzzle for you to play with. Just execute the script specifying the puzzle to solve as an argument (.\solve-Sudoku.ps1 profile-puzzle.txt)

Filed under: PowerShell