/* Title: 8 Queens
*  Author: Ben Miller
*
*  This program is called the 8 queens problem.  The idea is to put 8 queens on an 8 x 8 chess
*  chess board.  No one queen can be in the path of another one queen.  I am using the same
*  numbering system that Charlie gave us in his pseudocode.
*   0 nothing there, nothing covering
*  -1 queen there
*   1 one queen covering
*   2 two queens covering
*   etc.
*
*  I could not get the backtracking to work without using pointers so I
*  used the same idea as Charlie used in his program. 
*/

#include <stdio.h>

#define BOARD_SIZE 8

/* function prototypes */
void put_queen(int [BOARD_SIZE][BOARD_SIZE], int *);
void cover_path(int [BOARD_SIZE][BOARD_SIZE], int, int);
void uncover_path(int [BOARD_SIZE][BOARD_SIZE], int, int);
void display_board(int [BOARD_SIZE][BOARD_SIZE]);

main ()
{
	/* initialize array locations to 0 */
	int chess_board[BOARD_SIZE][BOARD_SIZE] = {0};
	int a = 0;

	put_queen(chess_board, &a);

	exit(1);
}

void put_queen (int board[BOARD_SIZE][BOARD_SIZE], int *column)
{
 /* Recursive algorithm for placing 8 queens on a chess board.  It steps through the board
 *  placing one queen in each row and column.  If a queen cannot be placed then the function
 *  backtracks until it can put a queen in the next column.
 *  Input:
 *    board - a two dimensional array of ints.
 *    column - pointer to the column I am searching to put a queen.
 *  Return:
 *    This function does not return any value.
 */
	int row, a, queen_row;

	for (row=0; row<BOARD_SIZE; row++) {
		/* find a place to put the queen in the column */
		if (board[row][*column] == 0) {
			board[row][*column] = -1;
			cover_path(board, row, *column);
			(*column)++;

			if (*column == BOARD_SIZE) {
				display_board(board);
				printf("Finished successfully.\n");
				exit(1);
			} else
				put_queen(board, &(*column));
		}
	}

	/* if there was not a place to put a queen */
	(*column)--;

	/* find the queen in this column */
	for (a=0; a<BOARD_SIZE; a++)
		if (board[a][*column] == -1) {
			board[a][*column] = 0;
                       	queen_row = a;
                }

	uncover_path(board, queen_row, *column);

	return;
}

void cover_path(int board[BOARD_SIZE][BOARD_SIZE], int row, int column)
{
 /* This function covers all the directions which the queen could move.
 *  Input:
 *    board - a two dimensional array of ints.
 *    row - the row where the queen was placed.
 *    column - the column where the queen was placed.
 *  Return:
 *    This funtion does not return any value.
 */
	int a, next_row, previous_row;

	/* cover column */
	for (a=0; a<BOARD_SIZE; a++)
		if (board[a][column] != -1)
			board[a][column] += 1;
 
	/* cover row */
	for (a=0; a<BOARD_SIZE; a++)
		if (board[row][a] != -1)
                        board[row][a] += 1;

	/* cover right diagonal up */
	previous_row = row - 1;
	for (a=column+1; (a<BOARD_SIZE) && (previous_row >= 0); a++) {
		board[previous_row][a] += 1;
		previous_row--;
	}

	/* cover right diagonal down*/
	next_row = row + 1;
	for (a=column+1; (a<BOARD_SIZE) && (next_row < BOARD_SIZE); a++) {
		board[next_row][a] += 1;
		next_row++;
	}

	/* cover left diagonal up */
	previous_row = row - 1;
	for (a=column-1; (a>=0) && (previous_row >= 0); a--) {
		board[previous_row][a] += 1;
		previous_row--;
	}

	/* cover left diagonal down */
	next_row = row + 1;
	for (a=column-1; (a>=0) && (next_row < BOARD_SIZE); a--) {
		board[next_row][a] += 1;
		next_row++;
	}
	return;
}

void uncover_path (int board[BOARD_SIZE][BOARD_SIZE], int row, int column)
{
 /* This function uncovers all the directions which the queen could of moved.
 *  Input:
 *    board - a two dimensional array of ints.
 *    row - the row where the queen was placed.
 *    column - the column where the queen was placed.
 *  Return:
 *    This funtion does not return any value.
 */
        int a, next_row, previous_row;

        /* cover column */
        for (a=0; a<BOARD_SIZE; a++)
                if (board[a][column] != -1 && board[a][column] != 0)
                        board[a][column] -= 1;

        /* cover row */
        for (a=0; a<BOARD_SIZE; a++)
                if (board[row][a] != -1 && board[row][a] != 0)
                        board[row][a] -= 1;

	/* cover right diagonal up */
        previous_row = row - 1;
        for (a=column+1; (a<BOARD_SIZE) && (previous_row >= 0); a++)
                if (board[previous_row][a] != 0) {
			board[previous_row][a] -= 1;
        	        previous_row--;
        	}

        /* cover right diagonal down*/
        next_row = row + 1;
        for (a=column+1; (a<BOARD_SIZE) && (next_row < BOARD_SIZE); a++)
                if (board[next_row][a] != 0) {
			board[next_row][a] -= 1;
                	next_row++;
        	}

        /* cover left diagonal up */
        previous_row = row - 1;
        for (a=column-1; (a>=0) && (previous_row >= 0); a--)
		if (board[previous_row][a] != 0) {
                	board[previous_row][a] -= 1;
                	previous_row--;
        	}

        /* cover left diagonal down */
        next_row = row + 1;
        for (a=column-1; (a>=0) && (next_row < BOARD_SIZE); a--)
		if (board[next_row][a] != 0) {
	                board[next_row][a] -= 1;
        	        next_row++;
        	}
	return;
}

void display_board(int board[BOARD_SIZE][BOARD_SIZE])
{
	int a = 0, b = 0;

	printf("Here is the location of the queens. \n\n");
	for (a=0; a<BOARD_SIZE; a++) {
		for(b=0; b<BOARD_SIZE; b++) {
			if (board[a][b] == -1)
				printf("   Q");
			else
				printf("%4d", board[a][b]);
		}
		printf("\n\n");
	}

	return;
}