티스토리 뷰

Algorithm

N Queen Problem - Backtracking

Dev gOm 2016. 11. 30. 19:00

Approach

N Queen Problem 문제를 가장 기본적인 Deterministic Algorithm(Backtraking) 을 이용하여 풀어본 코드.

자세한 내용은 추후 정리.


Code

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

#define TRUE 1
#define FALSE 0

int promising(int);
void queens(int);
void print();

int* col;
int N;
FILE *output;

int main(void)
{
	FILE *file;
	char file_name[255];
	int i;

	printf("input file name?");
	scanf("%s", &file_name);
	file = fopen(file_name, "r");
	output = fopen("output.txt", "w");
	N = getc(file) - '0';

	col = (int*)malloc(sizeof(int) * (N+1));

	for (i = 0; i <= N; ++i)
		col[i] = 0;

	queens(0);

	return 0;
}

int promising(int i)
{
	int k;
	int result;

	k = 1;
	result = TRUE;

	while (k < i&&result)
	{
		if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
			result = FALSE;
		k++;
	}

	return result;
}

void queens(int h)
{
	int i;

	if (promising(h)) {
		if (h == N) {
			print();
			exit(1);
		}
		else
		{
			for (i = 1; i <= N; ++i)
			{
				col[h+1] = i;
				queens(h + 1);
			}
		}
	}
}

void print()
{
	int i;
	for (i = 1; i <= N; ++i)
	{
		fprintf(output,"%d\n", col[i]);
	}
}


'Algorithm' 카테고리의 다른 글

2751 - Heap sort  (0) 2016.12.01
2665 - 미로 만들기 + 경로 출력  (0) 2016.11.30
2448_별찍기 - 11  (0) 2016.10.13
Matrix chain multiplication  (0) 2016.10.12
Floyd's Algorithm  (0) 2016.10.12
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함