Site pages

Current course

Participants

General

1 April - 7 April

8 April - 14 April

15 April - 21 April

22 April - 28 April

29 April - 5 May

6 May - 12 May

13 May - 19 May

20 May - 26 May

27 May - 2 June

3 June - 9 June

10 June - 16 June

## 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