Program to solve Eight Queen problem using backtracking technique

#include <stdio.h>

#include<conio.h>

int row[8],s=0;

int safe(int,int);

void putboard();

void queen(int);

int safe(int x, int y)

{

int i;

for(i=1;i<=y;i++)

if( row[y-i]==x || row[y-i]==x-i || row[y-i]==x+i)

return 0;

return 1;

}

void putboard()

{

int x,y;

printf("\nSolution # %d",++s);

printf(":\n---------------------------------\n");

for(y=0;y<8; y++)

{

for (x=0;x<8;x++)

if(x==row[y])

printf("| Q ");

else

printf("| ");

printf("|\n---------------------------------\n");

}

getch();

}

void queen(int y)

{

int x;

for(x=0;x<8;x++)

{

row[y-1]=x;

if( safe(x,y-1) )

if (y<8)

queen(y+1);

else

putboard();

}

}

void main()

{

clrscr();

queen(1);

getch();

}

OUTPUT

Download as Word File
Download as TEXT File
Download as PDF  

Program to perform Matrix Chain Multiplication

#include<stdio.h>

#include<conio.h>

#define MAX 15

#define INF 4294967295

int num,p[MAX+1],n;

void print(int [][MAX],int,int);

void matrixchainorder();

void setdata();

void printorder();

void print(int s[MAX][MAX],int i,int j)

{

if(i==j)

printf("A%d",num++);

else

{

printf("(");

print(s,i,s[i][j]);

printf(" x ");

print(s,s[i][j]+1,j);

printf(" ) ");

}

}

void matrixchainorder()

{

unsigned int q;

unsigned long m[MAX][MAX]={0};

int s[MAX][MAX]={0};

int l,j,i,k;

for(l=2;l<=n;l++)

for(i=1;i<=n-l+1;i++)

{

j=i+l-1;

m[i][j]=INF;

for(k=i;k<j;k++)

{

q=m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if(q < m[i][j])

{

m[i][j]=q;

s[i][j]=k;

}

}

}

printf("Number of Multiplications are %d ",m[1][n]);

num=1;

printf("Order of Multiplication is: ");

print(s,1,n);

}

void setdata()

{

int i;

printf("\nEnter number of matrices: ");

scanf("%d",&n);

for(i=1;i<=n;i++)

{

printf("Enter %d matrix size:",i);

scanf("%d%d",&p[i-1],&p[i]);

}

}

void printorder()

{

int i,j;

matrixchainorder();

}

void main()

{

clrscr();

setdata();

printorder();

getch();

}

OUTPUT

 

Click To Download as word File 

Download as TEXT File 

Download As PDF 

A program to perform All Pair Shortest Path problem

#include<stdio.h>

#include<conio.h>

int cost[20][20],n,a[20][20];

void setdata();

void getdata();

void path();

void setdata()

{

int i,j,k;

printf("\nEnter the number of nodes:");

scanf("%d",&n);

printf("\nEnter cost matrix(32767 for infinity):");

for(i=1;i<=n;i++)

{

printf("\nEnter %d row\n",i);

for(j=1;j<=n;j++)

{

scanf("%d",&cost[i][j]);

}

}

}

void getdata()

{

int i,j;

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

printf("%d ",a[i][j]);

}

printf("\n");

}

}

void path()

{

int i,j,k,l;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

a[i][j]=cost[i][j];

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

l=a[i][k]+a[k][j];

a[i][j]=(a[i][j]>l)?l:a[i][j];

}

}

void main()

{

clrscr();

setdata();

path();

printf("\nMatrix with shortest path is:\n");

getdata();

getch();

}

OUTPUT

 

Click To Download As Word File

 Download As TEXT File

Download As PDF