N-Queen

#include<iostream>
#include<cstdio>

using namespace std;

int n;
int map[16][16];
bool check[16];
int ans;

int dx[] = { -1,1,0 };
int dy[] = { -1,-1,-1 };
bool checking(int x, int y) {
	if (y <= 1) return true;
	for (int i = 0; i < 3; i++) {
		int nx = x + dx[i]; int ny = y + dy[i];
		while (nx <= n && ny <= n && nx > 0 && ny > 0) {
			if (map[nx][ny] == 1) return false;
			nx += dx[i]; ny += dy[i];
		}
	}
	return true;
}
bool cc(int x) {
	for (int i = 1; i <= n; i++) {
		if (x == check[i]) false;
	}
	return true;
}

void go(int x, int y) {
	if (y > n) {
		ans++;
		return;
	}
	map[x][y] = 1;
	
	check[y] = true;
	if (checking(x, y) == false) {
		map[x][y] = 0;
		check[x] = false;
		return;
	}
	if (y == n)
		go(0, n + 1);
	else {
		for (int i = 1; i <= n; i++) {
			if (i != x && i != x + 1 && i != x - 1) {
				if (!cc(i)) {
					map[x][y] = 0;
					check[x] = false;
					return;
				}
				go(i, y + 1);
			}
		}
	}
	map[x][y] = 0;
	check[x] = false;

}

int main() {
	cin >> n;

	ans = 0;
	for (int i = 1; i <= n; i++) {
		go(i, 1);
	}

	cout << ans << '\n';


	return 0;
}

map써서 한것도있고, 검사할때 세방향으로 진행하는 과정은 시간복잡도가 한방향일때 보다 압도적으로 커지게된다.

당연히 시간초과

 

#include<iostream>
#include<cstdio>

using namespace std;

int n;
int col[16];
int ans;
bool checking(int i) {
	for (int j = 0; j < i; j++) {
		if (col[j] == col[i] || abs(col[i] - col[j]) == i - j)
			return false;
	}
	return true;
}
void go(int i) {
	if (i == n ) {
		ans++;
		return;
	}
	else {
		for (int j = 0; j < n; j++) {
			col[i] = j;
			if (checking(i))
				go(i + 1);
		}
	}
}

int main() {
	cin >> n;
	
		go(0);
	cout << ans << "\n";
	return 0;
}

cols 배열 하나만 통해서, 백트래킹한 코드 훨씬깔끔하고 편하다.