8960 - N Queens Problem.c

/**********************************************************************************************************
NAME: CANDIDA RUTH NORONHA
CLASS: SE COMPS B
ROLL NO. : 8960
BATCH: C
TITLE: N QUEENS PROBLEM
SUBMISSION DATE : 12th APRIL, 2021
**********************************************************************************************************/

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

int board[20], count;

int main()
{
  int n, i, j;
  void queen(int row, int n);

  printf("\n------------------------------------------------------------------------------------------------\n");
  printf("\n\t\t\t\t N Queens Problem Using Backtracking\n");
  printf("\n------------------------------------------------------------------------------------------------\n");

  printf("\n Enter the Number of Queens : ");
  scanf("%d", &n);
  printf("\n------------------------------------------------------------------------------------------------\n");

  queen(1, n);
  return 0;
}

//function for printing the solution
void print(int n)
{
  int i, j;

  printf("\n Solution %d : \n\n", ++count);

  for (i = 1; i <= n; ++i)
    printf("\t%d", i);


  for (i = 1; i <= n; ++i)
  {
    printf("\n\n%d", i);
    for (j = 1; j <= n; ++j) //for nxn board
    {
      if (board[i] == j)
        printf("\tQ"); //queen at i,j position
      else
        printf("\t-"); //empty slot
    }
  }
  printf("\n------------------------------------------------------------------------------------------------\n");
}

/*function to check conflicts If no conflict for desired position returns 1 otherwise returns 0*/
int place(int row, int column)
{
  int i;
  for (i = 1; i <= row - 1; ++i) {
    //checking column and diagonal conflicts
    if (board[i] == column)
      return 0;
    else
    if (abs(board[i] - column) == abs(i - row))
      return 0;
  }
  return 1; //no conflicts
}

//function to check for proper positioning of queen
void queen(int row, int n)
{
  int column;
  for (column = 1; column <= n; ++column)
  {
    if (place(row, column))
    {
      board[row] = column; //no conflicts so place queen
      if (row == n) //dead end
        print(n); //printing the board configuration
      else //try queen with next position
        queen(row + 1, n);
    }
  }
}

/**********************************************************************************************************

OUTPUT:

------------------------------------------------------------------------------------------------

                                 N Queens Problem Using Backtracking
								 
------------------------------------------------------------------------------------------------

 Enter the Number of Queens : 4

------------------------------------------------------------------------------------------------

 Solution 1 :

        1       2       3       4

1       -       Q       -       -

2       -       -       -       Q

3       Q       -       -       -

4       -       -       Q       -
------------------------------------------------------------------------------------------------

 Solution 2 :

        1       2       3       4

1       -       -       Q       -

2       Q       -       -       -

3       -       -       -       Q

4       -       Q       -       -
------------------------------------------------------------------------------------------------

**********************************************************************************************************/