AMBALIKA INSTITUTE OF MANAGEMENT AND
TECHNOLOGY , LUCKNOW
DEPARTMENT OF COMPUTER SCIENCE
& ENGINEERING
DESIGN AND ANALYSIS OF ALGORITHM
LAB
(BCS-553)
Submitted To
Mr. Susheel kumar
(Assistant Professor)
Name of Student:
Roll No:
Branch:
Session:
INDEX
SL NAMEOFLABEXPERIMENT DATE SIGN REMARK
1 Program for Insertion Sort 07-10-2024
2 Program for Quick Sort 14-10-2024
3 Program for Merge Sort 21-10-2024
4 Program for Selection Sort 28-11-2024
5 Program for Heap Sort 04-11-2024
6 Program for Recursive Binary 11-11-2024
& Linear Search
7 Knapsack Problem using Greedy 18-11-2024
Solution
8 Perform Travelling Salesman Problem 25-12-2024
9 Find Minimum Spanning Tree using 02-12-2024
Kruskal’s Algorithm
10 Implement N Queen Problem 09-12-2024
using Backtracking
11
12
Appendices
I. InstituteVision
II. InstituteMission
III. CSEDepartmentVision
IV CSEDepartmentMission
V CSEDepartment PEOs
VI ProgramOutcomes (POs)
PRACTICAL-1
OBJECT:-TO IMPLEMENT THE INSERTION SORT.
THEORY – Insertion sort is a simple sorting algorithm, a comparisonsort
in which the sorted array (or list) is built one entry at a time. It is much less efficient on
large lists thanmoreadvanced algorithmssuchasquicksort,heapsort,or mergesort.
However,insertionsortprovidesseveraladvantages:
simpleimplementation,efficientfor(quite)smalldatasets
efficientfordatasetsthatarealreadysubstantiallysorted:therunningtimeisO(n
+d),wheredisthenumberofinversions
moreefficientinpracticethanmostothersimplequadratic(i.e.,O(n2))algorithmssuch
as selection sort or bubble sort: the average running time is n2/4, and
therunningtimeislinearinthebestcase
stable(i.e.,doesnotchangetherelativeorderofelementswithequalkeys)
in-place(i.e.,onlyrequiresaconstantamountO(1)ofadditionalmemoryspace)
online(i.e.,cansortalistasitreceivesit)
Class: Sortingalgorithm
DataStructure:
Array
TimeComplexity: Θ(n2)
SpaceComplexity:
Ώ(n)total,O(1)auxiliaryO
ptimal: Notusually
Program–1
#include<stdio.h>
#include<conio.h>
Voidmain()
{
intarr[5]={25,23,17,14,89};
inti,j,k,temp;
clrscr();
printf("INSERTIONSORT\n\n");p
rintf("array before sorting
:");for(i=0;i<5;i++)printf("%d\t",a
rr[i]);for(i=1;i<5;i++)
{
for(j=0;j<i;j++)
{
if(arr[j]>arr[i])
{
temp=arr[j];
arr[j]=arr[i];
for(k=i;k>j;k--)
arr[k]=arr[k-
1];arr[k+1]=te
mp;
}
}
}
printf("\n\narrayaftersorting:");for
(i=0;i<5;i++)printf("%d\t",arr[i]);
getch();
}
Output
:
PRACTICAL-2
OBJECT–TO IMPLEMEN THE QUICK SORT.
THEORY – Quicksort is a well-known sorting algorithm
developedby C. A. R. Hoare that, on average, makes O(nlogn) (big O notation)
comparisons to sortn items. However, in the worst case, it makes O(n2) comparisons.
Typically, quicksort issignificantly faster in practice than other O(nlogn) algorithms,
because its inner loop canbe efficiently implementedon most architectures,andin most
real-world data itispossible to make design choices which minimize the probability of
requiring quadratictime.
Quicksort is a comparison sort and, in efficient implementations, is not a stable
[Link] alistintotwosub-lists.
Thesteps are:
Pickanelement,calledapivot,fromthelist.
Reorder the list so that all elements which are less than the pivot come before
thepivot and so that all elements greater thanthe pivot come after it (equal
valuescan go either way). After this partitioning, the pivot is in its final position.
This iscalledthepartitionoperation.
Recursively sort the list of lesser elements and the list of greater elements
insequence.
The base cases of the recursion are lists of size zero or one,which are always sorted.
Program-2
#include<stdio.h>
voidswap(int*a,int*b){int
temp= *a;
*a=*b;
*b=temp;
}
intpartition(int
arr[],intlow,inthigh){intpivot=arr[hig
h];
inti=(low-1);
for(intj=low;j<=high-
1;j++){if(arr[j]<=pivot){
i++;
swap(&arr[i],&arr[j]);
}
}
swap(&arr[i+1],&arr[high]);r
eturn(i+1);
}
voidquickSort(int
arr[],intlow,inthigh){if(low<high){
intpi=partition(arr,low,high);
quickSort(arr, low, pi -
1);quickSort(arr,pi+1,
high);
}
}
intmain(){
intarr[]={12,11,13,5,6,7};
intn=sizeof(arr)/sizeof(arr[0]);
printf("Originalarray:
");for(inti=0;i<n;i++)
printf("%d",arr[i]);
quickSort(arr, 0,n-1);
printf("\nSortedarray:");f
or(inti=0; i<n; i++)
printf("%d",arr[i]);
return0;
}
Output
PRACTICAL-3
OBJECT–TO IMPLEMENT THE MERGE SORT
THEORY : Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It
dividesinput array in two halves, calls itself for the two halves and then merges the two
sortedhalves. The merge() function is used for merging two halves. The merge(arr, l, m,
r) iskey process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the
twosorted [Link] for details.
MergeSort(arr[],l,r)
Ifr>l
1. Findthemiddlepointtodividethearrayintotwohalves:middlem=(
l+r)/2
2. CallmergeSortforfirsthalf:Cal
lmergeSort(arr,l,m)
3. Call mergeSort for second
half:CallmergeSort(arr,m+1,
r)
4. Mergethetwohalvessortedinstep
2and3:Callmerge(arr,l,m,r)
TimeComplexity:[Link]
omplexitycanbeexpressedasfollowingrecurrencerelation.
T(n)=2T(n/2)+
[Link]
caseIIof MasterMethodandsolutionof therecurrenceis .
TimecomplexityofMergeSortis
inall3cases(worst,averageandbest)asmer
ge sort always divides the array in two halves and take linear time to merge two
[Link]:O(n)
Algorithmic Paradigm: Divide and
ConquerSortingInPlace:Noinatypicalimplement
ationStable:Yes
Program-3
#include<stdlib.h>
#include<stdio.h>
voidmerge(int arr[],int l,intm,int r)
{
inti,j,k;
intn1=m-
l+1;intn2=r-m;
/*createtemparrays*/in
tL[n1],R[n2];
/*CopydatatotemparraysL[]andR[]*/for(i
=0;i<n1;i++)
L[i]= arr[l
+i];for(j=0;j<n2;j++)
R[j]=arr[m+1+j];
/* Merge the temp arrays back into
arr[l..r]*/i= 0;//Initialindexoffirstsubarray
j = 0; // Initial index of second
subarrayk = l; // Initial index of merged
subarraywhile(i< n1&&j<n2)
{
if(L[i]<=R[j])
{
arr[k] =
L[i];i++;
}
else
{
arr[k]=R[j];j
++;
}
k++;
}
/*CopytheremainingelementsofL[],iftherearea
ny*/
while (i<n1)
{
arr[k] =
L[i];i++;
k++;
}
/*CopytheremainingelementsofR[],iftherearea
ny*/
while (j<n2)
{
arr[k]=R[j];j
++;
k++;
}
}
/*lisfor leftindexandrisrightindexofthesub-
arrayofarrtobesorted*/
voidmergeSort(int arr[],intl, intr)
{
if(l<r)
{
//Sameas(l+r)/2,butavoidsoverflowfor
//
largelandhintm=
l+(r-l)/2;
//Sortfirstandsecondhalvesm
ergeSort(arr, l,m);
mergeSort(arr,m+1, r);
merge(arr,l,m,r);
}
}
/*UTILITYFUNCTIONS*/
/* Function to print an array
*/voidprintArray(intA[],intsize)
{
inti;
for(i=0;i<size;i++)pri
ntf("%d",A[i]);
printf("\n");
}
/*Driverprogramtotestabovefunctions*/int
main()
{
intarr[]={12,11,13,5,6,7};
intarr_size=sizeof(arr)/sizeof(arr[0]);
printf("Givenarrayis\n");p
rintArray(arr,arr_size);
mergeSort(arr,0,arr_size-1);
printf("\nSortedarrayis\n");p
rintArray(arr,arr_size);retur
n0;
}
Output
PRACTICAL-4
OBJECT– TO IMPLEMENT THE SELECTION SORT
THEORY:
Theselectionsortalgorithmsortsanarraybyrepeatedlyfindingtheminimumelement(consideringas
cendingorder)[Link]
sinagivenarray.
1) The subarraywhichisalreadysorted.
2) Remainingsubarraywhichisunsorted.
In every iteration of selection sort, the minimum element (considering ascending order)
fromtheunsortedsubarrayispickedandmovedtothesortedsubarray.
Followingexampleexplainstheabovesteps:
arr[]=6425122211
//Findtheminimumelementinarr[0...4]
//andplaceitatbeginning
1125122264
//Findtheminimumelementinarr[1...4]
//andplaceitatbeginningofarr[1...4]111225
2264
//Findtheminimumelementinarr[2...4]
//andplaceitatbeginningofarr[2...4]111222
2564
//Findtheminimumelementinarr[3...4]
//andplaceitatbeginningofarr[3...4]111222
2564
TimeComplexity:O(n2)astherearetwonestedloops.
AuxiliarySpace:O(1)
Thegood thingaboutselection sortisitnevermakesmore
thanO(n)swapsandcanbeusefulwhenmemorywriteis acostlyoperation.
Stability:[Link] [Link] stable
selection sortfordetails.
InPlace:Yest,itdoesnotrequireextra space
PROGRAM-4
#include<stdio.h>
voidswap(int *xp,int *yp)
{
inttemp=*xp;
*xp=*yp;
*yp=temp;
}
voidselectionSort(int arr[],intn)
{
inti,j, min_idx;
// One by one move boundary of unsorted
subarrayfor(i=0;i<n-1;i++)
{
//Findtheminimumelementinunsortedarraymin
_idx=i;
for(j=i+1; j<n;j++)
if(arr[j]<arr[min_idx])
min_idx=j;
//Swapthefoundminimumelementwiththefirstelementswap(&arr[min_idx],
&arr[i]);
}
}
/* Function to print an array
*/voidprintArray(intarr[],intsize)
{
inti;
for (i=0; i < size;
i++)printf("%d",arr
[i]);
printf("\n");
}
//Driverprogramtotestabovefunctionsint
main()
{
intarr[]={64,25,12,22,11};
int n =
sizeof(arr)/sizeof(arr[0]);selecti
onSort(arr, n);printf("Sorted
array:\n");printArray(arr,n);
return0;
}
Output
PRACTICAL-5
OBJECT– TO IMPLEMENT THE HEAP SORT.
THEORY –Heapsort (method) is a comparison-based sortingalgorithm,
and is part of the selection sort family. Although somewhat slower in practiceon most
machines than a good implementation of quicksort, it has the advantage of aworst-
caseT(nlogn)runtime. Heapsortisanin-placealgorithm, but isnotastablesort.
Heapsort inserts the input list elements into a heap data structure. The largest value (in
amax-heap) or the smallest value (in a min-heap) are extracted until none remain,
thevalues having been extracted in sorted order. The heap's invariant is preserved after
eachextraction,so theonlycostisthatofextraction.
During extraction, the only space required is that needed to store the heap. In order
toachieve constant space overhead, the heap is stored in the part of the input array that
hasnot yetbeensorted.
(Thestructureofthis heapisdescribedatBinaryheap:
HeapImplementation.)
Heapsort uses two heap operations: insertion and root deletion. Each extraction places
anelement in the last empty location of the array. The remaining prefix of the array
storestheunsortedelements.
Program-5
#include<stdio.h>
voidheapify(intarr[],intn,inti);voi
dheapSort(intarr[],intn);
intmain(){i
nti,n;
printf("HEAPSORT\n\n");printf("Entert
henumberofelements:
");scanf("%d",&n);
intarr[n];
printf("Enterthearray:");f
or(i= 0;i<n;i++)
scanf("%d",
&arr[i]);heapSort(arr,n)
;printf("Sorted array:
");for(i= 0;i< n;i++)
printf("%d\t",arr[i]);
return0;
}
voidheapify(intarr[],intn,inti){intl
argest= i;
intleft=2*i+1;
intright=2*i+2;
if(left<n
&&arr[left]>arr[largest])largest=
left;
if(right<n&&arr[right]>arr[largest])larg
est=right;
if(largest!=i){intte
mp=arr[i];
arr[i]=arr[largest];arr[l
argest] =
temp;heapify(arr,n,lar
gest);
}
}
voidheapSort(intarr[],
intn){for(inti=n/2 -1;i>=0;i--)
heapify(arr,n,i);
for(inti=n-1;i>0; i--
){inttemp= arr[0];
arr[0] =
arr[i];arr[i]=
temp;heapify(arr
,i,0);
}
}
Output
PRACTICAL-6
OBJECT– TO IMPLEMENT THE RECURSIVE AND BINARY SEARCH.
THEORY–
Givenasortedarrayarr[]ofnelements,writeafunctiontosearchagivenelementxinarr[].
A simple approach is to do linear [Link] time complexity of above algorithm
isO(n).Anotherapproachto performthesametaskisusing BinarySearch.
Binary Search: Search a sorted array by repeatedly dividing the search interval in
[Link] with an interval covering the wholearray. If the value of the search key is
lessthan theitem inthemiddleof theinterval,narrowtheinterval [Link]
narrow it to the upper half. Repeatedly check until the value is found or
theintervalisempty.
Webasicallyignorehalfoftheelementsjustafteronecomparison.
1. Comparexwiththemiddleelement.
2. Ifxmatcheswith middleelement,wereturnthemidindex.
3. ElseIfxisgreaterthanthemidelement,thenxcanonlylieinrighthalfsubarrayafterthemid
[Link].
4. Else(xissmaller)recurforthelefthalf.
RecursiveimplementationofBinarySearch
PROGRAM-6
#include<stdio.h>
//[Link]
// locationofxingivenarrayarr[l..r]ispresent,
//otherwise -1
intbinarySearch(intarr[],intl,intr,intx)
{
if(r>=l)
{
intmid=l+(r-l)/2;
//Iftheelementispresentatthemiddle
//itself
if(arr[mid]==x)r
eturnmid;
//Ifelementissmallerthanmid, then
//itcanonlybepresentinleftsubarrayif(ar
r[mid]> x)
returnbinarySearch(arr,l,mid-1,x);
//Elsetheelementcanonlybepresent
//inrightsubarray
returnbinarySearch(arr,mid+1, r,x);
}
//Wereachherewhenelementisnot
// present in
arrayreturn-1;
}
intmain(void)
{
intarr[]={2,3,4,10,40};
int n = sizeof(arr)/
sizeof(arr[0]);intx=10;
int result=binarySearch(arr,0,n-1,x);
(result==-1)?printf("Elementisnotpresentinarray")
:printf("Elementispresentatindex%d",
result);
return0;
}
Output
PRACTICAL-7
OBJECT– TO IMPLEMENT OF KNAPSACK PROBLEM USING GREEDY SOLUTION
THEORY – In Fractional Knapsack, we can break items for maximizing the total value
ofknapsack. This problem in which we can break an item is also called the fractional
knapsackproblem.
Input:
Same as
aboveOutput:
Maximumpossiblevalue=240
By taking full items of 10 kg, 20 kg
and2/3rdoflastitemof30kg
An efficient solution is to use Greedy approach. The basic idea of the greedy approach is
tocalculatethe ratio value/weight for each item and sort theitem onbasis of this ratio. Thentake
the item with the highest ratio and add them until we can’t add the next item as a wholeand at
the end add the next item as much as wecan. Which will always be the
optimalsolutiontothisproblem.
A simple code with our own comparison function can be written as follows, please see
sortfunction more closely, the third argument to sort function is our comparison function
whichsorts the item according to value/weight ratio in non-decreasing
[Link] sorting we need to loop over these items and add them in our knapsack
satisfyingabove-mentionedcriteria.
Asmaintimetakingstepissorting, thewholeproblemcanbesolvedinO(nlogn)only.
PROGRAM-7
//Cprogramtosolve
fractionalKnapsackProblem#include<stdio.h>
#include<stdlib.h>
//StructureforanitemwhichstoresweightandcorrespondingvalueofItemstructItem
{
int value,weight;
};
//ComparisonfunctiontosortItemaccordingtoval/weightratiointcm
p(constvoid*a,constvoid*b)
{
double r1 = (double)((struct Item *)b)->value / ((struct Item *)b)-
>weight;double r2 = (double)((struct Item *)a)->value / ((struct Item *)a)-
>weight;returnr1>r2?1:-1;
}
doublefractionalKnapsack(intW,structItemarr[],intn)
{
qsort(arr,n,sizeof(structItem),cmp);
intcurWeight=0; // Current weight in
knapsackdoublefinalValue=0.0;//Result(valueinKnap
sack)
for(inti=0;i<n;i++)
{
if(curWeight+arr[i].weight<=W)
{
curWeight+=arr[i].weight;f
inalValue+=arr[i].value;
}
else
{
int remain=W-curWeight;
finalValue+=arr[i].value*((double)remain/arr[i].weight);bre
ak;
}
}
returnfinalValue;
}
//Driverprogramtotestabovefunctionint
main()
{
intW=50;//Weightofknapsack
structItemarr[] ={{60,10},{100,20},{120,30}};
intn=sizeof(arr)/sizeof(arr[0]);
printf("Maximumvaluewecanobtain=%.2f\n",fractionalKnapsack(W,arr,n));return0
;
}
Output
PRACTICAL-8
OBJECT–PERFORM TRAVELLING SALESMAN PROBLEM.
THEORY – Travelling Salesman Problem (TSP): Given a set of cities and
distancebetween every pair of cities, the problem is to find the shortest possible route
that visitsevery city exactly once and returns back to the starting
[Link] the difference between Hamaltonion and TSP. TheHamiltoninan cycle problem
is to find if there exist a tour that visits every city exactly once. Here we know that
Hamiltonian Tour exists (because the graph is complete) and in fact many such
toursexist, the problem is to find a minimum weight Hamiltonian
[Link] example,consider the graph shown in figure on [Link] in the graph is1-2
4-3-1.Thecostofthetouris10+25+30+15 whichis80.
The problem is a famous NP hard problem. There is no polynomial time know
solutionforthis problem.
1. [Link],wecanconsider
anypoint asstartingpoint.
2. Generateall(n-1)!permutationsofcities.
3. Calculatecostofeverypermutationandkeeptrackofminimumcostpermutation.
4. Returnthepermutation withminimumcost.
PROGRAM-8
#include
<stdio.h>#include
<limits.h>#define
V4
voidswap(int*a,int*b){int
temp= *a;
*a=*b;
*b=temp;
}
voidpermute(intgraph[][V],int*vertex,intstart,int
end,int*minPath,ints){if(start==end){
intcurrentPathWeight=0;i
ntk=s;
for(inti= 0;i< V-
1;i++){currentPathWeight+=graph[k][ver
tex[i]];k=vertex[i];}
currentPathWeight +=graph[k][s];
*minPath=(*minPath<currentPathWeight) ?*minPath:currentPathWeight;
}else{
for (int i = start; i <= end; i++)
{swap(&vertex[start],&vertex[i])
;
permute(graph,vertex,
start+1,end,minPath,s);swap(&vertex[start],&ver
tex[i]);//backtrack
}
}
}
inttravellingSalesmanProblem(intgraph[][V],ints){int
vertex[V-1];
intk =0;
for(inti=0;
i<V;i++)if(i!=s)
vertex[k++]=i;
intminPath=INT_MAX;
permute(graph,vertex, 0,V-
2,&minPath,s);returnminPath;
}
intmain(){
// Matrix representation of the
graphintgraph[V][V]={{0,10,15,20}
,
{ 10,0,35,25},
{ 15,35,0,30},
{20,25,30, 0}}
ints=0;
printf("MinimumcostforTSP:%d\n",travellingSalesmanProblem(graph,s));return0;
}
Output
PRACTICAL-9
OBJECT– FIND MINIMUM SPANNING TREE USING KRUSKAL’SALGORITHM.
THEORY- Kruskal's algorithm is algorithm in graph the or that find a minimum
spanning tree for a connected weighted graph. This means it finds a subset ofthe edges
that forms a tree that includes every vertex, where the total weight of all theedges in the
tree is minimized. If the graph is not connected, then it finds a minimumspanning forest
(a minimum spanning tree for each connected component).
Kruskal'salgorithmisanexampleofagreedyalgorithm.
Itworks asfollows:
createaforestF(asetoftrees),where eachvertexinthegraphis aseparatetree
createasetScontainingalltheedgesinthe graph
whileSisnonempty
remove anedgewithminimumweightfromS
ifthatedgeconnectstwodifferenttrees,thenaddittotheforest,combiningtwotreesint
oasingletree
otherwisediscardthatedge
Attheterminationofthealgorithm,theforesthasonlyonecomponentandformsaminim
umspanningtreeofthegraph.
This algorithm first appeared in Proceedings of the American Mathematical Society,
pp.48–50in1956,andwaswrittenbyJosephKruskal.
Other algorithms for this problem include Prim's algorithm, Reverse-Delete
algorithm,andBoruvka'salgorithm
Where E is the number of edges in the graph and V is the number of vertices,
Kruskal'salgorithm can be shown to run in O(E log E) time, or equivalently, O(E log V)
time, allwithsimple [Link]:
Eis atmostV2andlogV2=2logVisO(logV).
Ifweignoreisolated
vertices,whichwilleachbetheirowncomponentoftheminimumspanningtreeanyway,V=E+1,so
logVisO(logE).
Program–9
#include
<stdio.h>#include<st
dlib.h>
structlledge
{
intv1,v2;f
loatcost;
structlledge*next;
};
intstree[5],count[5],mincost;
structlledge*kminstree(structlledge*,int);int
getrval(int);
voidcombine(int,int);voi
ddel(structlledge*);
intmain()
{
structlledge*temp,*root;i
nti;
root=(structlledge*)malloc(sizeof(structlledge));ro
ot->v1=4;
root->v2=3;
root->cost=1;
temp=root-
>next=(structlledge*)malloc(sizeof(structlledge));temp->v1=4;
temp->v2=2;
temp->cost=2;
temp-
>next=(structlledge*)malloc(sizeof(structlledge));temp=temp-
>next;
temp->v1=3;
temp->v2=2;
temp->cost=3;
temp-
>next=(structlledge*)malloc(sizeof(structlledge));temp=temp-
>next;
temp->v1=4;
temp->v2=1;
temp->cost=4;
temp-
>next=NULL;root=kmin
stree(root,5);for(i=1;i<=
4;i++)
printf("\nstree[%d]->%d",i,stree[i]);
printf("\ntheminimumcostofspanningtreeis%d
",mincost);del(root);
return0;
}
structlledge*kminstree(structlledge*root,int n)
{
structlledge*temp=NULL;st
ructlledge *p,*q;
intnoofedges=0;i
for(i=0;i<n;i++)stre
e[i]=i;
for(i=0;i<n;i++)cou
nt[i]=0;
while((noofedges <(n-1))&&(root!=NULL))
{
p=root;
root =root->next;
p1 = getrval(p-
>v1);p2=getrval(p-
>v2);
if(p1!=p2)
{
combine(p->v1, p-
>v2);noofedges++;
mincost += p-
>cost;if(temp==NU
LL)
{
temp=p;
q=temp;
}
else
{
q->next =
p;q=q-
>next;
}
q->next=NULL;
}
}
returntemp;
}
intgetrval(int i)
{
int
j,k,temp;k=i;
while(stree[k]!=k)k
=stree[k];
j=i;
while(j!=k)
{
temp =
stree[j];stree[j]
=k;
j= temp;
}
returnk;
voidcombine(inti,intj)
{
if(count[i]<count[j])st
ree[i]=j;
else
{
stree[j]=i;
if(count[i]
==count[j])count[j]+
+;
}
}
voiddel(structlledge*root)
{
structlledge*temp;wh
ile(root!=NULL)
{
temp = root-
>next;free(root);
root=temp;
}
}
Output
PRACTICAL-10
OBJECT–TO IMPLEMENT N-QUEEN PROBLEM USING BACK TRACKING
THEORY – We have discussed Knight’stourand Rat in Maze problems in Set1 and Set2
respectively. Let us discuss N Queen as another example problem that can
besolvedusingBacktracking.
The expected output is a binary matrix which has 1s for the blocks where queens are
[Link],followingistheoutputmatrixforabove4queensolution.
{0, 1, 0, 0}
{0, 0, 0, 1}
{1, 0, 0, 0}
{0, 0, 1, 0}
The idea is to place queens one by one in different columns, starting fromthe leftmostcolumn.
When we place a queen in a column, we check for clashes with already placedqueens. In the
current column, if we find a row for which there is no clash, we mark this rowand column as
part of the solution. If we do not find such a row due to clashes then
webacktrackandreturnfalse.
1) Startintheleftmostcolumn
2) Ifallqueensareplacedre
turntrue
3) [Link].
a) Ifthequeencanbeplacedsafelyinthisrowthenmarkthis[row,
column]aspartofthesolutionandrecursivelycheckifplacingqueenhereleadstoa solution.
b) Ifplacingthequeenin[row,column]leadstoasolutionthenreturntrue.
c) Ifplacingqueendoesn'tleadtoasolutionthenumarkthis[row,column](Backtrack)andgotostep(a)totryotherrows.
3)Ifallrowshavebeentriedandnothingworked,returnfalsetotriggerbacktracking.
Program-10
/*C/C++programto
solveNQueenProblemusingbacktracking*/#include<stdio.h>
#include
<stdbool.h>#define
N4
void printSolution(int board[N][N])
{for(inti= 0;i< N;i++){
for (int j = 0; j < N;
j++)printf("%d",board[i][
j]);
printf("\n");
}
}
boolisSafe(intboard[N][N],introw,intcol){inti,j;
for(i=0;i<col;i++)if
(board[row][i])returnf
alse;
for(i= row,j=col;i>=0&&j>=0; i--,j--
)if(board[i][j])
returnfalse;
for(i= row,j=col;j>=0&&i<N;i++,j--
)if(board[i][j])
return
false;returntrue;
}
bool solveNQUtil(int board[N][N], int col)
{if(col>=N)
returntrue;
for(inti=0;i<
N;i++){if(isSafe(board,i,
col)){
board[i][col] =1;
if(solveNQUtil(board,col+1))re
turntrue;
board[i][col]=0;
}
}
returnfalse;
}
boolsolveNQ(){
intboard[N][N]={{0,0,0,0},
{0, 0,0,0},
{0, 0,0,0},
{0,0,0,0}};
if(solveNQUtil(board,0)==false){pri
ntf("Solution does not
exist");returnfalse;
}
printSolution(board);
returntrue;
}
intmain(){sol
veNQ();ret
urn0;
}
Output