Suppose that, we are looking at a map of Australia showing each of its states and territories (figure below). We are given the task of coloring each region either red, green, or blue in such a way that no neighboring regions have the same color. How many solutions are there for this map-coloring problem?

Tasmania