Project 2 – CSP – Graph Coloring

You are given a graph in the form of a text file, that you are supposed to color.  The proper vertex coloring is such that each vertex is assigned a color and no two adjacent vertices are assigned the same color.

Input Format

# Everything that starts with # is a comment

# First non comment line is of form Colors = n

Colors = 3

# Here comes the graph

1,3

2,18

3,19

2,19

# The “graph” presented above has 5 vertices: “1”, “2”, “3”, “18” and “19”, and 4 edges.

# Only the edges are provided in terms of first vertex and second vertex

# Edges are undirected: 1 is adjacent to 3, and 3 is adjacent to 1.

# In some graphs, the edge may be included twice (1,3) as well as (3,1) – just ignore the second one.

Example Inputs

Some example problems can be found at:

https://github.com/amrinderarora/ai/tree/master/src/main/resources/csp/coloring

Algorithm

Write a CSP algorithm to solve this problem.  The CSP algorithm should have the following components:

  • Search algorithm to solve the CSP
  • Heuristics (min remaining values, least constraining value, tie breaking rules)
  • Constraint propagation using AC3.