// Fargelegging av et kart, ikke et komplett program

public class uke_7_4
{
    // Fargelegging av et kart med n land.
    // Antar at landene er nummerert fra 0 til n-1
    // Genererer her *alle* lovlige fargelegginger med 4 farger.
    // Et forslag til smartere avskjæring er skissert under selve
    // programmet.

    int n;              // Antall land som skal fargelegges
     
    boolean felles[][]; // n x n tabell med info. om felles grenser
                        // Antar at tabellen er riktig utfylt
                        // på forhånd, slik at felles[i][j] == true
                        // hvis land nummer i og land nummer j har
                        // felles grense.

    int farge[];        // Tabell av lengde n. Alle lovlige
                        // fargelegginger lagres i tabellen "farge",
                        // slik at land nummer i har "farge[i]".

    void fargelegg(int land)
    {
       // Når denne funksjonen kalles skal alle landene fra og med nummer 0
       // til og med nummer "land-1" ha en lovlig farge. Funksjonen finner
       // alle lovlige fargelegginger av de resterende landene fra og med
       // land nummer "land"  til og med land nummer "n-1".

       if (land == n - 1)
       {
	   // Bunn i rekursjonen, alle landene er fargelagt
	   bruk_fargelegging();
       }
       else
       {
	   int f, nabo;
	   boolean brukt[] = {false, false, false, false};

	   // Finner ut hvilke farger som allerede er brukt av naboland

	   for (nabo = 0; nabo < land; nabo++)
	       if (felles[land][nabo] == true)
		   brukt[farge[nabo] - 1] = true;

	   // Prøver med alle lovlige farger for dette landet

	   for (f = 1; f <= 4; f++)
	       if (brukt[f - 1] == false)
	       {
		   farge[land] = f;
		   fargelegg(land + 1);
	       }
       }
    }
    
    void bruk_fargelegging()
    {
	  // Denne metoden kan f.eks. skrive ut en fargelegging
    }

     // En ekstra avskjæring som kan brukes, er at vi hver gang vi
     // prøver å sette en farge på et land også sjekker om dette vil
     // føre til at noen av de landene som vi ennå ikke har sett på,
     // ikke lenger får noen mulig farge som det selv kan ha. Hvis vi
     // gjør denne sjekken hver gang vi velger en farge, så behøver vi
     // bare sjekke dette for de ufargede landene som er naboland til
     // det vi nå satte farge på. Bare disse kunne jo miste den
     // evt. siste fargemuligheten på grunn av det fargevalget vi
     // gjorde.
     //
     // Legg inn denne ekstra avskjæringen i programmet selv!
}