Breaking
Backtracking

# Two color a map with no more than four colors

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);
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
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```