/* Roger Jang, Oct 1996 */
/* This program is tested on Sun SparcStation */

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

#define SIZE 8

void
print_matrix(int board[][SIZE]) {
	int i, j;
	for (i=0; i<SIZE; i++) {
		for (j=0; j<SIZE; j++)
			printf("%1d ", board[i][j]);
		printf("\n");
	}
	printf("\n");
}

int
select_pos(int current_pos[], int board[][SIZE]) {
	int i, j, picked;
	int pos_n = 0;

	for (i=0; i<SIZE; i++)
		for (j=0; j<SIZE; j++)
			if (board[i][j]==0) pos_n++;
	if (0==pos_n)
		return(0);

	picked = rand()%pos_n + 1;
	/*
	printf("pos_n = %d, picked = %d\n", pos_n, picked);
	*/

	for (i=0; i<SIZE; i++)
		for (j=0; j<SIZE; j++)
			if (board[i][j]==0) {
				picked--;
				if (picked == 0) {
					current_pos[0] = i;
					current_pos[1] = j;
					return(1);
				}
			}
}

void
update_board(int pos[], int board[][SIZE]){

	int i, j;
	int x=pos[0], y=pos[1];
	
	for (i=x+1; i<SIZE; i++)
		if (0==board[i][y]) board[i][y]=1;
	for (i=x-1; i>=0; i--)
		if (0==board[i][y]) board[i][y]=1;
	for (j=y+1; j<SIZE; j++)
		if (0==board[x][j]) board[x][j]=1;
	for (j=y-1; j>=0; j--)
		if (0==board[x][j]) board[x][j]=1;

	for (i=x+1,j=y+1; i<SIZE && j<SIZE; i++,j++)
		if (0==board[i][j]) board[i][j]=1;
	for (i=x-1,j=y-1; i>=0 && j>=0; i--,j--)
		if (0==board[i][j]) board[i][j]=1;
	for (i=x+1,j=y-1; i<SIZE && j>=0; i++,j--)
		if (0==board[i][j]) board[i][j]=1;
	for (i=x-1,j=y+1; i>=0 && j<SIZE; i--,j++)
		if (0==board[i][j]) board[i][j]=1;
}

int
main(){
	/* board value: 0 -> available, 1 -> forbidden, 2 -> occupied.*/
	int board[SIZE][SIZE];
	int current_pos[2];
	int i, j;
	int done = 0, try_n = 0;
	int success;

	srand(time(NULL));
	while (done != 1) {
		/* Initial board */
		for (i=0; i<SIZE; i++)
			for (j=0; j<SIZE; j++)
				board[i][j]=0;
		try_n++;
		printf("Try %d: ", try_n);
		for (i=0; i<SIZE; i++) {
			success = select_pos(current_pos, board);
			if (success == 0) {
				printf("%d queens have been placed\n", i);
				break;
			}
			board[current_pos[0]][current_pos[1]] = 2;
			update_board(current_pos, board);
		}
		if (i == SIZE)
			done = 1;
	}
	printf("Congratulations on successfully placed all 8 queens! \n\n");
	print_matrix(board);
	
	getchar();
	return(0);
}