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.

Submission

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