## HW 4: Graph Coloring Sudoku Solver

# CS 584/684 Homework 4: Graph Coloring, State-Space Search

Bart Massey

Due Thursday 5 June 2014 before class

In this assignment (suggested by Simon Niklaus), you will build a Sudoku solver using graph coloring. The basic idea is that each cell in the Sudoku can be thought of as containing a color number from 1..9, and the constraints between colors are given by an "interference graph" that does not allow the puzzle constraints to be violated. Thus, a valid 9-coloring of the graph corresponds to a solution.

You may use any reasonable programming language, but keep in mind that other students are grading your assignment.

Build a function that constructs the interference graph for 9x9 Sudoku. Use any graph representation you like. The graph should have a bunch of 9-cliques in it, corresponding to the places that need to be all different.

Build code to "prime" the interference graph with a Sudoku puzzle given on standard input, by fixing the starting colors of some of the cells. The format of the puzzle will be 9 lines of 9 characters, each terminated with an ASCII Carriage Return + Line Feed to mark the end of the line. Each character will be either a digit or a "." if the cell is blank.

The example puzzle from Wikipedia looks like

`53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79`

and is contained in a problem file here. The solution is

`534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179`

contained in a solution file here.

Build a graph 9-colorer using state-space search. You can use local search or complete search as you prefer. Don't get too fancy, as these problems are pretty easy.

Use your graph 9-colorer to solve the following problem created by me and available in a problem file here.

`......3.7 ..6.9.... 3..4.5..9 ....2..5. 53..1.... .2.3.4.7. ..7...56. .6...8... .8.2.....`

### Format

You may use any reasonable programming language. Keep it as simple as possible though, as other students have to execute and grade it. It is advised to write a summary that follows the usual format rules. Feel free to use a Zip container to upload your files.

### Submission

Submission is through http://crossgrade.svcs.cs.pdx.edu.