128. N-Queen
1. Python
def check(n):
for i in range(n):
if row[n] == row[i] or abs(row[n]-row[i]) == n-i:
return 0
return 1
def dfs(n):
global res
if n == N:
res += 1
else:
for i in range(N):
row[n] = i
if check(n):
dfs(n+1)
N = int(input())
row = [0]*N
res = 0
dfs(0)
print(res)
출처: https://jinho-study.tistory.com/979
n = int(input())
def dfs(arr):
global ans
length = len(arr)
if length==n:
ans+=1
return
candidate = list(range(n)) # 후보가 될 수 있는 자리를 0부터 n-1까지 만들고 제외하는 방법을 사용
for i in range(length):
if arr[i] in candidate: # 같은 가로줄에 있으면 후보에서 제외
candidate.remove(arr[i])
distance = length - i
if arr[i] + distance in candidate: # 같은 '/' 대각선에 있으면 후보에서 제외
candidate.remove(arr[i] + distance)
if arr[i] - distance in candidate: # 같은 '\' 대각선에 있으면 후보에서 제외
candidate.remove(arr[i] - distance)
if candidate:
for i in candidate:
arr.append(i)
dfs(arr)
arr.pop()
else:
return
ans = 0
for i in range(n):
dfs([i])
print(ans)
2. C++
#include <cstdio>
int n, ans;
int chess[14][14]; // 초기화가 이미 0으로 되어있음
// line : 0 ~ n - 1
void recur(int line) {
// 종료조건
if (line == n) {
ans++;
return;
}
// line어딘가에다가 queen을 놓아본다
for (int i = 0 ; i < n ; i++) {
if (chess[line][i] != -1) continue;
chess[line][i] = line;
// line에 놓았으니까 상/하/좌/우/대각선에는 queen을 놓지 못하게 처리한다
// 좌/우
for (int x = 0 ; x < n ; x++) {
if (chess[line][x] == -1) {
chess[line][x] = line;
}
}
// 하
for (int y = line ; y < n ; y++) {
if (chess[y][i] == -1) {
chess[y][i] = line;
}
}
// 대각선
for (int y = line, x = i ; y < n && 0 <= x ; y++, x--) {
if (chess[y][x] == -1) {
chess[y][x] = line;
}
}
for (int y = line, x = i ; y < n && x < n ; y++, x++) {
if (chess[y][x] == -1) {
chess[y][x] = line;
}
}
// 다음 줄 queen을 놓아본다
recur(line + 1);
// 지금 queen이 처리한 흔적을 지운다.
//자기가 그린 것만 지우기
for (int x = 0 ; x < n ; x++) {
if (chess[line][x] == line) {
chess[line][x] = -1;
}
}
// 하
for (int y = line ; y < n ; y++) {
if (chess[y][i] == line) {
chess[y][i] = -1;
}
}
// 대각선
for (int y = line, x = i ; y < n && 0 <= x ; y++, x--) {
if (chess[y][x] == line) {
chess[y][x] = -1;
}
}
for (int y = line, x = i ; y < n && x < n ; y++, x++) {
if (chess[y][x] == line) {
chess[y][x] = -1;
}
}
/*
//그냥 다 지우기(초기화)
//queen이 처리한 흔적을 지운다.
for(int y = line; y < n; y++){
for (int x =0; x < n; x++){
if (chess[y][x] == line){
chess[y][x] = -1;
}
}
}
*/
}
}
int main() {
// array fill
for (int i = 0 ; i < 14 ; i++) {
for (int j = 0 ; j < 14 ; j++) {
chess[i][j] = -1;
}
}
scanf("%d", &n);
// todo
recur(0);
printf("%d", ans);
}
3. Java
Author And Source
이 문제에 관하여(128. N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/128.-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)