Write a c program to print all solutions of 8 queens  problem?

Given a 8×8 matrix as a chess board, place 8 queens on the chess board such that no two queens check or attack each other. we have to place each queens so that no two queens share the same row, column, or diagonal. Below is figure which left side shows empty chess board and right side shows one of the placement of 8 queens. This puzzle has 92 distinct solutions. write a c program to print all solutions.

8 queens problem all solutions in c

Solution:

For solving we have to consider the condition carefully while coding and the condition is  ” The condition no two queens should share the same row,column or diagonal”. The first possible mechanism is pure brute force; blindly trying the eight queens in every possible location. This is a really dumb idea, but would calculate all possible solutions (We’d have to examine 64!/56! = 178,462,987,637,760 possible placements, ouch!) ( ref: from http://www.datagenetics.com/blog/august42012/).

A better method can be:

(1) start in the first column in the top left.
(2) places a queen in the second column and moves it until it finds
   a place where it cannot be hit by the queen in the first column.

(3) Then places a queen in the third column and moves it until it cannot be hit by either of the first two queens.
(4) continues this process with the remaining columns.
(5) If there is no place for a queen in the current column the program goes back to the preceding column and moves the queen in that column.
(6) If the queen there, is at the end of the column it removes that queen as well and goes to the preceding column.
(7) If the current column is the last column and a safe place has been found for the last queen, then a solution of the puzzle has been found.
(8) If the current column is the first column and its queen is being moved off the board then all possible configurations have been examined, all solutions have been found, and the algorithm terminates.

#include<stdio.h>
#include<string.h>

#define N 8
#define true 1
#define false 0

void zeroIt (int chess[N][N]);

void
print (int mat[N][N], int q[N])
{
  int i = 0;
  int j = 0;
  int p = 0;

  for (i = 0; i < N; i++)
    {
      p = q[i];
      for (j = 0; j < N; j++)
	{
	  if (p == j)
	    mat[j][i] = 1;

	  printf ("%d  ", mat[j][i]);
	}
      printf ("\n");
    }
}

int
isAttacked (int q[], int n)
{
  int i = 0;
  for (i = 0; i < n; i++)
    {
      if (q[i] == q[n])
	return false;		// same column
      if ((q[i] - q[n]) == (n - i))
	return false;		// same major diagonal
      if ((q[n] - q[i]) == (n - i))
	return false;		// same minor diagonal
    }
  return true;
}

void
solve (int q[N], int col, int chess[N][N])
{

  static count = 0;
  if (col == N)
    {
      printf ("Sol:%d \n", ++count);
      print (chess, q);
// reset chess
      zeroIt (chess);
    }
  else
    {
      int i = 0;
      for (i = 0; i < N; i++)
	{
	  q[col] = i;
	  if (isAttacked (q, col))
	    {
	      solve (q, col + 1, chess);
	    }
	}
    }
}

void
zeroIt (int chess[N][N])
{
  int i, j;
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      chess[i][j] = 0;
}

/* driver code */
main ()
{
// chess board
/*  0  means empty cells and 1 is queen

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
*/

  int chess[N][N];
  zeroIt (chess);
// print(chess,0);
  int a[N];
  solve (a, 0, chess);
}

 Request from community: Please verify above steps,and submit code at myconcept@wikistack.com.

Ref: http://introcs.cs.princeton.edu/java/23recursion/Queens.java.html, wikipedia.org




Related Contents to follow