0

私は、2人の女王がお互いを攻撃できないようにNXNチェス盤にN人の女王を配置する必要があるN女王の問題を解決していました。

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

int size=8;
char arr[8][8];
int i,j;

void initializeBoard()
{
  for(i=0;i<size;i++)
  {
    for(j=0;j<size;j++)
    {
        arr[i][j]='.';
    }
  }
}

void printArray()
{

  for(i=0;i<size;i++)
  {

    for(j=0;j<size;j++)
    {
        printf("%c\t",arr[i][j]);
    }

    printf("\n");
  }
  printf("\n\n");
}

void placeQueen(int i,int j)
{
  arr[i][j]='Q';
}

int isAvailable(int i,int j)
{
   int m,n,flag;

   for(m=0;m<i;m++)
   {
      for(n=0;n<size;n++)
      {
        int k=abs(i-m);
        int l=abs(j-n);

        if(arr[m][j]!='Q' && arr[k][l]!='Q')
        {
            flag=1;
        }

        else
        {
            flag=0;
            break;
        }
    }
}
return flag;

}


int main(void)
{
    initializeBoard();

    for(i=0;i<size;i++)
    {
        for(j=0;j<size;j++)
        {
            if(isAvailable(i,j)==1)
            {
                // means that particular position is available
                // and so we place the queen there

                placeQueen(i,j);
                break;
            }
        }
    }

    printArray();
    return 0;
}

問題はisAvailable（）メソッドにあると思います。しかし、私はバグを見つけることができません。私がそれを特定するのを手伝ってください。

私が取っているアプローチにはバックトラックが含まれていますか？そうでない場合は、いくつかの説明を付けて同じものを提供してください

4

4 に答える 4

1

以前にこの問題を実行したことがあるので、すべての配置で問題の有効な解決策が得られるわけではありません。

あなたの解決策は、常に利用可能な位置（0,0）にクイーンを常に配置することを含みます。

すべてを調べても何も見つからない場合は常にバックトラックを行う必要があります。または、すべてのクイーンをランダムに配置してソリューションをチェックするソリューションに依存する必要があります（この方法は実際には思ったよりもはるかに高速です） 、しかし同時に、ランダムであるため、平均的なケースでは非常に非効率的です）

潜在的な疑似ソリューション：

while(!AllQueensPlaced){
    for(going through the array ){
        if(isAvailable())
        {
            placeQueen();
            lastQueenPlaced = some logical location of last queen;
        }
    }
    if(!AllQueensPlaced)
    {
         backtrack(lastQueenPlaced);
    }
}

backtrackメソッドは、lastQueenPlacedをダーティとしてマークし、配列を再度トラバースして新しい場所を探してから、whileループを再度実行する必要があります。lastQueenPlacedでもある場合は、backtrack（）でlastQueenPlacedを変更することを忘れないでください。

于 2012-07-13T18:57:04.157 に答える
0

あなたのアプローチは後戻りしません。すべてではなく、いくつかの可能性を繰り返します。この問題は再帰的に解決するのが最善なので、あなたがしているように私はそれをしません。女王が他の人に攻撃されるためのルールを定義する必要があります。、およびrecursionを使用してこれを実行しifs、ルールを再度適用して反復します。ほとんどのバックトラッキングアルゴリズムは再帰的に記述されています。私はあなたに答えを与えるので、あなたは私のものに基づいてあなたを置くことができます。

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

int count = 0;
void solve(int n, int col, int *hist)
{
    int i, j;
    if (col == n) {
        printf("\nNo. %d\n-----\n", ++count);
        for (i = 0; i < n; i++, putchar('\n'))
            for (j = 0; j < n; j++)
                putchar(j == hist[i] ? 'Q' : ((i + j) & 1) ? ' ' : '.');

        return;
    }

#   define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)
    for (int i = 0, j = 0; i < n; i++) {
        for (j = 0; j < col && !attack(i, j); j++);
        if (j < col) continue;

        hist[col] = i;
        solve(n, col + 1, hist);
    }
}

int main(int n, char **argv)
{
    if (n <= 1 || (n = atoi(argv[1])) <= 0) n = 8;
    int hist[n];
    solve(n, 0, hist);
}

バックトラックが機能する方法は次のとおりです。

  1. 条件が満たされているかどうかを確認するための制約（ルール）を作成します。
  2. 問題を探索木と考えてください。このツリーの検索に費やされる時間はn、ボードのサイズに基づいています。検索する最良の方法は再帰的であるため、解決するための賢い方法は再帰を使用することです。
  3. そのコードでは、forループの最初のセットはボードを出力し、見つかったかどうかをチェックしますQ。
  4. # define attack(i, j) (hist[j] == i || abs(hist[j] - i) == col - j)2人の女王がお互いを攻撃していないと主張する私のルールです。
  5. ループの2番目のセットはfor、制約ルール内で別のクイーンを挿入できる条件を見つけます。
  6. 次に、find関数を再度呼び出します。これがバックトラックの実行方法です。
  7. 私の基本的なケースは、2つのクイーンをボードに配置できるというものです。次に、8まで別のクイーンを追加できるかどうかを再帰的にチェックします。したがって、2 + 1 =（1 + 1）+ 1 = 1（1 + 1）です。ルールを再度適用すると、3 + 1 =（2）+ 1 + 1 =（2）+（1 + 1）になり、4 =（3）+ 1 + 1 =（3）+（1 + 1）になります。 。
  8. 再帰はあなたのためにそれを行います。ルールを何度も適用してみましょう。したがってf(n+1) = f(n) + 1、その場合f(2) = 2は、私の基本ケースです。
  9. バックトラックの基本は、これらのブランチの1つが機能しない場合、ツリーがすべて検索されるまで、1つ上のレベルに移動して、別のブランチを検索することなどができます。繰り返しますが、再帰が進むべき道です。
于 2012-07-13T18:57:21.560 に答える
0

一次元配列を使用して、各行にクイーンを配置できる列を追跡します。

女王が脅かされる可能性のある条件は、1）ColumnForRow [i] == ColumnForRow [j]-同じ列になります2）（ColumnForRow [i]-ColumnForRow [j]）==（i- j）または（ColumnForRow [j] --ColumnForRow [i]）==（i --j）-これらは同じ対角線上にあります。

パブリッククラスNQueenSolver{

static int BOARD_SIZE = 15;
static int count = 0;
static int columnForRow[] = new int[BOARD_SIZE];

public static void main(String[] args) {
    PlaceQueen(0);
    System.out.println(count);
}

static boolean check(int row) {
    for (int i = 0; i < row; i++) {
        int diff = Math.abs(columnForRow[i] - columnForRow[row]);
        if (diff == 0 || diff == row - i)
            return false;
    }
    return true;
}

static void PlaceQueen(int row) {
    if (row == BOARD_SIZE) {
        printBoard();
        ++count;
        return;
    }
    for (int i = 0; i < BOARD_SIZE; i++) {
        columnForRow[row] = i;
        if (check(row)) {
            PlaceQueen(row + 1);
        }
    }
}

private static void printBoard() {
    //System.out.println(Arrays.toString(columnForRow));
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (columnForRow[i] == j)
                System.out.print("Q ");
            else
                System.out.print("* ");
        }
        System.out.println();
    }
    System.out.println();
}

}

于 2016-02-17T13:38:40.467 に答える
0

コードには再帰的な方法がありません。これは、バックトラッキングアルゴリズムを設計するときに頭に浮かぶべき最初の考えです。したがって、ここではバックトラック戦略を実装していません。

関数isAvailable（）は多くの点で不完全です。

セル（行、列）がすでに配置されているクイーンから攻撃を受けているかどうかを確認するには、次の戦略を使用できます。

注意点：

  1. クイーンを行ごとに配置する

  2. クイーンをi番目の行に配置するには、0から（i-1）番目の行に配置されたクイーンとの競合をチェックする必要があります。

  3. 女王は水平、垂直、斜めに攻撃します。

コード（参照：Tushar Royの講義/コード）

boolean isSafe = true;
for(int queen = 0; queen<row; queen++) // Checking with already placed queens
{
    // attack condition
    if(position[queen].column == column || position[queen].row + 
    position[queen].column == row + column || position[queen].row - 
    position[queen].column == row-column)
    {
        isSafe = false;
        break;
    }
}

お役に立てれば。

于 2017-09-26T20:42:13.473 に答える