I have to solve the Map Coloring (Graph Coloring) problem using Arc-Consistency 7 Algorithm.

So far i managed to solve it using Backtracking only. I don't know where to start to do it with the AC-7 algorithm.

Any idea might help. You can see what I've did so far here, I implemented it in C but you can explain it in mostly any programming language, I want to understand the idea behind it.

#include #include

#define V 5

void printSolution(int color[]);

bool colorCheck (int v, bool graph[V][V], int color[], int c) { for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true; }

bool mapColoring (bool graph[V][V], int m, int color[], int v) { if (v == V) return true;

for (int c = 1; c <= m; c++) { if (colorCheck(v, graph, color, c)) { color[v] = c;

if (mapColoring(graph, m, color, v+1) == true) return true;

color[v] = 0; } }

return false; }

bool startMapColoring(bool graph[V][V], int m) {

int color[V]; for (int i = 0; i < V; i++) color[i] = 0;

if (mapColoring(graph, m, color, 0) == false) { printf("Solution does not exist"); return false; }

printSolution(color); return true; }

void printSolution(int color[]) { printf("Solution Exists:" " Following are the assigned colors "); for (int i = 0; i < V; i++) printf(" %d ", color[i]); printf(" "); }

int main() { bool graph[V][V] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 1, 0, 0} }; int m = 4; startMapColoring(graph, m); return 0; }