首页 > 代码库 > 皇后问题

皇后问题

 

递归回溯代码

 

#include <iostream>using namespace std;int n,m, a[10];bool bz[3][10];void  DFS(int k){   int i;if  (k==n)    {   for ( i=0; i<n; i++)     cout<<a[i]<<" ";        cout<<endl;    }    else        for ( i=0; i<n; i++)           if ( !bz[0][i] && !bz[1][k+i] && !bz[2][k-i+n] )                          {    a[k]=i+1;         bz[0][i]=bz[1][k+i]=bz[2][k-i+n]=1;            DFS(k+1);bz[0][i]=bz[1][k+i]=bz[2][k-i+n]=0;            }    }int main(){ cin>>n;        DFS(0);return 0;}
View Code
#include <iostream>
using namespace std;
 
int n,m, a[10];
bool bz[3][10];
 
void  DFS(int k)
{   int i;
if  (k==n)
    {   for ( i=0; i<n; i++)     cout<<a[i]<<" ";
        cout<<endl;
    }
    else
        for ( i=0; i<n; i++)
           if ( !bz[0][i] && !bz[1][k+i] && !bz[2][k-i+n] )               
           {    a[k]=i+1;
         bz[0][i]=bz[1][k+i]=bz[2][k-i+n]=1;
            DFS(k+1);
bz[0][i]=bz[1][k+i]=bz[2][k-i+n]=0; 
           }    
}
 
int main()
{ cin>>n;
        DFS(0);
return 0;
}
 
 
递归代码1
 
#include <iostream>using namespace std;int n,m, a[10];bool ok( int k,int i){  for (int j = 0; j <k; j++)                    if (  a[j]==i  ||  abs(a[j]-i)==abs(j-k) )                       return false;            return true;}void  DFS(int k){   if  (k==n)    {   for (int i=0; i<n; i++)     cout<<a[i]<<" ";        cout<<endl;    }    else        for (int i=1; i<=n; i++)            if ( ok(k,i) )  { a[k]=i;    DFS(k+1); }}int main(){ cin>>n;        DFS(0);return 0;}
View Code

 

#include <iostream>
using namespace std;
 
int n,m, a[10];
 
bool ok( int k,int i)
{  for (int j = 0; j <k; j++)              
      if (  a[j]==i  ||  abs(a[j]-i)==abs(j-k) )              
         return false;         
   return true;
}
 
void  DFS(int k)
{   if  (k==n)
    {   for (int i=0; i<n; i++)     cout<<a[i]<<" ";
        cout<<endl;
    }
    else
        for (int i=1; i<=n; i++)
            if ( ok(k,i) )  { a[k]=i;    DFS(k+1); }
}
 
int main()
{ cin>>n;
        DFS(0);
return 0;
}
 
 
 
 
 
递归代码2
 

 

#include <iostream>using namespace std;int n,m, a[10];bool ok( int k,int i){   for (int j = 0; j <k; j++)        if (  a[j]==a[k]  ||  abs(a[j]-a[k])==abs(j-k) ) return false;    return true;}void  DFS(int k){   if  (k==n)    {   for (int i=0; i<n; i++)     cout<<a[i]<<" ";        cout<<endl;    }    else        for (int i=1; i<=n; i++)        {    a[k]=i;             if ( ok(k,i) ) DFS(k+1);        }}int main(){    cin>>n;    DFS(0);    return 0;}
View Code
#include <iostream>
using namespace std;
 
int n,m, a[10];
 
bool ok( int k,int i)
{   for (int j = 0; j <k; j++)
        if (  a[j]==a[k]  ||  abs(a[j]-a[k])==abs(j-k) ) return false;
    return true;
}
 
void  DFS(int k)
{   if  (k==n)
    {   for (int i=0; i<n; i++)     cout<<a[i]<<" ";
        cout<<endl;
    }
    else
        for (int i=1; i<=n; i++)
        {    a[k]=i;
             if ( ok(k,i) ) DFS(k+1);
        }
}
 
int main()
{    cin>>n;
    DFS(0);
    return 0;
}




 

递归代码3

#include <iostream>using namespace std;int n,m, a[10];void  DFS(int k){   int i,j,ok;if  (k==n)    {   for ( i=0; i<n; i++)     cout<<a[i]<<" ";        cout<<endl;    }    else        for ( i=1; i<=n; i++)        { ok=1;            a[k]=i;        for ( j = 0; j <k; j++)                 if (  a[j]==a[k] || k-a[k]==j-a[j] || k+a[k]==j+a[j]  )                                  {  ok=0;  break; }                  if ( ok )   DFS(k+1);         }   }int main(){ cin>>n;       DFS(0);return 0;}View Code
View Code

 

 

#include <iostream>
using namespace std;
 
int n,m, a[10];
 
 
void  DFS(int k)
{   int i,j,ok;
if  (k==n)
    {   for ( i=0; i<n; i++)     cout<<a[i]<<" ";
        cout<<endl;
    }
    else
        for ( i=1; i<=n; i++)
        { ok=1;
            a[k]=i;
        for ( j = 0; j <k; j++)              
   if (  a[j]==a[k] || k-a[k]==j-a[j] || k+a[k]==j+a[j]  )              
                    {  ok=0;  break; }         
         if ( ok )   DFS(k+1); 
        }   
}
 
int main()
{ cin>>n;
       DFS(0);
return 0;
}
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <iostream>
using namespace std;
int n,m, a[10];
bool ok( int k,int i)
{  for (int j = 0; j <k; j++)             
      if (  a[j]==i  ||  abs(a[j]-i)==abs(j-k) )             
         return false;        
   return true;
}
void  DFS(int k)
{   if  (k==n)
    {   for (int i=0; i<n; i++)     cout<<a[i]<<" ";
        cout<<endl;
    }
    else
        for (int i=1; i<=n; i++)
            if ( ok(k,i) )  { a[k]=i;    DFS(k+1); }
}
int main()
{ cin>>n;      DFS(0);
 return 0;
}