【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d324
【解題想法】N-Queens【筆記】
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a, b, sol_cnt;
int row[8];
void printRow() {
printf("%2d %d", ++sol_cnt, row[0]+1);
for (int i=1; i<8; i++) {
printf(" %d", row[i]+1);
}
printf("\n");
}
bool place(int r, int c) {
for (int pre=0; pre<c; pre++) {
if (row[pre]==r || (abs(row[pre] - r) == abs(pre - c))) {
return false;
}
}
return true;
}
void queen(int c) {
if (c == 8) {
if (row[b] == a) {
printRow();
}
} else {
for (int r=0; r<8; r++) {
if (place(r, c)) {
row[c] = r;
queen(c+1);
}
}
}
}
int main() {
int TC;
cin >> TC;
while (TC--) {
cin >> a >> b;
a--; // row# zero-based
b--; // col# zero-based
memset(row, -1, sizeof(row));
sol_cnt = 0;
printf("SOLN COLUMN\n");
printf(" # 1 2 3 4 5 6 7 8\n\n");
queen(0);
if (TC) printf("\n");
}
return 0;
}
Python code (credit: Amy Chou)
def Conflict(row, col):
for i in range(row):
if abs(Ans[i] - col) in [0, row - i]:
return True
return False
def Queen(d):
global res
if d == n:
line = [-1] * n
for i in range(n):
line[Ans[i]] = str(i+1)
res.append(" ".join(line))
return
for i in range(n):
if Used[i] or Conflict(d, i):
continue
Used[i] = 1
Ans[d] = i
Queen(d+1)
Used[i] = 0
n = 8
testcase = int(input())
for iter1 in range(testcase):
r, c = map(int, input().strip().split())
r, c = r-1, c-1
Ans = [-1] * n
Used = [0] * n
res = []
Queen(0)
res.sort()
print("SOLN COLUMN")
print(" # 1 2 3 4 5 6 7 8")
print()
i = 0
for ans in res:
temp = ans.split()
if temp[c] == str(r+1):
i += 1
print(f"{i:2d} {ans}")
if iter1 < testcase-1:
print()