四色定理的递归算法

Question

目前的问题是，将一张地图分成邻接矩阵中表示的区域，并使用四种颜色对地图进行着色，以确保没有两个相邻区域共享相同的颜色。我们将使用邻接矩阵来编码哪个区域与哪个其他区域相邻。矩阵的列和行是区域，如果两个区域不相邻，则单元格包含0，如果两个区域相邻，则单元格包含1。创建一个递归回溯解决方案，该方案接受用户的交互输入，即地图中的区域数和表示地图组成的邻接矩阵的文件名。

问题是，我遇到的是，第一个值在国家颜色改变，但数组中的许多值永远不会改变。

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

您的问题是，如果useColor返回为false，它不会为当前国家设置颜色，但仍会尝试递归地为地图的其余部分着色。作为一个例子，我们首先尝试用颜色1给第一个国家（国家0）着色，这成功了。然后我们尝试用颜色1给国家1着色，这失败了，因为它与已经有这种颜色的国家0相邻。然后尝试递归地给其余部分着色，如果成功，我们返回true。您应该做的是，如果当前颜色不起作用，那么您应该继续循环的下一次迭代，在递归着色其余颜色之前尝试另一种颜色。

更具体地说，你应该改变

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

到

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