/*
  Problema 27 (8 rainhas).  Escreva um programa que resolve o problema
  das 8 rainhas: 

  https://en.wikipedia.org/wiki/Eight_queens_puzzle

  (exemplos de execução abaixo)
 */ 

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

#define NMAX 20
#define TRUE 1
#define FALSE 0

void solve(int N);
void solveR(int a[], int k, int N);
void exch(int a[], int i, int j);

int should_btrack(int a[], int k, int N);
  
int main(int argc, char *argv[])
{
  int N = atoi(argv[1]);

  if (N > NMAX) {
    printf("N deve ser no maximo %d\n", NMAX);
    exit(0);
  }

  solve(N);
  
  return 0;
}

void solve(int N)
{
  int a[NMAX], i;
  for (i = 0; i < N; i++) 
    a[i] = i;

  solveR(a, 0, N);
}

/*
 * Para k = N, imprime a[], que é uma solução do
 * problema das N rainhas. Para  k < N, faz 
 * a[0..N - 1] assumir todas as soluções 
 * com prefixo a[0..k - 1] dado.  Imprime todas essas
 * soluções.  Ao término de uma chamada de solveR(), 
 * a[] está no mesmo estado que quando ela foi chamada. 
 */
void solveR(int a[], int k, int N)
{
  int i;
  if (k == N) {
    int i;
    for (i = 0; i < N; i++) 
      printf("%d ", a[i]);
    printf("\n");
    return;
  }
  for (i = k; i < N; i++) {
    exch(a, k, i);;
    if (!should_btrack(a, k, N))
      solveR(a, k + 1, N);
    exch(a, k, i); /* põe a[] no estado inicial */
  }
}

void exch(int a[], int i, int j)
{
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
}

int should_btrack(int a[], int k, int N)
{
  int i;
  for (i = 0; i < k; i++) {
    if (a[k] - a[i] == k - i) return TRUE;
    if (a[i] - a[k] == k - i) return TRUE;
  }
  return FALSE;
}

/*
$ p27 4
1 3 0 2 
2 0 3 1 
$ p27 5
0 2 4 1 3 
0 3 1 4 2 
1 3 0 2 4 
1 4 2 0 3 
2 0 3 1 4 
2 4 1 3 0 
3 1 4 2 0 
3 0 2 4 1 
4 1 3 0 2 
4 2 0 3 1 
$ p27 6
1 3 5 0 2 4 
2 5 1 4 0 3 
3 0 4 1 5 2 
4 2 0 5 3 1 
$ p27 14 | wc -l
  365596
$ 
 */