ColoringProblem

AIGuy.org

This applet solves the coloring problem, i.e. assigning colors to a number of regions and adjacent regions cannot have the same color. Famous examples are coloring the territories of Australia (simple) or the 50 states in USA (quite complex). The coloring problem is known as a Constraint Satisfaction Problem (CSP) and the applet can be used to compare the most common algorithms for solving CSPs.

The following algorithms are implemented:

  • Breadth-First and Depth-First search (for comparison)
  • Backtracking Search
  • Forward Checking
  • Min-Conflicts local search

 

Backtracking Search and Forward Checking can also use the following heuristics:

  • Minimum Remaining Values (MRV)
  • Degree Heuristics (DH)

 

Coloring Problem