#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 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, int *queenPosition, boardStatus *queenFlag);

/* ??????????§£?????¢??° */
/* ?????° : n			    ????????????????????????????????? */
/* 		  queenPosition ?????????????????´??? */
/*        queenFlag     ????????????????????§???????????????????????????????????° */
/* ????????? :  0  , 8?????????????????????????????? */
/*		     1  , ?????????????????????????????????????????? */
/* ?????? : ???????????????????????\????????????????????????????????????????????? */
int solveProblem(int n, int queenPosition[], 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) {

	int queenPosition[QUEEN_NUM]; /* ?????????????????´??? */
	boardStatus queenFlag; /* ????????????????????§???????????????????????????????????° */
	int i;

	for (i = 0; i < QUEEN_NUM; i++) {
		queenPosition[i] = -1;
		queenFlag.advance[i] = 0;
		queenFlag.vertical[i] = 0;
	}
	for (i = 0; i < (QUEEN_NUM * 2) - 1; i++) {
		queenFlag.rightDownward[i] = 0;
		queenFlag.rightUpward[i] = 0;
	}
	

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

	/* ??????????§£??? */
	if (solveProblem(0, queenPosition, queenFlag) == 0) {
		/* ?§£????????? */
		dispBoard(queenPosition);
	}

	return 0;

}

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

	Input *input;
	char buf[MAX_BUF + 1]; /* ??????????????§??????1??????????????? */
	size_t lineLen = 0;	/* ?????????????????????????????? */
	int k;	/* ????????????????????????????????????????????° */
	int r, c;	/* ????????????????????? */
	int rDigit = 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", &r);
		/* r????????°????±??????? */
		if (r != 0) {
			rDigit = (int)log10(r) + 1;
		}
		sscanf(&buf[rDigit + 1], "%d", &c);

		if (!queenFlag->advance[r] && !queenFlag->vertical[c] && !queenFlag->rightUpward[r + c] && !queenFlag->rightDownward[r - c + (QUEEN_NUM-1)] ) {
			queenPosition[r] = c; /* ????????????????????? */
			queenFlag->advance[r] = 1;
			queenFlag->vertical[c] = 1;
			queenFlag->rightUpward[r + c] = 1;
			queenFlag->rightDownward[r - c + (QUEEN_NUM -1)] = 1;
		}
		else {
			printf("??????????????????????????????");
			return 1;
		}
	}
	return 0;
}

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

	int i;

	while (queenFlag.advance[n] && n < QUEEN_NUM) {
		n++;
	}
	if (n >= QUEEN_NUM) {
		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)]) {

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

			if (solveProblem(n + 1, queenPosition, 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