Backtracking

Two color a map with no more than four colors

Pinterest LinkedIn Tumblr

Given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.

Write a program to implement four color theorem?

source Code

package com.dsacode.Algorithm.backtracking;
 
public class TwoColorMap {
 
    private int G[][],x[],n,m,soln;
 
    public void mColoring(int k){ 
        for(int i = 1;i <= n; i++){
           next_color(k); 
           if(x[k]==0)
              return; 
           if(k==n) 
              write();
           else
              mColoring(k+1); 
        }
   }
 
   private void next_color(int k){
      do{
           int i=1;
         x[k]=(x[k]+1)%(m+1);
         if(x[k]==0)
           return;
         for(i = 1; i <= n; i++)
            if(G[i][k]!=0 && x[k]==x[i]) 
               break;
         if(i==n+1)  
             return; 
      }while(true);
   }
 
   private void write(){
      System.out.print("\nColoring(V C) #  "+(++soln)+"-->");
      for(int i = 1; i <= n; i++)
          System.out.print("\t("+i+" "+x[i]+")"); 
   }
    
   public void input(){
         n=4; m=3;
         System.out.println("Number of vertices : "+n);
         G=new int[n+1][n+1];
         x=new int[n+1];
         System.out.println("Number of colors : "+m);
         System.out.println("Adjacency matrix : ");
        for(int i = 1; i <= n;i++)
           for(int j = 1; j <= n; j++)
               G[i][j]=1;
         
        G[1][1]=G[2][2]=G[3][3]=G[4][4]=G[2][4]=0;
         
        for(int i = 1;i <= n; i++){
            for(int j = 1; j <= n; j++){
                System.out.print(G[i][j] +" ");
            }
            System.out.println();
        }
   }
    
   public static void main (String[] args) {
       TwoColorMap obj=new TwoColorMap();
        obj.input();
        obj.mColoring(1);
        if(obj.soln==0)
           System.out.println("\nNeed more than "+obj.m+" colors");
        else
           System.out.print("\ntotal number of solutions : "+obj.soln);
   }
 
}

Output

Number of vertices : 4
Number of colors : 3
Adjacency matrix :
0 1 1 1
1 0 1 0
1 1 0 1
1 1 1 0
 
Coloring(V C) #  1-->    (1 1)   (2 2)   (3 3)   (4 2)
Coloring(V C) #  2-->    (1 1)   (2 3)   (3 2)   (4 3)
Coloring(V C) #  3-->    (1 2)   (2 1)   (3 3)   (4 1)
Coloring(V C) #  4-->    (1 2)   (2 3)   (3 1)   (4 3)
Coloring(V C) #  5-->    (1 3)   (2 1)   (3 2)   (4 1)
Coloring(V C) #  6-->    (1 3)   (2 2)   (3 1)   (4 2)
total number of solutions : 6

Algorithm Explanation

Initialize matrix with rows and columns.
G is graph’s adjacency matrix and x is solution vector.
Call backtracking function coloring kth vertex, checking adjacency node and not same color.
If unsuccessful then backtrack. If it successful, check the left to color.

Reference

  1. http://mathworld.wolfram.com/Four-ColorTheorem.html
  2. http://www.mathpages.com/home/kmath266/kmath266.htm
  3. https://en.wikipedia.org/wiki/Four_color_theorem

Write A Comment