問題: N クイーン問題 (C)

N クイーン問題 (C)

問題

整数 n を入力として受け取り、n×n の盤面に n 個のクイーンを互いに取り合わないように置く方法の数を、バックトラッキングで求めてください。1 行ずつクイーンを置き、同じ列や斜めに既にクイーンがあれば別の列を試します。最初に見つかった解の各行のクイーンの列番号と、解の個数を表示します。

入力例

出力例

2 4 6 1 3 5
解の個数: 4

残り時間: 00:00

速度: 0 文字/分

参照コード

コピーはできません。自分でタイピングしてください。

#include <stdio.h>
#include <stdlib.h>

int n, count = 0;
int queen[20];

int canPlace(int row, int col) {
    for (int i = 0; i < row; i++) {
        if (queen[i] == col || abs(queen[i] - col) == row - i) {
            return 0;
        }
    }
    return 1;
}

void solve(int row) {
    if (row == n) {
        count++;
        if (count == 1) {
            for (int i = 0; i < n; i++) {
                printf("%d%c", queen[i] + 1, i == n - 1 ? '\n' : ' ');
            }
        }
        return;
    }
    for (int col = 0; col < n; col++) {
        if (canPlace(row, col)) {
            queen[row] = col;
            solve(row + 1);
        }
    }
}

int main(int argc, const char *argv[]) {
    scanf("%d", &n);
    solve(0);
    printf("解の個数: %d\n", count);
    return 0;
}

N クイーン問題 (C)

問題

入力例

出力例

参照コード

入力エリア