Solving Sudoku in Python
This is a great article about solving sudoku in python. Peter Norvig is a director of research at google and looks to be a pretty smart cookie.
I've toyed with writing a sudoku solver in python and the first part of his code mirrored closely to what I was thinking. Build a set of dictionaries where given a cell you can find all the other cells that constrain it (what he calls units and peers).
Naming the cells A1, A2 like an excel spreadsheet is very smart and I hadn't though of that (2D arrays are a pain in Python). Putting all the possibilities in each cell (i.e. "123456789") to start and eliminating impossible values as you set the givens is brilliant.
In fact, it's so brilliant that I had a hard time following the generator expressions and list comprehensions despite being very comfortable with them. Also, Peter's lisp heritage shows throughout his code.
The part that confuses me is where he picks the most constrained cell (for example one that has only two possible values) and works on that. This is what I would do when playing sudoku by hand, but it isn't clear that this method would solve every puzzle. But doing this does radically improve the speed of the program, and mirrors more closely how a human would play.
All in all it's very cool example of what you can do in a 100 odd lines of Python code.
I've toyed with writing a sudoku solver in python and the first part of his code mirrored closely to what I was thinking. Build a set of dictionaries where given a cell you can find all the other cells that constrain it (what he calls units and peers).
Naming the cells A1, A2 like an excel spreadsheet is very smart and I hadn't though of that (2D arrays are a pain in Python). Putting all the possibilities in each cell (i.e. "123456789") to start and eliminating impossible values as you set the givens is brilliant.
In fact, it's so brilliant that I had a hard time following the generator expressions and list comprehensions despite being very comfortable with them. Also, Peter's lisp heritage shows throughout his code.
The part that confuses me is where he picks the most constrained cell (for example one that has only two possible values) and works on that. This is what I would do when playing sudoku by hand, but it isn't clear that this method would solve every puzzle. But doing this does radically improve the speed of the program, and mirrors more closely how a human would play.
All in all it's very cool example of what you can do in a 100 odd lines of Python code.
Comments