queens.c

#include <stdio.h>
#include <stdlib.h>
#define BOARD_SIZE 8

void print_rows(int row[], int len) {
  int i;
  for (i = 0; i < len; ++i) {
    printf("%d ", row[i]);
  }
  printf("\n");
}

// check_configuration takes a partial configuration, and the row
// in which we want to place the next queen, and returns true only
// if the new configuration is one where the new queen is not attacking
// any other queen.
int check_configuration(int queens_placed, int row[], int next) {
  int i;
  for (i = 0; i < queens_placed; ++i) {
    // same row
    if (row[i] == next) {
      return 0;
    }
    // same diagonal
    if (queens_placed - i == abs(row[i] - next)) {
      return 0;
    }
  }
  return 1;
}

// place_queens implements a recursive algorithm to place queens.
// A valid configuration of queens can be represented by the array row[],
// where row[0] is the row of the queen in the 0th column, and so on.
void place_queens(int queens_placed, int row[]) {
  if (queens_placed == BOARD_SIZE) {
    print_rows(row, BOARD_SIZE);
    return;
  }
  int i;
  // We are trying to place a queen in the queens_placed column.
  // Try placing a queen in every row, and see if the configuration
  // is valid.
  for (i = 0; i < BOARD_SIZE; ++i) {
    if (check_configuration(queens_placed, row, i)) {
      row[queens_placed] = i;
      place_queens(queens_placed + 1, row);
    }
  }
}

int main() {
  int row[BOARD_SIZE];
  place_queens(0, row);
}