To demonstrate the concept of [Constraint Satisfaction Problems](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem (CSP) using four different techniques but which will be combined in three different ways to produce interesting results.

1. Depth First Search Only

2. Depth First Search with Forward Checking

3. Depth First Search with Forward Checking and propagation through singleton domains

To demonstare CSP we will be applying the concept on coloring the states of two countries i.e. United States of America and Australia. The aim is to only use four colors to color the fifty states of the US and 3 colors to color the 7 states of Australia. The consraints are that the colors should be applied to states in such a wat that the same colors are NOT applied to the same state.

The project uses heuristics to help narrow down the color to apply to each states before hand so that when the final color is applied all states have the correct color applied. The foilowing heurisitc approaches are used:

1. Minimum Remaining Value (MRV): This approach requires that a color already applied from an existing set of colors (in the case of the US, four and in the case of Australia, three)
2. Degree Constraint: This approach focusses on states having the most number of adjacent states to ensure that those are prioritised during color assignment.
3. Least Constraining Value (LCV): This approach focusses on states having the least number of conections and the least number of adjacent states and those are priorotised for color assignment.

The purpose of using so many heuristic approaches is to calculate which is the more efficient approach whole taking the least amount of time.

1. Python 3

2. Juputer Notebook

3. Basemap Library