#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define INPUT_FILE_NAME "InputData.txt"
#define MAX_BUF 255
#define BY_STDIN 1
#define BY_FILE 0
#define TRUE 1
#define FALSE 0
#define QUEEN_NUM 8

typedef struct boardStatus
{
	int queenPosition[QUEEN_NUM]; /* ?????????????????´??? */
	int advance[QUEEN_NUM]; /* ???????????\?????§??????????????????????????????????????????????????????????????° */
	int vertical[QUEEN_NUM];	/* ????????????????????????????????????????????????????????°(???) */
	int rightUpward[(QUEEN_NUM * 2) - 1];/* ????????????????????????????????????????????????????????°(?????????????????????) */
	int rightDownward[(QUEEN_NUM * 2) - 1];/* ????????????????????????????????????????????????????????°(?????????????????????) */
}boardStatus;

typedef struct Input
{
	FILE* inputFile;
} Input;

/* ??\?????¢??° */ /* ??????????????´ */
/* ?????°	  : howToInput    ??\????????? ( BY_FILE : ??????????????????, BY_STDIN : ?¨??????\????????? ) */
/*          queenPosition ?????????????????´??? */
/*          queenFlag     ????????????????????§???????????????????????????????????° */
/* ????????? :  0  ??£???, /*
/*		     1  ??¨?????? */
/* ??????   : ?????°??§???????????????????????§??\????????????????????? */
/*			??\?????????????????????????????????????????? */
int acceptInput(int inputType, boardStatus *queenFlag);

/* ??????????§£?????¢??° */
/* ?????° : n			    ????????????????????????????????? */
/* 		  queenPosition ?????????????????´??? */
/*        queenFlag     ????????????????????§???????????????????????????????????° */
/* ????????? :  0  , 8?????????????????????????????? */
/*		     1  , ?????????????????????????????????????????? */
/* ?????? : ???????????????????????\????????????????????????????????????????????? */
int solveProblem(int n, boardStatus queenFlag);

/* ?????¢????????? */
/* ?????° : queenPosition ?????????????????´??? */
/* ???????????????????????????????????´??????'Q', ????????\??????'.'??§?????¢(?????????)????????? */
void dispBoard(const int queenPosition[]);

size_t getLine(Input *input, char* buf, size_t bufSize);
Input * createInputByFile(char * filePath);
Input * createInputByStdin();

/* ???????????¢??° */
int main(void) {

	boardStatus queenFlag = { 0 }; /* ????????????????????§???????????????????????????????????° */
	int a;

	/* ???????????????????????\????????????????????? */
	if (acceptInput(BY_STDIN, &queenFlag) == 1) {
		return 1;
	}
	//acceptInput(BY_STDIN);

	/* ??????????§£??? */
	a = solveProblem(0, queenFlag);

	return 0;

}

/* ??\?????¢??° */
int acceptInput(int inputType, boardStatus *queenFlag) {

	Input *input;
	char buf[MAX_BUF + 1]; /* ??????????????§??????1??????????????? */
	size_t lineLen = 0;	/* ?????????????????????????????? */
	int k;	/* ????????????????????????????????????????????° */
	int row, column;	/* ????????????????????? */
	int rowDigit = 1; /* r????????° */
	int i;

	if (inputType == BY_FILE) {
		input = createInputByFile(INPUT_FILE_NAME);
		lineLen = getLine(input, buf, MAX_BUF);
		k = atoi(buf);
		if (k < 0 || QUEEN_NUM + 1 < k) {
			//????????????????????????
			fclose(input->inputFile);
			printf("k??????????????§???");
				return 1;
		}
	}
	else {	/* ?¨??????\????????? */
		input = createInputByStdin();

		while (1) {
			lineLen = getLine(input, buf, MAX_BUF);
			k = atoi(buf);
			if (k < 0 || QUEEN_NUM + 1 < k) {
				printf("k??????????????§???");
			}
			else {
				break;
			}
		}
	}

	for (i = 0; i < k; i++) {
		lineLen = getLine(input, buf, MAX_BUF);
		sscanf(buf, "%d", &row);
		/* r????????°????±??????? */
		if (row != 0) {
			rowDigit = (int)log10(row) + 1;
		}
		sscanf(&buf[rowDigit + 1], "%d", &column);

		if (!queenFlag->advance[row] && 
			!queenFlag->vertical[column] && 
			!queenFlag->rightUpward[row + column] && 
			!queenFlag->rightDownward[row - column + (QUEEN_NUM-1)] ) {

			queenFlag->queenPosition[row] = column; /* ????????????????????? */
			queenFlag->advance[row] = 1;
			queenFlag->vertical[column] = 1;
			queenFlag->rightUpward[row + column] = 1;
			queenFlag->rightDownward[row - column + (QUEEN_NUM -1)] = 1;
		}
		else {
			printf("??????????????????????????????");
			return 1;
		}
	}
	return 0;
}

/* ??????????§£?????¢??° */
int solveProblem(int n, boardStatus queenFlag) {

	int i;

	while (queenFlag.advance[n] && n < QUEEN_NUM) {
		n++;
	}
	if (n == QUEEN_NUM) {
		dispBoard(queenFlag.queenPosition);
		return 0;
	}

	for (i = 0; i <= (QUEEN_NUM - 1); i++) {
		if (!queenFlag.vertical[i] &&
			!queenFlag.rightUpward[n + i] &&
			!queenFlag.rightDownward[n - i + (QUEEN_NUM - 1)]) {

			queenFlag.queenPosition[n] = i;
			queenFlag.vertical[i] = 1;
			queenFlag.rightUpward[n + i] = 1;
			queenFlag.rightDownward[n - i + (QUEEN_NUM - 1)] = 1;

			if (solveProblem(n + 1, queenFlag) == 0) {
				return 0;
			}

			queenFlag.vertical[i] = 0;
			queenFlag.rightUpward[n + i] = 0;
			queenFlag.rightDownward[n - i + (QUEEN_NUM - 1)] = 0;

		}
	}
	return 1;

}

/* ????????????????????¢??° */
void dispBoard(const int queenPosition[]) {

	int i, j;

	/*printf("\n");*/
	for (i = 0; i <= (QUEEN_NUM - 1); i++) {
		/*printf("%d ", queenPosition[i]);*/
		for (j = 0; j <= (QUEEN_NUM - 1); j++) {
			/* ???????????????????????????????????° */
			if (j == queenPosition[i]) {
				printf("Q");
			}
			else {
				printf(".");
			}
		}
		printf("\n");
	}
}

/* 1????????????????????§buf???????´????buf?????????????????? */
size_t getLine(Input *input, char* buf, size_t bufSize)
{
	if ((fgets(buf, bufSize, input->inputFile)) == NULL)
	{
		return 0;
	}

	if (input->inputFile != stdin) {
		printf("%s", buf);
	}

	size_t size = 0;
	while (buf[size + 1] != '\0') {
		size++;
	}
	return size;
}

Input * createInputByFile(char * filePath)
{
	Input* ret = NULL;
	FILE* fp = NULL;

	if ((fp = fopen(filePath, "r")) != NULL) {
		ret = malloc(sizeof(Input));
		ret->inputFile = fp;
	}

	//errno_t err = fopen_s(&fp, filePath, "r");
	//if (fp != NULL && err == 0) {
	//	ret = malloc(sizeof(Input));
	//	/* set members of Input */
	//	ret->inputFile = fp;
	//}

	return ret;
}

Input * createInputByStdin()
{
	Input* ret = NULL;
	ret = malloc(sizeof(Input));
	ret->inputFile = stdin;

	return ret;
}

Measured memory_bytes: 632