Scribd
Upload
2 views3 pages

Program 12

The document contains a C/C++ program that implements the N Queen's problem using backtracking. It includes functions to check if a queen can be safely placed on the board, solve the problem recursively, and print the solution. The program prompts the user to input the number of queens and displays the resulting board configuration if a solution exists.

Uploaded by

brahamanadreddy078
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Program 12

The document contains a C/C++ program that implements the N Queen's problem using backtracking. It includes functions to check if a queen can be safely placed on the board, solve the problem recursively, and print the solution. The program prompts the user to input the number of queens and displays the resulting board configuration if a solution exists.

Uploaded by

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

12. Design and implement C/C++ Program for N Queen’s problem using Backtracking.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define TRUE 1
#define FALSE 0

// Function to print the solution


void printSolution(int **board, int N)
{
int i, j;
printf("\nSolution:\n\n");
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
if (board[i][j])
printf("Q ");
else
printf("# ");
}
printf("\n");
}
}

// Function to check if a queen can be placed on board[row][col]


int isSafe(int **board, int N, int row, int col)
{
int i, j;

// Check this row on left side


for (i = 0; i < col; i++)
if (board[row][i])
return FALSE;

// Check upper diagonal on left side


for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return FALSE;

// Check lower diagonal on left side


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

return TRUE;
}
// A recursive utility function to solve N Queen problem
int solveNQUtil(int **board, int N, int col)
{
int i;
if (col >= N)
return TRUE;

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


{
if (isSafe(board, N, i, col))
{
board[i][col] = 1;

if (solveNQUtil(board, N, col + 1))


return TRUE;

board[i][col] = 0; // BACKTRACK
}
}

return FALSE;
}

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

if (!solveNQUtil(board, N, 0))
{
printf("Solution does not exist.\n");
for (i = 0; i < N; i++)
free(board[i]);
free(board);
return FALSE;
}

printSolution(board, N);

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


free(board[i]);
free(board);
return TRUE;
}
void main()
{
int N;
clrscr();
printf("Enter the number of queens: ");
scanf("%d", &N);

solveNQ(N);

getch();
}

Output:
Enter the number of queens: 4
##Q#
Q###
###Q
#Q##

You might also like