11.7 – Eight Queen problem

by subbu on December 12, 2013

Eight queen problem

It is the puzzle of placing eight queens on the chess board of 8×8 so that no two queens attack each other. It means no two queens share the same row, column and diagonal. Later it is extended to nxn queens that are placing n queens on nxn board and excludes with 2×2 and 3×3 boards.

eight queen problem

It can be done in different combinations, Say for example eight queens can be placed on 8×8 board in 92 combinations. Now we will see how we can solve the problem recursively.

Solving eight queen problem in C:

#include<stdio.h>
int q[50],n;
void printQueens();
int isConsistent(int);
void enumerate(int);
int main()
{
 printf("Enter the size of board:");
 scanf("%d",&n);
 if(n==2||n==3)
 {
  printf("Can't play the game..");
  return 0;
 }
 enumerate(0);
 return 0;
}
void enumerate(int c)
{
 int i;
 if (c == n)
   printQueens();
 else
 {
   for(i = 0; i < n; i++)
   {
     q1 = i;
     if(isConsistent(c))
       enumerate(c+1);
   }
  }
}
void printQueens()
{
 static int count=1;
 int i,j;
 printf("Combination %d\n",count++);
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
   if(q[i]==j)
     printf("Q ");
   else
     printf("* ");
  printf("\n");
 }
 printf("\n\n");
}
int isConsistent(int c)
{
 int i;
 for (i = 0; i < c; i++)
 {
  if (q[i] == q1)
    return 0;   // same column
  if ((q[i] - q1) == (c - i))
    return 0;   // same major diagonal
  if ((q1 - q[i]) == (c - i))
    return 0;   // same minor diagonal
  }
  return 1;
}

Execution:
Enter the size of board:1
Combination 1
Q

Execution:
Enter the size of board:3
Can’t play the game..

Execution:
Enter the size of board:4
Combination 1
* Q * *
* * * Q
Q * * *
* * Q *
Combination 2
* * Q *
Q * * *
* * * Q
* Q * *

Execution:
Enter the size of board: 8
————
————
Combination 91
* * * * * * * Q
* * Q * * * * *
Q * * * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
Combination 92
* * * * * * * Q
* * * Q * * * *
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *

Previous post:

Next post: