Solving Sudoku with awk

awk is a fun and powerful language available in the command-line of Linux, Mac OS X, and even Windows (with a little help from Cygwin). In fact, our own Dale Dougherty co-authored one of the classic books on awk (and sed, another great Unix power tool) back in 1990 (the second edition was released in 1997), sed & awk.

At The Geek Stuff, Bill Duncan has posted a fun awk program that can solve Sudoku puzzles:

The application I chose to use as an example is “yet another sudoku puzzle solver”. I must confess at the outset that I have never sat down to solve one of these puzzles myself, but sketched this out over a few days while commuting on a train and watching other people work on them. It was far more fun I think than actually doing any of the puzzles..

[…]

This program uses a very simple depth-first recursive backtracking algorithm with up-front and ongoing elimination of invalid entries. Awk may not have the expressive power for representing complex data that perl or other languages have, but with care, many moderate sized problems and data sets can be used. This algorithm may not be the best one around, but it is certainly fast enough for most problems and is easy to implement.

When you strip out blank lines and comments it’s only 67 lines! Keeping in the awk spirit, that would be:

awk '!/^[ t]*#/ && !/^$/' solve.awk | wc -l

Yet Another Sudoku Puzzle Solver Using AWK

If you need to generate some puzzles to throw at it, try this Sudoku Generator written in Python.