n-クイーン問題のアルゴリズム（バックトラッキング）

この記事は Google 翻訳を使用して処理されました

問題の説明

n クイーン問題は、n 行 n 列のチェス盤に n 個のクイーンを配置し、クイーン同士が攻撃できないようにすることです。ルールは、2 個のクイーンが同じ行、列、または対角線上にないことです（つまり、、チェスのクイーンの移動範囲）

問題分析

n クイーン問題を解決するために、次のアイデアが提案されています。

i 番目のクイーンは i 番目の列に置かれる

最初のクイーンから始めて、各クイーンについて、対応する行の最初の列から試します（i番目のクイーンはi番目の行に対応します）配置できる場合は位置を決定し、次のクイーンを検討します前の女王と衝突する場合は、次の列を考慮する最後の列を超えた場合は、前のクイーンの位置が再決定されます。

すべての配置ソリューションが見つかるまでこのプロセスを繰り返します。

C コード

#include <stdio.h>
#include <math.h>

#define N 4 // クイーンの数

// k 番目のクイーンの現在の位置が前のクイーンと競合するかどうかを判定する
int isplace(int pos[], int k){
        int i;
        for(i=1; i<k; i++){
            if(pos[i]==pos[k] || fabs(i-k) == fabs(pos[i]-pos[k]))
                return 0;
        }
        return 1;
}

int main(){
    int i,j;
    int count = 1;
    int pos[N+1];

    // 初期化の位置
    for(i=1;i<=N;i++)
        pos[i]=0;
    
    j = 1;
    while(j>=1){
        pos[j]=pos[j]+1;

        // i 番目のクイーンを配置してみて
        while(pos[j]<=N && !isplace(pos,j)){
            pos[j]=pos[j]+1;
            // 配置計画を取得する
        }

        if(pos[j]<=N && j==N){
            printf("方案 %d：", count++);
            for(i=1;i<=N;i++)
                printf("%d", pos[i]);
            printf("\n");
        }

        // 次のクイーンを考えてみよう
        if(pos[j]<=N && j<N){
            j+=1;
        }else{ // 前のクイーンについて考えるために戻る
            pos[j]=0;
            j-=1;
        }
    }
    return 1;
}