Island Hopping
In the grid world of Kara there are "islands", each one represented by a single tree trunk. We are interested in finite state machines (programs) that send Kara on a voyage to visit many islands, under some assumptions on the relative location of the islands in the ocean. In order to state this problem precisely we introduce some standard mathematical concepts.
The Manhattan distance between two grid squares (x, y) and (x', y') is defined as |x - x'| + |y - y'|. We assume that the distance between any pair of islands is >= 3. Two islands (x, y) and (x', y') are called neighbors iff their relative location is like that of a knight's jump in chess, i.e. |x - x'| = 2 and |y - y'| = 1, or |x - x'| = 1 and |y - y'| = 2.
A maximal set of islands such that one can go from any island to any other in the same set is called an archipelago. An archipelago can be represented as a connected graph whose nodes are islands and whose edges are pairs of neighbors. A sequence of consecutive edges that leads back to the starting node is called a cycle. A graph without cycles is called a tree.
(a) [10 points] Program Kara so that, when started on a square next to an island, willvisit (touch) all the islands of any archipelago whose graph is a tree. If the graph has cycles, what can you say about the part of the archipelago your program will visit?
(b) [10 points] Modify the program a) so that Kara lays down a trace of clover leaves covering every square he has traversed, and stops when he returns to the starting square.
(c) [5 bonus points] Having learned to explore an archipelago, Kara aims to explore the entire ocean of his toroidal world (the world is a Torus: when Kara gets beyond a border of the grid, he automatically reappears on the opposite side). For this challenging task, Kara is allowed to place and pick up clover leaves to mark and unmark any square. The general idea is that, when Kara has finished visiting one archipelago, he sails out into to open seas, hoping to discover new archipelagos he has not visited before. Can you guarantee that Kara eventually discovers every archipelago?