How do you write a program in c plus plus that implements the n-queens problem with backtracking?

Answer 1

#include<stdio.h>

#include<conio.h>

#include<math.h>

int a[30],count=0;

int place(int pos)

{

int i;

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

{

if((a[i]==a[pos])((abs(a[i]-a[pos])==abs(i-pos))))

return 0;

}

return 1;

}

void print_sol(int n)

{

int i,j;

count++;

printf("\n\nSolution #%d:\n",count);

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

{

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

{

if(a[i]==j)

printf("Q\t");

else

printf("*\t");

}

printf("\n");

}

}

void queen(int n)

{

int k=1;

a[k]=0;

while(k!=0)

{

a[k]=a[k]+1;

while((a[k]<=n)&&!place(k))

a[k]++;

if(a[k]<=n)

{

if(k==n)

print_sol(n);

else

{

k++;

a[k]=0;

}

}

else

k--;

}

}

void main()

{

int i,n;

clrscr();

printf("Enter the number of Queens\n");

scanf("%d",&n);

queen(n);

printf("\nTotal solutions=%d",count);

getch();

}

Answer 2

The following program can be found by searching WikiBooks under Algorithm, Implementation, Miscellaneous, N-Queens.

#include <iostream>

using namespace std;

const int N = 5;

int position[N];

// Check if a position is safe

bool isSafe(int queen_number, int row_position)

{

// Check each queen before this one

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

{

// Get another queen's row_position

int other_row_pos = position[i];

// Now check if they're in the same row or diagonals

if (other_row_pos N) // We placed N-1 queens (0 included), problem solved!

{

// Solution found!

cout << "Solution: ";

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

cout << position[i] << " ";

cout << endl;

}

else

{

for (int i = 0; i < N; i++) // Generate ALL combinations

{

// Before putting a queen (the k-th queen) into a row, test it for safeness

if (isSafe(k, i))

{

position[k] = i;

// Place another queen

solve(k + 1);

}

}

}

}

int main()

{

solve(0);

return 0;

}

Answer 3

The following program can be found by searching WikiBooks under Algorithm, Implementation, Miscellaneous, N-Queens.

#include

using namespace std;

const int N = 5;

int position[N];

// Check if a position is safe

bool isSafe(int queen_number, int row_position)

{

// Check each queen before this one

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

{

// Get another queen's row_position

int other_row_pos = position[i];

// Now check if they're in the same row or diagonals

if (other_row_pos N) // We placed N-1 queens (0 included), problem solved!

{

// Solution found!

cout << "Solution: ";

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

cout << position[i] << " ";

cout << endl;

}

else

{

for (int i = 0; i < N; i++) // Generate ALL combinations

{

// Before putting a queen (the k-th queen) into a row, test it for safeness

if (isSafe(k, i))

{

position[k] = i;

// Place another queen

solve(k + 1);

}

}

}

}

int main()

{

solve(0);

return 0;

}

Answer 4

#include<stdio.h>

int main()

{

printf("WRONG PERSON,I DONT KNOW");

getch();

}