Python Coding Project

Constraint satisfaction problems (CSP) - Map Coloring A ? k -coloring of a map is an assignment of ? k colors, one to each country, in such a way that no two countries sharing a border have the same color. This problem can be translated to a constraint graph. A coloring of a graph G assigns a color to each vertex of G, with the restriction that two adjacent vertices never have the same color. The chromatic number of G, written χ(G), is the smallest number of colors needed to color G. In this project, we will experiment with map coloring techniques and compare the observed results in the context of USA and Australia maps. Compute the chromatic number of USA and Australia map. Experiment with both maps using the following methods [without heuristics] Depth first search only Depth first search + forward checking Depth first search + forward checking + propagation through singleton domains Experiment with both maps using the following methods with heuristics where the order of variables needs to be defined in the following order MRV, Degree Constraint, and Least Constraining Value Depth first search only Depth first search + forward checking Depth first search + forward checking + propagation through singleton domains Present the results in a tabular format the number of backtracking happened and the time required to compute the result.