Given a map with six regions that needs to be colored with three colors it is very trivial to find the total number of map colorings including illegal solutions (i.e., two adjacent regions have the same color).
$T=3^6=729$
What is an effective method to calculate the total number of legal solutions (i.e., no two adjacement regions have the same color)?