【題解】ZeroJudge d324: 00750 – 8 Queens Chess Problem

【題目敘述】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()
分享本文 Share with friends