I had posted here already here to forum a beautiful code for solving Sudoku puzzles, so I was in kind of dilemma what to do, as I read the task to do a sudoku solve as one task in Project Euler.
To use the code from before and just take the correct corner numbers or really do something from cratch by myself?
I decided to do both. So I took the right answer from the super fine solver and entered the forum to see what kind of solutions the early posters had done for the task. I took as bench mark one Python code, which ran for around 25 seconds for the 50 Sudokus.
So I desided to take a filosophical stance and prove how stupid the sudoku solver can come and still solve all puzzles and reasonably give up for impossible ones.
My code is using only one method, no precomputed neighbour coordinates or localized propagation of values to keep as different as possible from the other solution.
Algorithm "Find the nail for the hammer" Take alternative from stack (initialy the start position) Stop if found solution. Find the minimum length set of undesided values (typically two alternatives) Assign the values possible to this place one by one and keep the alternatives which did not lead to immediate conflict Push the correct alternatives to list used as stack. Return to beginning.
So the idea was to be as different from original advanced Sudoku solver as possible, but still I wanted to solve the Sudokus reasonable speed vs the 25 s bench mark solution (the advanced solution with double recursive constraint propagation takes all of 0.02 s per puzzle ie 1 s for 50).
Here is my code. One interesting point of this solution is that it solves the very hard random puzzles of Norvig also and that this program is really much faster with the Python 3.2rc2 thant with Python 2 including 2.6.6 with psyco module.
Finally the solution is reasonable fast, little under 8 seconds in my old computer with Python 3.2rc2, 12+ s with Python 2.6, one second slower than Python 3.2rc2 with Python 2.7.1.
If you want to speed it up little you can change the definition of possibilities to do inline the 2d array index calculation:
def possibilities(s): s = [value if len(value)==1 else '.' for value in s] return itertools.takewhile(lambda x: x, (''.join(sorted(remaining_neighbours(s, i, j))) if s[i * 9 + j] in '.0' or len(s[i * 9 + j]) > 1 else s[i * 9 + j] for i in range(9) for j in range(9)))