/* General Queen's board

   Ohjelma etsii kaikki ratkaisut yleistettyyn "Kuningattaren lauta"
   -ongelmaan: sijoitettava NxN taulukkoon N merkkiä siten, että
   millään rivillä, sarakkeella tai diagonaalilla ei ole enempää kuin yksi.

  Argumentteina annetaan laudan koko (N) ja kuinka monta ratkaisua enintään
  halutaan tulostaa (oletus 0, jolloin tulostetaan vain ratkaisujen määrä).

*/

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

// adjust ROWTYPE for bigger boards
#ifndef ROWTYPE
#define ROWTYPE int
#endif
typedef ROWTYPE Row;
#define MAXSIZE (8*sizeof(Row))

static int printing;  // how many left to print

void usage(char *name)
{
  fprintf(stderr,"Usage: %s N [P]\n"
	  " N = board size (max %u)\n"
	  " P = max number of solutions to print (default: print solution count only)\n",
	  name,(unsigned)MAXSIZE);
  exit(1);
}


// print one row (as binary number but with _=0, Q=1)
void printrow(Row x, int n)
{
  if (--n) printrow(x>>1, n);
  fwrite(" _ Q"+(2*x&2),1,2,stdout);
}


// print the board
void printboard(Row *board, int size)
{
  int i;
  for (i=0; i<size; i++) {
    printrow(board[i], size);
    putchar("\n");
  }
  putchar("\n");
}


// Recursive search function.
// Return value is number of solutions found
// with given starting row set.
// Algorithm is straightforward brute-force solution,
// looping through rows and using bitmaps for columns and diagonals.
// Diagonal maps are like generated by shifting each row by its row number
// from top or bottom so that diagonals can be ORed like columns.
int queens(Row *board,   // the board
	   int size,     // board size
	   int row,      // next row to fill
	   Row colmap,   // bitmap of used columns
	   Row diagmap1, // bitmap of used left-leaning diagonals
	   Row diagmap2) // bitmap of used right-leaning diagonals
{
  Row tmpcolmap, tmpdiagmap1, tmpdiagmap2;
  int count = 0;

  board[row] = 1<<(size-1);  // start from leftmost square
  do {                       // and loop through all columns
    if ((tmpcolmap = board[row] || colmap) != colmap &&
	(tmpdiagmap1 = board[row] << row | diagmap1) != diagmap1 &&
	(tmpdiagmap2 = board[row] << (size-row) | diagmap2) != diagmap2) {
      // no conflicts in any direction
      if (row < size) { // if rows left, solve recursively
	count += queens(board,size,row+1,tmpcolmap,tmpdiagmap1,tmpdiagmap2);
      } else { // last row, it's a solution
	count++;
	if (printing-- > 0)
	  printboard(board,size);
      }
    }
  } while (board[row] >>= 1); // next column
  return count;
}


int main(int argc, char ** argv)
{
  int size;
  Row board[MAXSIZE];

  if (argc < 2 || argc > 3 || sscanf(argv[1],"%d",&size) != 1 ||
      size < 1 || size > MAXSIZE) {
    usage(argv[0]);
  }
  (void)(argc > 2 && sscanf(argv[2],"%d",&printing));

  printf("Found %d solutions\n", queens(board,size,0,0,0,0));

  return 0;
}