Island Hopping

In the grid world of Kara there are "islands", each one represented by a single tree. Between any pair of island, there is at least one empty square, meaning they do not touch each other, not even diagonally. Two islands are called neighbors if their relative location is like that of a knight's jump in chess. The following image shows all possible neighbors of the center island:

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.

Problem 1: Program Kara so that, when started on a square next to an island, he will visit (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?

Problem 2: Modify the program to problem 1 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.

Problem 3: Having learned to explore an archipelago, Kara aims to explore the entire ocean of his toroidal world. 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. If Kara is deterministic, can you guarantee that Kara eventually discovers every archipelago? Experiment with the non-deterministic version of Kara to solve this problem.