Scribd
Upload
43 views2 pages

Program12-Queens C

The document presents a C/C++ program that solves the N Queen's problem using backtracking. It includes functions to check queen placements, recursively find solutions, and print the board configuration. The program prompts the user for the number of queens and outputs the total number of solutions found.

Uploaded by

Veeresha Gowda Bergi
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
43 views2 pages

Program12-Queens C

The document presents a C/C++ program that solves the N Queen's problem using backtracking. It includes functions to check queen placements, recursively find solutions, and print the board configuration. The program prompts the user for the number of queens and outputs the total number of solutions found.

Uploaded by

Veeresha Gowda Bergi
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

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

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

int x[30]; // Array to store the positions of the queens


int count = 0; // To count the number of solutions

// Function to check if a queen can be placed at the current position


int place(int k)
{
int i;
for (i = 1; i <= k-1; i++)
{
if ((x[i] == x[k]) || (abs(i-k) == abs(x[i] - x[k])))
{
return 0;
}
}
return 1;
}

// Recursive function to solve the N-Queens problem


void queens(int n)
{
int k = 1;
x[k] = 0;
while (k != 0)
{
do
{
x[k]++;
} while ((x[k] <= n) && (!place(k)));

if (x[k] <= n)
{
if (k == n)
print_solution(n);
else
{
k++;
x[k] = 0;
}
}
else
k--;
}
}
// Function to print the current board configuration
int print_solution(int n)
{
int i, j;
count++;
printf("\n Solution # %d\n", count);

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


{
for (j = 1; j <= n; j++)
{
if (x[i] == j)
printf("Q\t");
else
printf("*\t");
}
printf("\n");
}
}

// Main function
void main( )
{
int n;
printf("\n Enter the number of queens\n");
scanf("%d", &n);
queens(n);
printf("\n Total Solutions = %d", count);
getch();
}

You might also like