Stream-based sudoku solver

A friend of mine was talking about a sudoku solver he'd written in python as an programming challenge, and confessed that Peter Norvig's version was more elegant, in part because he used generators. Python generators are infinite streams -- so this sounded like something I could tackle with Aqueduct.

I though a bit about how to solve Sudoku using streams (I didn't want to cheat and actually read PN's solution before trying it myself). Basically, I reasoned that I could use streams to brute force a solution in the same way I did for the N-queens solver. Each one of the 9 x 9 cells in the sudoko board would be its own pipeline stage. It would combine a stream of all valid input boards with all possible values of that cell, filter out invalid moves, and pass new boards on to the next cell.



It turned out to be pretty easy to adapt from the N-queens example (ordinarily I don't like to cut-and-paste code, but when I'm writing samples I do because I don't want to have some shared 'board game' library).  Much as the n queens solver had combined candidates, filtered invalid moves and accepted new boards, we could do the exact same thing here.  The only difference was in what was considered a valid move. The code is pretty simple -- about 70 lines of code (not including a board printer, comments, and boilerplate).

I first tried an "Easy" sudoko from my "Enjoy Sudoku Daily" iPhone app:

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

My solver was able to tackle this in under 30 seconds:

-------------------

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

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

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

-------------------

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

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

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

-------------------

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

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

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

-------------------

For a "fiendish" puzzle, it took 29 minutes for an exhaustive search...not great, sure, but considering this is a brute-force algorithm and hadn't been tuned, this is still a pretty nice result.