#include <iostream>
#include<iomanip>

using namespace std;
void eightQueens(char board[], int size);
void shuffle(char list[], int size);
int linearSearch(char list[], char key, int arraySize);
int linearSearchInt(int list[], int key, int arraySize);




const int SIZE = 8;
int main()
{	char board[SIZE];

	srand(unsigned( time(0)));
	int x = rand()%SIZE;
	for (int i = 0; i < SIZE; i++)
	{
		if (i == x)
			board[i] = 'Q';
		else
			board[i] = ' ';
	}
		eightQueens(board, SIZE);
}
void eightQueens(char board[],int size)
{
	int count = 0, vale, test[SIZE];
	for (int i = 0; i < size ; i++)
	{
		 vale = linearSearch(board, 'Q', size);
		 bool flage = true;
		 
		for (int j = 0; j < count;j++)
		{
			if (test[j] == vale)
				flage = false;
		}
		if (flage == true)
		{
			for (int j = 0; j < size; j++)
			{
				cout  << "|";
				cout << board[j];
			}
			test[count] = vale;
			count++;
			shuffle(board, size);
		}
		else
		{
			int n = 0;
			for (int j = 0; j < 100; j++)
			{
				shuffle(board, size);
				if (linearSearchInt(test, linearSearch(board, 'Q', size), size) == -1)
				{
					n = linearSearch(board, 'Q', size);
					test[count] = n;
					count++;
					break;
				}
			}
			for (int j = 0; j < SIZE; j++)
			{
				if (j == n)
					board[j] = 'Q';
				else
					board[j] = ' ';
			}
			for (int j = 0; j < size; j++)
			{
				cout << "|";
				cout << board[j] ;
			}
			

		}
		cout <<'|'<< endl;
	}
	
}

int linearSearch( char list[], char key, int arraySize)
{
	for (int i = 0; i < arraySize; i++)
	{
			if (key == list[i])
				return i;
	}
	return -1;
}
int linearSearchInt(int list[], int key, int arraySize)
{
	for (int i = 0; i < arraySize; i++)
	{
		if (key == list[i])
			return i;
	}
	return -1;
}
void shuffle(char list[], int size)
{
	
	for (int i = size - 1; i > 0; i--)
	{
		// Generate an index j randomly with 0 <= j <=i
		int j = rand() % (i + 1);
		// Swap myList[i] with myList[j]
		char temp = list[i];
		list[i] = list[j];
			list[j] = temp;
	}
}