Coloring Problem

Java code:

public class ColoringProblem {
    private enum Color {
        RED, GREEN, WHITE
    }
    static boolean[][] graph =
        {{false, true, false, true, false, false},
         {true, false, true, false, true, false},
         {false, true, false, false, false, true},
         {true, false, false, false, true, false},
         {false, true, false, true, false, true},
         {false, false, true, false, true ,false}};
    static Color[] graphColor = new Color[graph.length];
    static int countComb = 0;
    
    public static void main(String[] args) {
        paintColor(0);
        System.out.println("總共有" + countComb + "種塗色方法");
    }

    private static void paintColor(int vertex) {
        if (vertex < graph.length) {
            for (Color c: Color.values()) {
                boolean isUsed = false;
                
                for (int i=0; i<graph.length; i++) {
                    if (graph[vertex][i] && graphColor[i] == c) {
                        isUsed = true;
                        break;
                    }
                }
                if (!isUsed) {
                    graphColor[vertex] = c;
                    paintColor(vertex + 1);
                    graphColor[vertex] = null;
                }
            }
        }
        else {
            for (int i=0; i<graphColor.length; i++)
                System.out.printf("%-6s", "v" + (i + 1));
            System.out.println();
            for (Color c: graphColor) {
                switch (c) {
                    case RED:
                        System.out.printf("%-6s", "red");
                        break;
                    case GREEN:
                        System.out.printf("%-6s", "green");
                        break;
                    case WHITE:
                        System.out.printf("%-6s", "white");
                }
            }
            System.out.print("\n\n");
            countComb++;
        }
    }
}

範例輸入輸出:

---

此程式解決的是塗色問題，也就是在一個graph上面，用m個顏色去著色，並且相鄰的點不可以塗上相同的顏色。程式的作法是先選一個點並且從第一個顏色開始嘗試，塗上顏色後在選擇下一個點塗色。塗色時需要檢查相鄰的點有沒有使用一樣的顏色，若有使用一樣的顏色，就必須換色，若沒有顏色可以塗，就必須更改上一個點的顏色。若所有點都成功上色了，就表示找到一個塗色方法了，依照這個方法不斷做下去，就可以找出所有塗色的方法了。

因為此程式是解決課本第5章第18題的問題，所以輸入參數已經寫死在程式裡，輸出為所有的塗色方法和塗色方法的總數目。因為輸出結果過長，所以以上只貼出部份輸出結果。