首页 > 代码库 > 皇后问题
皇后问题
递归回溯代码
#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;}
#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;}
#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;}
#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
#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;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。