N-Queens in C

--D. Thiebaut (talk) 12:09, 24 October 2014 (EDT)

---

[12:13:58] ~/temp$: cat queensFirst.c
/*
   queens.c
   D. Thiebaut
   Position N queens on an NxN chess board, and stops after first solution is found.

   Compile and run as follows:
   g++ -O3 queens.c -o queens
   ./queens 8

   (replace 8 by a dimension of your choice, up to the constant MAXN.)
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <time.h>

#define MAXN 40    /* change this to a higher dimension if desired... */
#define EMPTY 0
#define TAKEN 1
#define QUEEN -1000

/* Prototypes */
void clrscr(void);
void gotoxy(int, int);
void Display(int Chessboard[][MAXN], int);
int  addQueen(int, int Chessboard[][MAXN], int);
void Init(int CHessboard[][MAXN]);
int Syntax(int argc, char *argv[]);
void Print(int Chessboard[][MAXN], int N);


int main(int argc, char *argv[]) {
  int N;
  int Chessboard[MAXN][MAXN];
  clock_t start = clock(), end;

  N=Syntax(argc, argv);

  Init(Chessboard);
  addQueen(/* row */ 0, Chessboard, N);
  /*
  if (addQueen( 0, Chessboard, N))
     printf("N=%d solution found!\n",N);
  else
    printf("N=%d no solutions found!\n",N);
  */
  end = clock();
  printf( "%dx%d %1.0f ms\n", N, N,  ((float)(end-start))/CLOCKS_PER_SEC*1000 );

  return 0;
}

int addQueen(int row, int Chessboard[][MAXN], int N) {
  int col, r, c;

  for (col=0; col<N; col++)
    if (Chessboard[row][col]==EMPTY)      {
	/*--- put a queen on board ---*/
	Chessboard[row][col]=QUEEN;
	
	/*--- mark lower diagonals ---*/
	for (r=row+1, c=col+1; r<N && c < N; r++, c++)
	  Chessboard[r][c]++;  /* mark cells on the diagonal as taken */
	for (r=row+1, c=col-1; r<N && c >=0; r++, c--)
	  Chessboard[r][c]++;  /* mark cells on other diag. as taken */
	for (r=row+1; r<N; r++)
	  Chessboard[r][col]++;


	/*--- if on last row, then we found a solution! ---*/
	if (row==N-1)
	    /* Print(Chessboard, N); */
	  return 1;

	else
	  /*--- otherwise, add another queen ---*/
	  if (addQueen(row+1, Chessboard, N))
	    return 1;
	
	/*--- we're now backtracking.  Remove present queen ---*/
	/*--- put a queen on board ---*/
	Chessboard[row][col]=EMPTY;
	
	/*--- mark lower diagonals ---*/
	for (r=row+1, c=col+1; r<N && c < N; r++, c++)
	  Chessboard[r][c]--;  /* unmark cells on the diagonal */
	for (r=row+1, c=col-1; r<N && c >=0; r++, c--)
	  Chessboard[r][c]--;  /* unmark cells on other diag */
	for (r=row+1; r<N; r++)
	  Chessboard[r][col]--;
      }
  return 0;
}

void Print(int Chessboard[][MAXN], int N) {
  static int count=0;
  int r, c;

  printf("solution %2d: ",count++);
  for (r=0; r<N; r++)
      for (c=0; c<N; c++)
	if (Chessboard[r][c]==QUEEN)
	  printf("%d ",c);
  printf("\n");
}

void Display(int Chessboard[][MAXN], int N) {
  int r, c;
  gotoxy(1,1);

  printf("+");
  for (c=0; c<N; c++)
    printf("--"); printf("+\n");
  for (r=0; r<N; r++)
    {
      printf("|");
      for (c=0; c<N; c++)
	if (Chessboard[r][c]==QUEEN)
	  printf(" Q");
	else if (Chessboard[r][c]==EMPTY)
	  printf("  ");
	else
	  printf(" .");
      printf("|\n");
    }
  printf("+");
  for (c=0; c<N; c++)
    printf("--"); printf("+\n");
  
}

void Init(int Chessboard[][MAXN]) {
  int row,col;
  for (row=0; row <MAXN; row++)
    for (col=0; col<MAXN; col++)
      Chessboard[row][col]=EMPTY;
}

int Syntax(int argc, char *argv[]) {
  if (argc <= 1)
    {
      fprintf(stderr,"Syntax: queens N\n");
      fprintf(stderr,"where N is the size of the chessboardn");
      exit(1);
    }
  return atoi(argv[1]);
}

/* ------------------------------oOo----------------------------------- */
void gotoxy(int x, int y) {
  printf("%c[%d;%dH",27,x,y);
}

/* ------------------------------oOo----------------------------------- */
void clrscr(void) {
  gotoxy(1,1);
  printf("%c[J",27);
}