N Queen Problem Solution done in C language.

nqueen.c

#include <stdio.h>
#include <stdlib.h>

#define N_MAX_BOARD_ROW_SIZE 15
/*
 Board array keeps queen placement(column index) on given indexed row value
 Example board allocation for N = 4
   1 2 3 4
 1 - Q - -
 2 - - - Q
 3 Q - - -
 4 - Q - -
 Quenn indexes will be setted on board array as below:
 board[1] = 2
 board[2] = 4
 board[3] = 1
 board[4] = 3
 */
int board[N_MAX_BOARD_ROW_SIZE] = { 0 };

// drawing character for blank place of chess board
const char bullet_code = 'x';

enum PrintingStepType {
  Searching,
  Placed,
  RollingBack,
  FoundSolution
};

// number of total iterations
int step_count = 0;

// problem size for current operation [4 < n <= 13]
int problem_size = 0;

// command line argument for step debugging
int wait_for_enter = 1;

/* function declerations */
// main function to search solution path recursively
int queen(int row, const int n);

// checks whether queen can be placed in given position or not
int place(int row, int column);

// prints descriptions
void printMenu();

// prints current state of chess board
void printTable(int n);

// clears the console output
void clear_screen();

int main(int argc, char *argv[]) {
  
  // checking command line arguments for step debugging
  if (argc > 1) {
    // set wait_for_enter active if any
    wait_for_enter = *argv[1] == '0' ? 0 : 1;
  }
  
  do {
    clear_screen();
    printMenu();
    scanf("%d", &problem_size);
  } while (problem_size < 4 || problem_size > 13); // try to get N value from console until the value is acceptable
  
  // start with start position
  if (queen(1, problem_size) == 1) {
    printTable(problem_size);
  }
  
  printf("\n");
  system("pause");
  return 0;
}

void printMenu() {
  printf("\t- N Queens Problem Using Backtracking -");
  printf("\n\nEnter number of Queens[Must be between 4 and 13]:");
}

//function for printing the solution
void printTable(int n) {
  int i, j;
  //clear_screen();
  printf("\n\nSolution:\n\n");
  
  printf(" ");
  for (i = 1; i <= n; ++i)
    printf("  %d", i);
  
  for (i = 1; i <= n; ++i) {
    printf("\n\n%d", i);
    for (j = 1; j <= n; ++j) //for nxn board
    {
      if (board[j] == i)
        printf("  Q"); //queen at i,j position
      else
        printf("  %c", bullet_code); //empty slot
    }
  }
  printf("\n");
}

void printStep(int row, int step_type) {
  int i, j;
  if (wait_for_enter == 0) return;
  
  clear_screen();
  printf("\n\nStep [%d] [Column %d]: ", ++step_count, row);
  
  switch (step_type) {
    case Searching:
      printf("[Searching a valid place to queen]");
      break;
    case RollingBack:
      printf("[No solution are found for this layout! Rolling back]");
      break;
    case Placed:
      printf("[Queen is placed]");
      break;
    case FoundSolution:
      printf(" Problem is solved! All queens are in right place");
      return;
      break;
    default:
      printf(" Upps!!!...");
      break;
  }
  printf("\n\n");
  
  printf(" ");
  for (i = 1; i <= problem_size; ++i)
    printf("  %d", i);
  
  for (i = 1; i <= problem_size; ++i) {
    printf("\n\n%d", i);
    for (j = 1; j <= problem_size; ++j) //for nxn board
    {
      if (board[j] == i)
        printf("  Q"); //queen at i,j position
      else
        printf("  %c", bullet_code); //empty slot
    }
  }
  printf("\n\nPress enter to continue..");
  getchar();
}

// Funtion to check conflicts. If no conflict for desired postion returns 1 otherwise returns 0
int place(int row, int column) {
  int i;
  // checking column and digonal conflicts
  for (i = 1; i <= row - 1; ++i) {
    if (board[i] == column) // "board[i] == column" means queen at i-th row is placed at column-th column.
      return 0;
    else
      // checking diagonal conflict
      if (abs(board[i] - column) == abs(i - row))
        return 0;
    // Queens placed at (x1, y1) and (x2,y2)
    // x1==x2 means same rows, y1==y2 means same columns, |x2-x1|==|y2-y1| means
    // they are placed in diagonals.
  }
  return 1; //no conflicts
}

//function to check for proper positioning of queen
int queen(int row, const int n) {
  int column;
  
  // base case: if searching row count is bigger than the problem size, it means all queens are placed successfully.
  if (row > n) {
    return 1;
  }
  
  printStep(row, Searching);
  // search place for queen
  for (column = 1; column <= n; ++column) {
  	
  	// check if queen can be placed to given position
    if (place(row, column)) {
    
      // no conflicts so place queen
      board[row] = column;
      
      printStep(row, Placed);
      
	  // check if we can go further(continue) with this arrangement 
      if (queen(row + 1, n) == 1) {
        printStep(row, FoundSolution);
        return 1;
      }
      
      // if there are dead end for this arrangement than rollback and try another permutation
      printStep(row, RollingBack);
      board[row] = 0; // backtrack
    }
  }
  return 0;
}

void clear_screen() {
#ifdef WIN32
  system("cls");
#else
  system("clear");
#endif
}