2

これは基本的にエイトクイーンの問題ですが、1Dアレイでブルートフォースで解決します。サイズが8で、要素の範囲が0から7の配列（bという名前）があるとします。

次のように、配列内の各インデックスを8つのforループで初期化します。

int b[8]={0};

int count = 0;


for(b[0] = 0; b[0]<8; b[0]++){ 
for(b[1] = 0; b[1]<8; b[1]++){ 
for(b[2] = 0; b[2]<8; b[2]++){ 
for(b[3] = 0; b[3]<8; b[3]++){ 
for(b[4] = 0; b[4]<8; b[4]++){ 
for(b[5] = 0; b[5]<8; b[5]++){
for(b[6] = 0; b[6]<8; b[6]++){
for(b[7] = 0; b[7]<8; b[7]++){
                if(check(b)) 
                {
                count++;
                print(b, count);
                }
            }}
        }}
    }}
}}

このプログラムが行うことになっているのは、0から7までの数字のすべての組み合わせをチェックし、特定の条件に対してのみtrueを返すことです。92の解決策があるはずですが、これがおなじみのように聞こえるなら、そうあるべきです-それは力ずくの力を使った8クイーンの問題です。ここから、これが条件であると私が理解していることです。

配列に連続した数字の文字列があるかどうかを確認できるようにしたい。そのような：

[0 | 5 | 7 | 1 | 2 | 3 | 6 | 4]

ここで、要素b [3]、b [4]、およびb[5]は連続しています。数字の連続した文字列があるので、私はそれを望んでいません、私はfalseを返したいです（基本的に女王は攻撃しています）

また、次のような逆方向に連続する数字の文字列を持つ配列は必要ありません。

[0 | 5 | 7 | 3 | 2 | 1 | 6 | 4]

そして最後に、インデックスに2つ以上の数値を入れて、それらの間の数値を変更しただけで連続して見えるようにしたくありません。

[0 | 2 | 4 | 6 | 1 | 3 | 5 | 7]

b[0]とb[7]は「連続インデックス」の数値であるため、上記は受け入れられません（少なくとも2つのクイーンが互いに攻撃しているため）。

[6 | 1 | 3 | 0 | 4 | 7 | 5 | 2]

b[1]とb[4]も連続したインデックスにあるため、上記も受け入れられません。

同様に、値が交換されると、配列

[7 | 2 | 4 | 6 | 1 | 3 | 5 | 0]

[6 | 4 | 3 | 0 | 1 | 7 | 5 | 2]

また、受け入れられません。また、同じ番号を2つ以上持つことはできません。

私が抱えている問題は、チェック関数の作成にあります。1つのforループと1つのif-thenステートメントを使用する必要があると言われました。チェック関数は配列全体をそのまま取得できますか？もしそうなら、配列の右端の要素をどのように見て、連続したインデックスがあるかどうかを確認します（クイーンが攻撃しています）？私はこれを試しました：

bool ok(int board[8]){

    for(int c = 7; c >= 0; c--){ //row check
        for (int j=0; j<c; j++){
            if (board[c]==board[j]){
                return false;
            }
        }


        for(int i = 1; i <= c; i++){
            // diagonal check from top left to bottom right
            if  ((board[c]-i >= 0) && (board[c-i] == board[c]-i))
                {return false;}
            if ((board[c]+i <= 7) && (board[c+i] == board[c]+i))
                {return false;}
            // diagonal check from bottom left to top right
            if ((board[c]-i >= 0) && (board[c-i] == board[c]+i))
                {return false;}
            if ((board[c]+i <= 7) && (board[c+i] == board[c]-i))
                {return false;}

        }

    }

    return true;
}

しかし、これは機能しないだけでなく（300以上のソリューションが得られます）、私が言われているほど小さくはありません。

4

1 に答える 1

1

対角線での衝突のチェックには少し問題があると思います.15の対角線が各方向に進んでいます(コーナーの非常に短い1平方の対角線を含む).コードは、board[c]+i <= 7とboard[c]-i >= 0条件。

3 つのブール配列を使用してチェックを簡素化し、高速化する方法を次に示します。8 行、15 の上昇対角線、15 の下降対角線があります。

bool row[8];
bool ascending[15];
bool descending[15];

最初は、これらの行/対角線のいずれにもクイーンはありません。の要素を確認しながら、次の操作boardを行います。

for (int i = 0 ; i != 8 ; i++) {
    // Check and mark the row
    if (row[board[i]]) return false;
    row[board[i]] = true;
    // Check and mark the ascending diagonal
    int ascIdx = board[i]+i;
    if (ascending[ascIdx]) return false;
    ascending[ascIdx] = true;
    int descIdx = 7+board[i]-i;
    if (descending[descIdx]) return false;
    descending[descIdx] = true;
}
return true;
于 2013-03-03T17:51:06.363 に答える