For this assignment you will solve the classic Four Color Problem using backtrack search, or, backtracking. The backtrack process is inherently repetitive, and you will implement that repetition using both iteration and recursion.

• Make IterativeMapColorer.java, which inputs a map description file and either (a) outputs a legal coloring for it, or (b) outputs that it is impossible to do so. Your program must employ iterative backtracking; it will be invoked with the command

            java IterativeMapColorer < mapdescriptionfile

  where mapdescriptionfile is a text file that describes the map. In particular, the first line of a map description file will contain the number of countries in the map (a positive integer), and each remaining line will contain a pair of distinct, positive integers, separated by one or more spaces, indicating a pair of countries that happen to be adjacent. (For the specifics of how to do standard I/O in Java, refer to Doing Standard I/O in Java.)
• Make RecursiveMapColorer.java, which solves the same problem using recursive backtracking. It will be invoked like this:

            java RecursiveMapColorer < mapdescriptionfile

• Extra Credit: Make IsMapColorable.java, which inputs a positive integer, n (via args[0]), plus a map description file (via standard input, as above), and outputs either (a) a legal coloring for the map using at most n colors, or (b) a message saying that the map is not n-colorable. For example, to see if the map in file europe is five-colorable, you would do this:

            java IsMapColorable 5 < europe

Revised: April 14, 2009