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

#define SIZE 8

int isBoardvalid(int board[SIZE][SIZE], int Row[8]);
int printArray(int array[SIZE][SIZE]);
int clearColumn(int board[SIZE][SIZE], int Column);
int arrayAllZero(int board[SIZE][SIZE]);

int main()
{
	srand(time(0));

	int board[SIZE][SIZE] = { 0 }; // chessboard
	int Row[8] = { 0 }; // each column owns a queen , array Row record which row the queen is locate in each column
	int count = 0; // counter for how many times the creation and validation checking of the board
	int Column = 0; // there are 8 columns , each column owns a queen

	while (1)
	{
		arrayAllZero(board);

		// create a pattern randomly
		for (Column = 0; Column < SIZE; Column++)
		{
			Row[Column] = rand() % 8; // assign which row the queen is locate in each column randomly
		}

		for (Column = 0; Column < SIZE; Column++)
		{
			board[Row[Column]][Column] = 1; // assign the location of queen value 1
		}

		count++;

		if (isBoardvalid(board, Row) == 0) // the pattern is valid
		{
			printf("The %d-th solution\n", count);
			printArray(board);
			return 0;
		}

	}
	return 0;
}

// Find if the board valid or not , array Row record the position of queens
// Return 0 if valid
// Return 1 if not valid
int isBoardvalid(int board[SIZE][SIZE], int Row[8])
{
	int Column = 0;
	int count = 0;
	int i = 0;

	for (Column = 0; Column <= 7; Column++) // 8-1 = 7
	{
		// board[Row[Column]][Column] is the position of queen

		for (i = -7; i <= 7; i++)
		{
			if (i != 0) // if i = 0 , it's the position of queen herself
			{
				if (Column + i >= 0 && Column + i < 8 && board[Row[Column]][Column + i] != 0)
				{
					count++; // rule out same row
				}

				if (Row[Column] + i >= 0 && Row[Column] + i < 8 && board[Row[Column] + i][Column] != 0)
				{
					count++; // rule out same column
				}

				if (Row[Column] + i >= 0 && Row[Column] + i < 8 && Column + i >= 0 && Column + i < 8 && board[Row[Column] + i][Column + i] != 0)
				{
					count++; // rule out upper right diagonal
				}

				if (Row[Column] + i >= 0 && Row[Column] + i < 8 && Column - i >= 0 && Column - i < 8 && board[Row[Column] + i][Column - i] != 0)
				{
					count++; // rule out lower left diagonal
				}
			}
		}
	}

	if (count == 0) // no queen attacks another
	{
		return 0; // the board is valid
	}
	else
	{
		return 1; // the board is not valid
	}
}

// Print an array , mark the posiotion of queen
int printArray(int array[SIZE][SIZE])
{
	int i = 0;
	int j = 0;

	for (i = 0; i < SIZE; i++)
	{
		printf("-----");
	}
	printf("-\n");

	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{

			if (array[i][j] == 1)
			{

				printf(". Q  ");
			}
			else
			{
				printf(".    ");
			}
		}
		printf(".\n");
		for (j = 0; j < SIZE; j++)
		{
			printf("-----");
		}
		printf("-\n");
	}
	return 0;
}

// Assign 0 to all the elements of assigned column
int clearColumn(int board[SIZE][SIZE], int Column)
{
	int i = 0;
	int j = 0;

	for (i = 0; i < SIZE; i++)
	{
		board[i][Column] = 0;
	}
	return 0;
}

// Assign 0 to all the array element
int arrayAllZero(int board[SIZE][SIZE])
{
	int i = 0;
	int j = 0;

	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			board[i][j] = 0;
		}
	}
	return 0;
}