/*
 * Find a placment of queens on a chessboard such that they 
 * can't attack each other.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum {
	EMPTY = '.',
	QUEEN = 'q',
	BOARD_SIZE = 6,
	N_QUEENS = 6
};
	
void initialize_board(int chessboard[BOARD_SIZE][BOARD_SIZE]);
void place_queens(int chessboard[BOARD_SIZE][BOARD_SIZE], int nQueens);
int no_queens_attack_each_other(int chessboard[BOARD_SIZE][BOARD_SIZE]);
void print_board(int chessboard[BOARD_SIZE][BOARD_SIZE]);

/*
 * Find a placement of N_QUEENS queens on a BOARD_SIZE size chessboard
 * such that no queen attacks any other.
 *
 * This is done by generating a placement randomly and testing
 * if any two queens can attack each other and repeating this
 * until a suitable placement is found
 *
 * Much more efficient approaches exist to this problem!
 */
 
/*
 * Don't change this function.
 */
 
int
main(void) {
	int board[BOARD_SIZE][BOARD_SIZE];

	srand(time(NULL));
	while (1) {
		initialize_board(board);
		place_queens(board, N_QUEENS);
		if (no_queens_attack_each_other(board))
			break;
	}
	print_board(board);
	return 0;
}


/*
 * given a chessboard, return false, iff any two queens can attack
 * each other, return true otherwise
 *
 * Two queens can attack each other if they are on
 * the same row, the same column or the same diagonal
 * of the chessboard.
 */
	
int
no_queens_attack_each_other(int chessboard[BOARD_SIZE][BOARD_SIZE]) {
	/*
	 * put your code here
	 */
	 	
	return 1;
}

/*
 * Don't change the functions below here
 */
 
/*
 * initialize the squares of the chessboard to EMPTY
 */
void
initialize_board(int chessboard[BOARD_SIZE][BOARD_SIZE]) {
	int i, j;
	
	for (i = 0; i < BOARD_SIZE; i++)
		for (j = 0; j < BOARD_SIZE; j++)
			chessboard[i][j] = EMPTY;
}

/*
 * place n_queens in random positions
 * on a chessboard.
 */
void
place_queens(int chessboard[BOARD_SIZE][BOARD_SIZE], int n_queens) {
	int i, x, y;
	i = 0;
	while (i < n_queens) {
		x = rand() % BOARD_SIZE;
		y = rand() % BOARD_SIZE;
		if (chessboard[x][y] != EMPTY)
			continue;
		chessboard[x][y] = QUEEN;	
		i++;
	}
}

/*
 * print the chessboard
 */
void
print_board(int chessboard[BOARD_SIZE][BOARD_SIZE]) {
	int i, j;
	
	printf("\n\n");
	for (i = 0; i < BOARD_SIZE; i++) {
		for (j = 0; j < BOARD_SIZE; j++)
			printf("%c ", chessboard[i][j]);
		printf("\n\n");
	}
	printf("\n\n");
}