Algorytm rekursywny dla czterobarwnego twierdzenia

Question

Problem polega na zastosowaniu mapy podzielonej na regiony wyrażonej w macierzy sąsiedztwa i przy użyciu czterech kolorów, kolor mapy tak, aby żadne dwa przylegające regiony nie miały tego samego koloru. Będziemy używać matrycy przyległości do kodowania granic regionu, na którym innym obszarze. Kolumny i wiersze macierzy są regionami, podczas gdy komórki zawierają 0, jeśli dwa regiony nie sąsiadują ze sobą, a granice 1, jeśli mają granicę . Utwórz rekurencyjne rozwiązanie do przechwytywania, które akceptuje jako interaktywne dane wejściowe od użytkownika liczbę regionów na mapie i nazwę macierzy sąsiedztwa wyrażającą makijaż mapy.

Problem, na który napotykam, polega na tym, że pierwsza wartość w countryColor została zmieniona, ale wiele wartości w tablicy nigdy się nie zmienia.

private static final int[] color = {1,2,3,4}; 
//this color array is meant to represent 4 colors like red, blue, green, orange etc. 

private static int[][] map = {{0,1,1,0,1,1,0},{1,0,0,1,1,0,1},{1,0,0,1,1,1,0},{0,1,1,0,1,0,1},{1,1,1,1,0,0,0},{1,0,1,0,0,0,1},{0,1,0,1,0,1,0}}; 
//this is the adjacency matrix showing which countries are next to each other 

private static int[] countryColor = new int[7]; 
//this is the array that holds the color values for each country 

private static boolean colorMap(int country){ 
    System.out.println("Checking Country "+ country); 
    boolean check; 
     for(int j= 0;j< countryColor.length; j++){ 
      if(useColor(country,color[j]) == true) 
       countryColor[country] = color[j]; 
      if(country == countryColor.length-1) 
       return true;      
      check = colorMap(country+1); 
      System.out.println(check); 
      if(check == true) 
       return true; 
      countryColor[country]=0; 
     } 
    return false; 
} 

private static boolean useColor(int country, int color){ 
    for(int i = 0; i < map.length;i++){ 
     if(map[country][i] == 1&& countryColor[i]==color){ 
      System.out.println("Nah country " + country +" cant be "+color); 
      return false; 
     } 
    } 
    return true; 
} 

Answer 1

Twój problem jest, że jeśli useColor wraca jako fałszywe, nie ustawić kolor dla bieżącego kraju, ale nadal stara się rekurencyjnie pokolorować resztę mapie. Jako przykład, najpierw próbujemy i kolorujemy pierwszy kraj (kraj 0) z kolorem 1, który się powiódł. Następnie próbujemy kolorować kraj 1 z kolorem 1, który kończy się niepowodzeniem, ponieważ sąsiaduje z krajem 0, który ma już ten kolor. To następnie próbuje rekursywnie zabarwić resztę, a jeśli się powiedzie, wówczas zwracamy prawdę. To, co powinieneś robić, to to, że obecny kolor nie działa, wtedy powinieneś przejść do następnej iteracji pętli próbując innego koloru przed rekursywnym zabarwianiem reszty.

Dokładniej, należy zmienić

if(useColor(country,color[j]) == true) 
    countryColor[country] = color[j]; 

do

if(useColor(country,color[j]) == true) 
    countryColor[country] = color[j]; 
else 
    continue; //this will try and color the current country with another color