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

//trackers
int solutions[92][64];
int found_sltns = 0;

//data structure to store args for the find_queen fn
struct queens_arg {
  int board[64];
  int focus_idx;
};

/*
 * Counts the number of queens that exists on a board
 */
int no_of_queens(int board[64]) {
  int idx;
  int total = 0;
  #pragma omp parallel for
  for (idx = 0;idx < 64;idx++) {
    if (board[idx] == 1) total++;
  }
  #pragma end parallel for
  return total;
}

/*
 * Counts the number of queens in a row
 */
int on_row(int board[64], int x, int y) {
  int count = 0;
  int i;
  #pragma omp parallel for
  for (i = (y * 8); i < ((y * 8)+8) ;i++) {
    if (board[i] == 1)
      count++;
  }
  #pragma end parallel for
  return count;
}

/*
 * Counts the number of queens in a column
 */
int on_col(int board[64], int x, int y) {
  int count = 0;
  int i;
  #pragma omp parallel for
  for (i = x; i < 64 ;i=i+8) {
    if (board[i] == 1)
      count++;
  }
  #pragma end parallel for
  return count;
}

/*
 * Counts the number of queens in diagonals that run both ways.
 */
int on_diagonal(int board[64], int x, int y) {
  int count = 1;
  int idx = coord_to_idx(x,y);
  int i;

  //northwest direction
  if ((y > 0) && (x > 0))
    for (i = idx - 9; (i >= 0) && (i <= 64) ; i = i - 9) {
      if ((board[i] == 1) && (i != idx))
	count++;
      if (on_edge(i))
	break;
    }
  //northeast direction
  if ((y < 7) && (x > 0))
    for (i = idx - 7; (i >= 0) && (i <= 64) ;i = i - 7) {
      if ((board[i] == 1) && (i != idx))
	count++;
      if (on_edge(i))
	break;
    }
  //southwest direction
  if ((y > 0) && (x < 7))
    for (i = idx + 7; (i >= 0) && (i <= 64) ;i = i + 7) {
      if ((board[i] == 1) && (i != idx))
	count++;
      if (on_edge(i))
	break;
    }
  //southeast direction
  if ((y < 7) && (x < 7))
    for (i = idx + 9; (i >= 0) && (i <= 64) ;i = i + 9) {
      if ((board[i] == 1) && (i != idx))
	count++;
      if (on_edge(i))
	break;
    }

  return count;
}

/*
 * Converts a coordinate to an array index. For example (1,1) refers to index 9.
 */
int coord_to_idx(int x, int y) {
  return (y*8)+x;
}

/*
 * Checks if an index positioning lies on the edge of the board
 */
int on_edge(int idx) {
  int x = idx % 8;
  int y = idx / 8;
  if ((x == 0) || (x == 7) || (y == 0) || (y == 7))
    return 1;
  return 0;
}

/*
 * Checks if all the existing queens (irregardless if it has < 9 or not) are in a good position that prevents them from attacking each other.
 * If so, returns false (0), else return true.
 */
int good_board(int board[64]) {
  int i;
    for (i = 0;i<64;i++)
      if (board[i] == 1) {
	int x = i % 8;
	int y = i / 8;
	if ((on_row(board,x,y) != 1) || (on_col(board,x,y) != 1) || (on_diagonal(board, x, y) != 1))
	  return 0;
      }
  return 1;
}

/*
 * Adds a board to the solution array
 */
void add_solution(int board[64]) {
  int i;
  //check if sltn already exist
  for (i = 0;i<92;i++) {
    if (solutions[i] == board) return;
  }
  #pragma omp parallel for
  for (i = 0;i<64;i++) {
    #pragma omp critical
      solutions[found_sltns][i] = board[i];
    #pragma end critical
  }
  #pragma end parallel for
  found_sltns++;
}

/*
 * Prints a board
 */
void print_board(int board[64]) {
  printf("\n");
  int i;
  for (i = 0;i<64;i++) {
    if (i % 8 == 0) printf("\n");
    printf("%d ", board[i]);
  }
  printf("\n");
}

/*
 * Copies an array from one to another.
 */
void copy_array(int from[64], int to[64]) {
  int i;
  #pragma omp parallel for
  for (i = 0; i<64;i++) {
    if (from[i]) to[i] = 1;
    else to[i] = 0;
  }
  #pragma end parallel for
}

/*
 * Recursive function using backtracking algorithm to find all possible solutions. Solutions are saved with add_solution() method.
 */
void *find_queens(void *args) {

  //vars
  struct queens_arg *data = (struct queens_arg *) args;
  int board[64];
  copy_array(data->board, board);
  int focus_idx = data -> focus_idx;

  //base cases
  if (found_sltns == 92) return;
  if (focus_idx == 64) return;
  if (!good_board(board)) return;

  if (no_of_queens(board) == 8) {
    //found solution
    add_solution(board);
    return;
  }

  //begin the recursion
  if (no_of_queens(board) < 8) {
    //add a queen
    int new_board1[64];
    int new_board2[64];
    int i;
    copy_array(board,new_board1);
    copy_array(board,new_board2);
    new_board1[focus_idx] = 1;

    struct queens_arg *args1 = malloc(sizeof (struct queens_arg));
    struct queens_arg *args2 = malloc(sizeof (struct queens_arg));
    (*args1).focus_idx = focus_idx+1;
    (*args2).focus_idx = focus_idx+1;
    copy_array(new_board1, args1->board);
    copy_array(new_board2, args2->board);

    (*find_queens)(args1);
    (*find_queens)(args2);

    free(args1);
    free(args2);
  }

}

main() {

  //build the board
  int board[64] = {
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
  };

  //begin recursion
  struct queens_arg *args = malloc(sizeof (struct queens_arg));
  args->focus_idx = 0;
  copy_array(board,args->board);
  (*find_queens)(args);

  //prints all possible solutions
  int i;
  for (i = 0;i<found_sltns;i++) {
    print_board(solutions[i]);
  }

  //say goodbye :)
  return 0;
}