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

1. 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.

2. 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.

3. 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.

4. 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.