/* This program computes ALL solutions to the n-queens problem. */
/* The board size is input at the beginning of execution.	*/

/* From Wirth's Algorithms+Data Structures = Programs.          */
/* This program is suitable for a code-generation benchmark,	*/
/* especially given common sub-expressions in array indexing.	*/
/* See the Programmer's Guide for how to get a machine code     */

#define False 0
#define True 1
#define Boolean char

#include <stdio.h>

typedef int Integer;

static Boardsize=0;

#define MaxBoardsize 20

#define Asub(I)  A[(I)-1]
#define Bsub(I)  B[(I)-2]
#define Csub(I)  C[(I)+MaxBoardsize-1]
#define Xsub(I)  X[(I)-1]

static Boolean A[MaxBoardsize /* 1. .MaxBoardsize */];
static Boolean B[MaxBoardsize+MaxBoardsize-1 /* 2..(MaxBoardsize+MaxBoardsize) */];
static Boolean C[MaxBoardsize+MaxBoardsize-1 /*-(MaxBoardsize-1)..(MaxBoardsize-1) */];
static Integer X[MaxBoardsize /* 1.. MaxBoardsize */];

static Solutions=0;

#if 0
static void Print() {
   Integer I;
   for (I = 1; I <= Boardsize;)
      printf("%4d",Xsub(I++));
   printf("\n");
   }
#else
/* Get rid of output provided above, for benchmarking;
   change if 0 to if 1 above to see all the solutions:
*/
#define Print()
#endif
static void Try(I) Integer I; {
   Integer J;
   for (J = 1; J <= Boardsize; J++)
      if (Asub(J) && Bsub(I+J) && Csub(I-J)) {
	 Xsub(I) = J;
	 Asub(J) = False; Bsub(I+J) = False; Csub(I-J) = False;
	 if (I < Boardsize) Try(I+1); else {Print(); Solutions++;}
	 Asub(J) = True; Bsub(I+J) = True; Csub(I-J) = True;
	 }
   }

void main () {
   Integer J,I,iter;
   printf("Board size? ");
   scanf(" %d",&Boardsize);
   printf("No. of iterations? ");
   scanf(" %d",&iter);
   printf("Starting test...");
   for (J = 0; J < iter; J++) {
      for (I =	1; I <=  Boardsize; Asub(I++) = True);
      for (I =	2; I <= Boardsize+Boardsize; Bsub(I++) = True);
      for (I = -(Boardsize-1); I <=  Boardsize+1; Csub(I++) = True);
      Try(1);
      }
   printf("End of test; %d solutions.\n",Solutions);
   }
