The somewhat vaingloriously named DeewiantSudoku is a Sudoku (Wikipedia article) solver I wrote back in 2006. I was intrigued by the solving techniques discussed at places such as the Sudoku Programmers forum and decided to try my hand at programming them; a plain brute-force solver would have been uninteresting. (I did eventually add brute-forcing support to DeewiantSudoku, though.)
With its array of solving methods, I expect that DeewiantSudoku will be able to solve just about any puzzle you’ll run into in a newspaper, or wherever it is you get your Sudoku fix. Books of “hard puzzles” might stump it though, since these techniques are probably quite well-known by now.
Example
As an example, let’s try DeewiantSudoku on the following interesting puzzle (displayed as ASCII art because I’m lazy; this way you can paste it directly into DeewiantSudoku, though):
..3|..4|..9
...|.7.|.5.
2..|6..|8..
---+---+---
..9|...|..4
.4.|...|.3.
8..|...|7..
---+---+---
..4|..3|..2
.2.|.6.|...
7..|8..|6..
Here’s a snippet of DeewiantSudoku’s output with the --explain flag passed:
Cells [B3], [B9] must contain 1, 6; eliminated 2 such candidates in row B.
Found an XYZ-wing among [A1], [B3], [A4] for 1; eliminated 1 candidate for 1.
Found a Jellyfish among [C2], [C3], [C6], [F3], [F6], [F9], [H6], [H9], [I2], [I3] for 5; eliminated 5 candidates for 5 in columns 2, 3, 6, 9.
Found a Jellyfish among [A1], [D1], [E1], [A4], [E4], [A5], [D5], [E5], [G5], [A7], [D7], [G7] for 1; eliminated 6 candidates for 1 in columns A, D, E, G.
It seems it’s doing something pretty clever to find the final solution! (Yes, those are actually real names for Sudoku solving techniques.) I won’t spoil the solution for you here, in case you’re the type who would care about that. Here are the statistics the program outputs:
Solve time: 5 ms
Iterations: 36
Methods used:
Naked singles: 34
Hidden singles: 25
Jellyfish: 2
XYZ-wings: 1
Naked pairs: 1
5 methods used.
As you can see, it didn’t need to guess and backtrack, which is what most solvers do. (Some are more clever and use algorithms like Dancing Links (Wikipedia article); in any case my point is that the fact that such solvers solve Sudoku is incidental; their algorithms are more generic and not the way a human would solve the puzzle.)
This is not the kind of puzzle you’d see in a newspaper, at least not where I’m from: even naked pairs, a much simpler technique than jellyfish or XYZ-wings, tend to rank a puzzle to some kind of “very hard” or equivalent difficulty level, in my experience.
Downloads
The latest version, 3.0.0 alpha 1:
- Changelog
- Windows binary (PE, x86):
- Linux binary (ELF, x86):
- Linux binary (ELF, x86–64):
- Source:
Warning! The above version seems to use memory quite heavily on Sudokus bigger than 9*9. If you have problems, try 2.1.0 (it calls itself 2.0.2 but that’s just a bug):
- Linux binary (ELF, x86):
- Linux binary (ELF, x86–64):
- Source:
Sorry, no Windows binary for this one. Ask if you need one.
Historical note
I meant to refactor the whole thing and add more interesting techniques than the ones supported in the release above, but never got around to it, moving to CCBI instead. The latest release (the only public one) dates back to August 2008. I still consider this unfinished and may return to it in the future. Until then, it stands as it is: buggy and incomplete but not useless.
Compiling
DeewiantSudoku is written in the D programming language. It was written prior to the 1.0 release, back when Tango didn’t exist, and thus uses the Phobos library supplied with the DMD and GDC compilers. I’ve managed to build 3.0.0 alpha 1 with GDC 0.24 successfully on Linux. For Windows users, DMD 0.164 can build it since that’s what I’ll have used when developing it. Newer versions may or may not work. (Remember to enable deprecated features with the -d flag!)