Artificial Intelligence:

Constraint Satisfaction Problems Consider the problem of coloring each node of this 13-node graph with one of three colors (R, G, B):

c) AC-3. Explain in your own words how to use a table to store coloring constraints and show how it is updated using the AC-3 algorithm for the above graph. Give enough details to distinguish AC-3 from forward checking. d) 3-Coloring. Show that the graph is 3-colorable by finding a 3-coloring consistent with part (b). (Deciding 3-colorability, i.e., whether a graph is 3-colorable, is actually NP-complete.) You need not use any of the above heuristics, but they should help.

Please help, I will upvote your answer.

Transcribed image text