HW 4 Sample Solution
Homework 4: Sudoku solver using graph coloring
Bart Massey 2014-06-04
I chose to implement the Sudoku solver for this problem in
Python, and to add a Sudoku generator using the same
underlying code as well. You can find the implementation at
http://github.com/BartMassey/sudoku .
Two different graph representations are used for
convenience. The graph is created as an edge list, including
only the edges from lower to higher numbered vertices. The
graph is then converted to an adjacency list for the
colorer. The graph generator proceeds by unioning together
the 9-cliques representing the various rows, columns and
boxes.
The colorer uses simple depth-first search with dynamic
most-constrained-first vertex ordering and static priority
coloring. It is capable of being called to produce one
solution, a specified number of solutions, or all
solutions. Being able to ask whether there are two different
colorings is useful for the generator. Being able to ask
how many solutions there are is useful for checking the
correctness of the puzzle and solver.
Not much testing has been done on this code. However, it
does solve the two sample instances, given in the homework,
one of which was generated using it.
The code executes nearly instantaneously on the sample
instances. Benchmarking should be done to indicate how much
the heuristics affect performance. In addition, it would be
nice to look for harder problems online and evaluate the
performance on these as well.
Bart Massey 2014-06-04
I chose to implement the Sudoku solver for this problem in
Python, and to add a Sudoku generator using the same
underlying code as well. You can find the implementation at
http://github.com/BartMassey/sudoku .
Two different graph representations are used for
convenience. The graph is created as an edge list, including
only the edges from lower to higher numbered vertices. The
graph is then converted to an adjacency list for the
colorer. The graph generator proceeds by unioning together
the 9-cliques representing the various rows, columns and
boxes.
The colorer uses simple depth-first search with dynamic
most-constrained-first vertex ordering and static priority
coloring. It is capable of being called to produce one
solution, a specified number of solutions, or all
solutions. Being able to ask whether there are two different
colorings is useful for the generator. Being able to ask
how many solutions there are is useful for checking the
correctness of the puzzle and solver.
Not much testing has been done on this code. However, it
does solve the two sample instances, given in the homework,
one of which was generated using it.
The code executes nearly instantaneously on the sample
instances. Benchmarking should be done to indicate how much
the heuristics affect performance. In addition, it would be
nice to look for harder problems online and evaluate the
performance on these as well.
Last modified: Thursday, 5 June 2014, 12:39 PM