Nel mondo a griglia di Kara ci sono delle isole, ognuna rappresentata da singoli alberi. Tra ogni paio di alberi c'è al massimo una cella vuota, il cui significato è che non si toccano tra di loro, e ciò però non accade quando sono messi in diagonale.Due isole sono dette "figlie" se la posizione del loro "parente" è tipo quella che può avere un Alfiere negli scacchi. La seguente immagine illustra tuti i possibili "figli" dell'isola centrale:
Un numero massimale di isole tali che uno possa nadare da un'isola verso tutte le altre nello stesso insieme è chiamata arcipelago. Un arcipelago può essere rappresentato come un grafo connesso i cui nodi sono isole e i cui vertici siano paia di filgi. Una sequanza consecutiva di vertici che porta indietro al nodo di partenza è detto ciclo. Un grafo senza cicli è detto albero.
Problema 1: Programma Kara in modo che, quando parte da un quadrato vicino un'isola, lei visiti (tocca) tutte le isole dell'arcipelago il cui grafo è un albero. Se il grafo ha cicli, cosa si può dire della perte dell'arcipelago che il tuo programma ha visitato?
Problema 2: Modifica il programma del problema 1 in modo che Kara lasci una traccia fatta di quadrifogli che copra tutte le celle che attraversa, e si fermi quando ritorna alla cella i partenza.
Problema 3: Avendo imparato ad esplorare l'arcipelago, Kara vorrà esplorare l'intero oceano del suo mondo "toroidale". Per questo obbiettivo molto affascinante, Kara è abilitata a paizzare ed eliminare i quadrifogli per segnare e non segnare le celle. L'idea generale è che, qando Kara ha finito di visitare l'arcipelago, lei possa navigare verso il mare aperto, sperando di scoprire nuovi arcipelaghi che non ha visitato prima. Se Kara è deterministico, puoi garantire che Kara eventualmente scopra tutti gli arcipelaghi? Sperimenta con una versione non-deterministica di Kara per risolvere il problema.