U E D R , A S I H C RSS

Eight Queen Problem/서상현

~cpp 

#include <stdio.h>
#define NUM 8

int n = NUM;
int board[NUM][NUM] = {0,};

void print()
{
	int i, j;
	for (i=0; i<n; i++) {
		for (j=0; j<n; j++) {
			printf("%d", board[i][j]);
			printf(" ");
		}
		printf("\n");
	}
}

int safe(int x, int y)
{
	int d;
	int xx, yy;
	int drct[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
	if (board[x][y]) return 0;
	for (d=0; d<8; d++) {
		xx = x + drct[d][0];
		yy = y + drct[d][1];
		while ((0<=xx && xx<n) && (0<=yy && yy<n)) {
			if (board[xx][yy]) return 0;
			xx += drct[d][0];
			yy += drct[d][1];
		}
	}
	return 1;
}

int recur(int level)
{
	int i, j;
	if (level == n) {
		print();
		return 1;
	}
	else {
		for (i=0; i<n; i++) {
			for (j=0; j<n; j++) {
				if (safe(i, j)) {
					board[i][j] = 1;
					if (recur(level+1))
						return 1;
					board[i][j] = 0;
				}
			}
		}
		return 0;
	}
}

void main()
{
	recur(0);
}


모든 해를 출력하려면 recur 함수를 이렇게 고친다.

~cpp 

void recur(int level)
{
	int i, j;
	if (level == n) {
		print();
	}
	else {
		for (i=0; i<n; i++) {
			for (j=0; j<n; j++) {
				if (safe(i, j)) {
					board[i][j] = 1;
					recur(level+1);
					board[i][j] = 0;
				}
			}
		}
	}
}

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0083 sec