NQueen problem in C

Today I am going to post the NQueen problem in C with Backtracking.
What is the problem : According to this problem, we will have to place N queens in a n*n chessboard in such a way that the quuens are non-attacking. Non-attacking means there should be no queens in the same row,column or diagonal.
How to solve the problem : Here we will use the method of backtracking. In order to solve this problem, we first place the first queen, then the second and so on. But if we fail to place a queen, then we go back to the last successful position and try a different path. Now here is the details of the method : If a queen is already placed at location (i,j) and we want to place another queen at location (k,l), then we have to check whether we can place it in that location in the following way :
1  : check j!=l (not in same column)
2  ; ((i-j)!=(k-l)) (not in same right diagonal)
3 : ((i+j)!=(k+l)) (not in same left diagonal)
The second and third condition can be combined in a single condition which is : (abs(j-l)!=abs(k-i))
--------------------------------------------------------------------------------------------------------------------------

C CODE

--------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>
#include<math.h>

int x[50],soln=0;

int place(int k,int i){ //place kth queen at ith location
   int j;
   for(j=1;j<k;j++)  //checking with previously placed queens
     if((x[j]==i) || (abs(x[j]-i)==abs(j-k)))
      return 0;
   return 1;  //if successfully placed at ith location
}

void nqueens(int k,int n){
  int i;
  for(i=1;i<=n;i++)
    if(place(k,i)==1){  //if not successful then backtrack
     x[k]=i;  //if successful then save column number
     if(k==n)  //if all queens olaced then show solution
       display(n);
     else
       nqueens(k+1,n); //place all other queens
    }
}

void display(int n){
   int i,j;
   soln++;
   printf("\nSOLUTION #%d\n",soln);
   for(i=1;i<=n;i++){
     for(j=1;j<=n;j++)
       if(x[i]==j)
          printf("Q\t");
       else
          printf("*\t");
     printf("\n\n");
   }
}

int main(){
   int n;
   printf("Enter no. of queens : ");
   scanf("%d",&n);
   nqueens(1,n);

   printf("TOTAL SOLN. : %d",soln);

   return 0;
}Note : This code has been written and compiled with GCC compiler under Linux environment Ubuntu 12.04 LTS Precise Pangolin.

-------------------------------------------------------------------------------------------------------------------------

OUTPUT

------------------------------------------------------------------------------------------------------------------------- 

Enter no.of queens : 4

SOLUTION #1
*       Q       *       *

*       *       *       Q

Q       *       *       *

*       *       Q       *


SOLUTION #2
*       *       Q       *

Q       *       *       *

*       *       *       Q

*       Q       *       *

TOTAL SOLN. : 2

-------------------------------------------------------------------------------------------------------------------------

DOWNLOAD LINKS

-------------------------------------------------------------------------------------------------------------------------

 DOWNLOAD the source from Mediafire

Graph coloring problem with Backtracking in C

Today I am going to post a program in C that is used for solving the Graph Coloring problem.
What is Graph-Coloring : In this problem, for any given graph G we will have to color each of the vertices in G in such a way that no two adjacent vertices get the same color and the least number of colors are used.
How to solve the problem : First take input number of vertices and edges in graph G. Then input all the indexes of adjacency matrix of G whose value is 1. Now we will try to color each of the vertex. A next_color(k) function takes in index of the kth vertex which is to be colored. First we assign color1 to the kth vertex.Then we check whether it is connected to any of previous (k-1) vertices using backtracking. If connected then assign a color x[i]+1 where x[i] is the color of ith vertex that is connected with kth vertex.
--------------------------------------------------------------------------------------------------------------------------

SOURCE CODE

--------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>
int G[50][50],x[50];  //G:adjacency matrix,x:colors
void next_color(int k){
   int i,j;
   x[k]=1;  //coloring vertex with color1
   for(i=0;i<k;i++){ //checking all k-1 vertices-backtracking
     if(G[i][k]!=0 && x[k]==x[i])  //if connected and has same color
       x[k]=x[i]+1;  //assign higher color than x[i]
   }
}

int main(){
  int n,e,i,j,k,l;
  printf("Enter no. of vertices : ");
  scanf("%d",&n);  //total vertices
  printf("Enter no. of edges : ");
  scanf("%d",&e);  //total edges
 
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      G[i][j]=0;  //assign 0 to all index of adjacency matrix
     
  printf("Enter indexes where value is 1-->\n");
  for(i=0;i<e;i++){
    scanf("%d %d",&k,&l);
    G[k][l]=1;
    G[l][k]=1;
  }
 
  for(i=0;i<n;i++)
    next_color(i);  //coloring each vertex

  printf("Colors of vertices -->\n");
  for(i=0;i<n;i++)  //displaying color of each vertex
    printf("Vertex[%d] : %d\n",i+1,x[i]);

  return 0;
}
NOTE : This code is written,compiled and run with GCC compiler under Linux environment Ubuntu12.04LTS Precise Pangolin.

--------------------------------------------------------------------------------------------------------------------------

OUTPUT

--------------------------------------------------------------------------------------------------------------------------

Enter no. of vertices : 4

Colored vertices of Graph G

Enter no. of edges : 5
Enter indexes where value is 1-->
0 1
1 2
1 3
2 3
3 0
Colors of vertices -->
Vertex[1] : 1
Vertex[2] : 2
Vertex[3] : 1
Vertex[4] : 3
--------------------------------------------------------------------------------------------------------------------------

RELATED POSTS

--------------------------------------------------------------------------------------------------------------------------

 To understand m-coloring i.e. to color a graph with all possible m colors (hence known as M-Way Coloring or m-coloring) visit :

M-Coloring problem with Backtracking

C program to find maximum and minimum of an array using Divide & Conquer rule

Today I am going to post a program that is going to find out the maximum and minimum element of an array. You will say that it is very easy. But here we are going to use the Divide & Conquer technique to solve this problem . This technique will be able to solve the problem in a much lesser time. Here is the code for you-

#include<stdio.h>

int a[50],max,min;

void find(int i,int n){
   int mid,max1,min1;

   if(i==n)
     max=min=a[i];
   else if(i==n-1)
     if(a[i]>=a[n-1]){
       max=a[n];
       min=a[i];
     }
     else{
       max=a[i];
       min=a[n];
     }
   else{
     mid=(i+n)/2;
     find(i,mid);
     max1=max;
     min1=min;
     find(mid+1,n);
     if(max<max1)
         max=max1;
     if(min>min1)
         min=min1;
   }
} 

int main(){
   int i,n;

   printf("Enter size of array : ");
   scanf("%d",&n);

   printf("Enter elements in array-->\n");
   for(i=0;i<n;i++)
      scanf("%d",&a[i]);

   max=min=a[0];
   find(1,n-1);

   printf("Minimum : %d",min);
   printf("\nMaximum : %d",max);
  
   return 0;
}NOTE : This code is compiled with GCC compiler under Linux environment Ubuntu 12.04 LTS Precise Pangolin.

Important News to all followers

Over 150+ requests have come to me via email to set up a seperarte blog that deals only with java codes. So keeping in mind of all your requests I have decided to set up a new blog that will deal only with Java programs. This blog will contain posts covering most of the topics of core java and their related codes to help you out about most of the topics. So from now on you can get all related posts on my new blog at Java Code House(http://javaingrab.blogspot.com). But I will still continue posting on this blog.

Rotate Text in Java using Graphics2D

Today I will post how to continously rotate a text i.e string in Java Graphics2D. As you know that there are 4 types of transformation available in Java which are translation,rotation,scaling and shearing. Here I will use translation and rotation for this purpose. The text will be placed exactly at the center of the screen such that mid-point of text and screen coincide. Then the text will be rotated with screen center as the anchor point of rotation. Here is the code for you ->

import java.awt.*;
import java.awt.geom.*;
import java.awt.font.*;
import javax.swing.*;

public class RotateText extends JPanel{
    static int angdeg=0;
  
    @Override
    public void paint(Graphics g){
        Graphics2D g2d = (Graphics2D) g;
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,                         RenderingHints.VALUE_ANTIALIAS_ON);
         g2d.setColor(Color.white); //to remove trail of painting
         g2d.fillRect(0,0,getWidth(),getHeight());
         Font font =  new Font("serif",Font.BOLD,50);
         g2d.setFont(font);  //setting font of surface
         FontRenderContext frc = g2d.getFontRenderContext();
         TextLayout layout = new TextLayout("JAVA", font, frc);
         //getting width & height of the text
         double sw = layout.getBounds().getWidth();
         double sh = layout.getBounds().getHeight();
         //getting original transform instance
        AffineTransform saveTransform=g2d.getTransform();
        g2d.setColor(Color.black);
        Rectangle rect = this.getBounds();
        //drawing the axis
        g2d.drawLine((int)(rect.width)/2,0,(int)(rect.width)/2,rect.height);
        g2d.drawLine(0,(int)(rect.height)/2,rect.width,(int)(rect.height)/2);
        AffineTransform affineTransform = new AffineTransform(); //creating instance
       //set the translation to the mid of the component
       affineTransform.setToTranslation((rect.width)/2,(rect.height)/2);
       //rotate with the anchor point as the mid of the text
       affineTransform.rotate(Math.toRadians(angdeg), 0, 0);
       g2d.setTransform(affineTransform);
       g2d.drawString("JAVA",(int)-sw/2,(int)sh/2);
       g2d.setTransform(saveTransform); //restoring original transform
    }
   
    public static void main(String[] args) throws Exception{
         JFrame frame = new JFrame("Rotated text");
         RotateText rt=new RotateText();
        frame.add(rt);
        frame.setSize(500, 500);
   frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      frame.setLocationRelativeTo(null);
      frame.setVisible(true);
      while(true){
             Thread.sleep(10); //sleeping then increasing angle by 5
             angdeg=(angdeg>=360)?0:angdeg+5; //
             rt.repaint(); //repainting the surface
         }
    }
}