Q$2.(8$p$)$ A map of a part of central Europe is shown in the figure.

Use backtracking search with most$-$constrained$-$variable heuristics and Arc Consistency Checking to

color this map using four colors $(R,G,B,Y).$ Is it possible to color the map with three colors? Can you

prove that it is impossible? Hint: Color Austria first.Q$1.(8$p$)$ The Traveling Salesman Problem $($TSP$)$ is a challenge to the salesman who wants to visit every

location exactly once and return home, as quickly as possible. Each location can be reached from

every other location, and for each pair of locations, there is metric that defines the time between them.

Given the following graph

your task is to use gradient descent to improve on the original loop, i$.$e$.$ find a loop with a lower cost.

Note that at each step the method should identify the pair of edges whose endpoints can be switched to

improve the loop. The switching is done in the following manner. Given the loop $a_1,a_2,a_3,a_4,a_5$dots,$a_n,a_1$

the edges which do not share a node can be switched, for example switching the edges $(a_1,a_2)$ and

$(a_4,a_5)$ we obtain a new loop $a_1,a_4,a_3,a_2,a_5,dots{a}_n,a_1.$

Start with the loop $($Medford Belmont Everett Arlington Cambridge Somerville Medford$)[$or $($M B E

ACSM $)$ for short$].$ You should stop when the loop cannot be improved anymore.