8.
N Queen Problem
What is N-Queen problem?
The N Queen is the problem of placing N chess queens on an N×N chessboard so
that no two queens attack each other.
For example, the following is a solution for the 4 Queen problem.
The expected output is in the form of a matrix that has ‘Q‘s for the blocks where
queens are placed and the empty spaces are represented by ‘.’ . For example, the
following is the output matrix for the above 4-Queen solution.
.Q..
...Q
Q...
..Q.
N Queen Problem using Backtracking:
The idea is to place queens one by one in different columns, starting from the leftmost
column. When we place a queen in a column, we check for clashes with already
placed queens. In the current column, if we find a row for which there is no clash, we
mark this row and column as part of the solution. If we do not find such a row due to
clashes, then we backtrack and return false.
Below is the recursive tree of the above approach:
Follow the steps mentioned below to implement the idea:
Start in the leftmost column
If all queens are placed return true
Try all rows in the current column. Do the following for every row.
o If the queen can be placed safely in this row
o Then mark this [row, column] as part of the solution and
recursively check if placing queen here leads to a solution.
o If placing the queen in [row, column] leads to a solution then
return true.
o If placing queen doesn’t lead to a solution then unmark this [row,
column] then backtrack and try other rows.
o If all rows have been tried and valid solution is not found return false to
trigger backtracking.
10. Finding Duplicate Elements in a Sorted Array using
Hashing in C:
In this article, I am going to discuss Finding Duplicate Elements in a Sorted Array
using Hashing in C Language with Examples. In our previous article, we have
seen how to find duplicate elements in a sorted array.
How to Find Duplicate Elements in a Sorted Array using Hashing in C Language?
We have the following sorted array.
We have taken a sorted array that has duplicated elements. As we can see
elements reoccur one or more than one time in the above array. We want to know
the duplicate elements as well as their count i.e. 13 is duplicated, then how many
times it duplicated. For this, we are using a method that will use a hash table. As we
have seen in the hash table in our previous articles. Below is the simplest form of
hast table:
We take the size of hast table 16 because 16 is the largest element in the above-
given array. As we have taken a sorted array so we can find the largest element at
the end of the array. Next, we have to fill the hash table or extra array with zeroes.
Now, let’s look at the procedure:
We have to scan through the given array by taking one element at a time.
0th Index:
We are taking an index pointer ‘k’ which is starting from the 0th index:
1st Index:
Now, ‘k’ is pointing to the 1st index:
2nd Index:
Now, ‘k’ is pointing to the 2nd index:
3rd Index:
Now, ‘k’ is pointing to the 3rd index:
In the same manner, we will trace the whole array and increment the value of the
extra array as we will find duplicate elements. So, at last, our extra array will be:
So, when we will find any duplicate element then we will increment the value of the
same index number in the extra array ‘H’.
Let’s do some analysis. So, how many times we are scanning through the array?
Only 1 time. While scanning we are incrementing the count in the extra array. So, it
will be constant time. The major time we spent is O (n). Now we have to find out
what are the duplicate elements from the above hast table. So, we will scan for 1.
For scanning the hash table, it will take O (n). Here n means linear.
Full Code in C language:
#include <stdio.h>
#include <stdlib.h>
struct List{
int C[15];
int size;
int length;
};
void Display(struct List list) {
int i;
printf("Elements are:\n");
for (i = 0;i<list.length;i++)
printf("%d ", list.C[i]);
printf("\n\n");
void DuplicateHashTable(struct List list, int max){
int H[max+1];
for(int i = 0; i <= max; i++){
H[i] = 0;
for(int i = 0; i < list.length; i++){
H[list.C[i]]++;
}
printf("Duplicate Elements are: \n");
for (int i = 0; i <= max; i++){
if(H[i] > 1)
printf("%d is appearing: %d times\n", i, H[i]);
int main(){
struct List list_1 = {{5, 7, 9, 9, 10, 11, 13, 13, 13, 16},
10, 10};
Display(list_1);
DuplicateHashTable(list_1, 16);
}
Output:
Time Complexity: O(n)
In the next article, I am going to discuss How to Find Duplicate Elements in an Unsorted Array in C
Language with Examples. Here, in this article, I try to explain How to Find Duplicate Elements in a
Sorted Array using Hashing in C Language with Examples and I hope you enjoy this Finding
Duplicate Elements in a Sorted Array using Hashing in C Language with Examples article.
