Some time ago, I wrote a Sudoku solver in Java, along with an editor, interactive hint mode, puzzle generator etc, but the project never got finished because of feature creep and I generally got a bit bored of it all.

This morning, I resurrected the project and implemented the solver in PowerShell.

It’s not the shortest solver in history as it has gone through some performance improvements, but it does work and unless you’ve got a really hard puzzle, it’s quite quick too.

Download the script from here: sudoku.ps1

There are sample puzzles here (simple) and here (very hard). They are simple text files with numbers separated by white space. A zero indicates a blank in the puzzle.

You run the script like this:

PS > ./sudoku.ps1 sample-puzzle.txt
Going to to try to solve this puzzle:
7 . 5  . 3 .  8 . 2
. . 2  8 . 1  4 . .
8 1 .  . . .  . 5 6

. 3 .  1 . 8  . 2 .
. . 1  . 7 .  9 . .
. 9 .  3 . 2  . 4 .

9 8 .  . . .  . 3 7
. . 3  9 . 4  5 . .
2 . 6  . 8 .  1 . 4

Solved!
Guesses 53 (9 were wrong)
Elapsed time 00:00:00.4850316
Result:
7 4 5  6 3 9  8 1 2

3 6 2  8 5 1  4 7 9
8 1 9  2 4 7  3 5 6

4 3 7  1 9 8  6 2 5
6 2 1  4 7 5  9 8 3
5 9 8  3 6 2  7 4 1

9 8 4  5 1 6  2 3 7
1 7 3  9 2 4  5 6 8
2 5 6  7 8 3  1 9 4

I welcome any hints on performance or algorithmic improvements. No C# inlining please, it’s a PowerShell project 🙂

The very hard puzzle above takes a very long time to solve. So long, in fact, that I gave up waiting for it. If there is anyone out there with space time and cpu cycles, please run it and let me know how long it takes 🙂

Update: I’ve heard from one person that it takes approx 1.2 days to solve. My original Java app, in contrast takes 4.1 seconds.

Update 2: It looks like I inspired Mark Sheppard to do a better job (ie, not brute force). His PowerShell script solves the hard puzzle in 12 seconds (9.3 seconds on my Mac). Well done!