Scribd
Upload
7 views

Daa Assignment 7

Uploaded by

Satvik Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views

Daa Assignment 7

Uploaded by

Satvik Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Daa Assignment 7

Name: Satvik gupta Roll no: 23ucs698

Objectives: To understand the concept of backtracking in the context of


solving 8 queens' problems and learn to satisfy the constraints with regard
to the placement of queens on the chessboard.

Q.1 Implement the backtracking-based solution to 8 Queen’s problem.


1. The input to the problem will be the size of the chessboard (consider
square-shaped chessboards) and the implementation must return the
queen positions on the chessboard.
2. Repeat the above activity for different values of N and visualize the
performance of the algorithm against the chess board size.
3. Show empirically that for N=2 and N=3 no solution exists.

N Queen’s problem
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

bool isSafe(int** board, int row, int col, int N) {


for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}

bool solveNQUtil(int** board, int col, int N) {


if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col, N)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1, N))
return true;
board[i][col] = 0;
}
}
return false;
}

bool solveNQ(int N) {
int** board = (int**)malloc(N * sizeof(int*));
for (int i = 0; i < N; i++)
board[i] = (int*)malloc(N * sizeof(int));

for (int i = 0; i < N; i++)


for (int j = 0; j < N; j++)
board[i][j] = 0;

if (solveNQUtil(board, 0, N) == false) {
printf("Solution does not exist for N = %d\n", N);
return false;
}

for (int i = 0; i < N; i++)


free(board[i]);
free(board);

return true;
}

int main() {
for (int N = 4; N <= 20; N++) {
printf("N = %d:\n", N);

clock_t start = clock(); // Start timing

solveNQ(N);

clock_t end = clock(); // End timing


double time_taken = (double)(end - start) / CLOCKS_PER_SEC;
printf("Time taken for N = %d: %f seconds\n", N, time_taken);
printf("\n");
}
return 0;
}

2. Graph Between Time taken vs Size of Board :-


import matplotlib.pyplot as plt
import numpy as np

xpoints =
np.array([0.000072,0.000002,0.000007,0.000002,0.000030,0.000012,0.00
0035,0.000019,0.000112,0.000051,0.001053,0.000792,0.006367,0.003528
,0.030409,0.002556,0.179589])
ypoints = np.array([4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20])

plt.plot(ypoints, xpoints , marker = 'o')


plt.title('Runtime Complexity of n-Queens Problem (Backtracking)')
plt.ylabel("Time taken (in seconds) ----->")
plt.xlabel("Size of Chess board (n) ------->")
plt.show()

3.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void printSolution(int** board, int N) {


for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j])
printf("Q ");
else
printf(". ");
}
printf("\n");
}
}

bool isSafe(int** board, int row, int col, int N) {


for (int i = 0; i < col; i++)
if (board[row][i])
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}

bool solveNQUtil(int** board, int col, int N) {


if (col >= N)
return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col, N)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1, N))
return true;
board[i][col] = 0;
}
}
return false;
}

bool solveNQ(int N) {
int** board = (int**)malloc(N * sizeof(int*));
for (int i = 0; i < N; i++)
board[i] = (int*)malloc(N * sizeof(int));

for (int i = 0; i < N; i++)


for (int j = 0; j < N; j++)
board[i][j] = 0;

if (solveNQUtil(board, 0, N) == false) {
printf("Solution does not exist for N = %d\n", N);
free(board);
return false;
}

printSolution(board, N);

for (int i = 0; i < N; i++)


free(board[i]);
free(board);

return true;
}

int main() {
for (int N = 2; N <= 3; N++) {
printf("Testing for N = %d\n", N);
solveNQ(N);
printf("\n");
}
return 0;
}

Output : -
Testing for N = 2
Solution does not exist for N = 2
Testing for N = 3
Solution does not exist for N = 3

You might also like