-1

コードと出力はバックトラック前は正常に機能していますが、バックトラックを続行できません。取り外した後はどうすればよいですか？これは、最初の4つのクイーンの出力をバックトラックする前の手段としてのみ提供しています。

    #include <iostream>
    #include <conio.h>
    using namespace std;
    int recu(int i,int k);
    void place(int i,int k);
    void unplace(int i,int k);
    int q[8][8];
    int row[8];
    int column[8];
    int c[15];
    int d[15];
    int totalqueens=0;
    int s;

    int main()
    {
        for(int i=0;i<8;i++) //Flags for rows,columns and diagonals
        {
        row[i]=0;
        column[i]=0;
        c[i]=0;d[i]=0;
        }
        for(int i=8;i<15;i++)
        {
        c[i]=0;d[i]=0;
        }
        int i=0;
        int k=0;
        recu(i,k);


      for(int i=0;i<8;i++)
      {
          for(int k=0;k<8;k++)
          {
                if(q[i][k]==1)
                {
                   cout<<"(";
                   cout<<i;
                   cout<<",";
                   cout<<k;
                   cout<<")";
                }
           }
     }

    getch();
    return 0;
}

int recu(int i,int k)
{ 
     if(totalqueens==8)
     {  goto print; }
     if(k<8)
      {
          if(column[i]==0 && row[k]==0 && c[i+k]==0 && d[i-k+7]==0)
           {
             place(i,k);

             s=k;
             k=0;
             recu(i+1,k);
           }
           else
           { 
             recu(i,k+1);
             unplace(i-1,s);
            //**I am not able to proceed further**
           }

      }

print:
    ;
}

void place(int i,int k)
{     
    totalqueens++;
    q[i][k]=1;
    row[k]=1;
    column[i]=1;
    c[i+k]=1;
    d[i-k+7]=1;
}

void unplace(int i,int k)
{
    q[i][k]=0;
    row[i]=0;
    column[k]=0;
    c[i+k]=0;
    d[i-k+7]=0;
    //cout<<"before call";
    recu(i,k+1);
    //cout<<"working";
}
4

2 に答える 2

0

すべてのクイーンが配置されておらず、別のクイーンを配置できない場合は、バックトラックします。次のようにバックトラックします。

  1. 最後に配置されたクイーンを後の場所に配置できるかどうかを確認します。その場合は、そこに配置してバックトラックを停止します。（配置を再開します。）

  2. 最後に配置されたクイーンを削除します。

  3. クイーンが残っていない場合は、停止します。すべての解決策が見つかりました。

  4. 手順1に進みます。

于 2012-12-28T21:45:04.427 に答える
0

あなたのコードはただ一つの解決策を与えます。出力部分を正しい場所に配置しないでください。

このようにしてみてください：

void print()
{
      for(int i=0;i<8;i++)
      {
          for(int k=0;k<8;k++)
          {
                if(q[i][k]==1)
                {
                   cout<<"(";
                   cout<<i;
                   cout<<",";
                   cout<<k;
                   cout<<")";
                }
           }
     }
}

それを1つの方法にします。次に、recuメソッドで、次のように変更します。

if(totalqueens==8)
{
    print();
    return;
}

goto文は使用しないでください。それは非常に醜く、未知の問題を引き起こす可能性があります。

于 2012-12-29T01:42:27.897 に答える