nQueen.rar_NQueen

#include<iostream> #include<math.h> using namespace std; void nQueen(int n,int x[]); void backtrack(int t,int n,int x[]); bool place(int k,int x[]); int sum=0; int main() { int n;//皇后个数 cout<<"请输入n:"<<endl; cin>>n; int *x=new int[n+1]; //当前解 nQueen(n,x); //for(int i=1;i<=n;i++) //cout<<x[i]; return 0; } void nQueen(int n,int *x) { //int sum=0; for(int i=0;i<=n;i++) { x[i]=0; } backtrack(1,n,x); //return sum; } void backtrack(int t,int n,int *x) { if(t>n) { sum++; cout<<"解法"<<sum<<endl; for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) { if(x[j]==k) cout<<"Q "; else cout<<"- "; } cout<<endl; } cout<<endl<<endl; } for(int i=1;i<=n;i++) { x[t]=i; if(place(t,x)) backtrack(t+1,n,x); } } bool place(int k,int x[]) { for(int j=1;j<k;j++) if(abs(k-j)==abs(x[j]-x[k]) || x[j]==x[k]) return false; return true; } /* #include <stdio.h> #include <stdlib.h> #define N 8 int column[N+1]; // 同栏是否有皇后，1表示有 int rup[2*N+1]; // 右上至左下是否有皇后 int lup[2*N+1]; // 左上至右下是否有皇后 int queen[N+1] = {0}; int num; // 解答编号 void backtrack(int); // 递回求解 int main(void) { int i; num = 0; for(i = 1; i <= N; i++) column[i] = 1; for(i = 1; i <= 2*N; i++) rup[i] = lup[i] = 1; backtrack(1); return 0; } void showAnswer() { int x, y; printf("\n解答 %d\n", ++num); for(y = 1; y <= N; y++) { for(x = 1; x <= N; x++) { if(queen[y] == x) { printf(" Q"); } else { printf(" ."); } } printf("\n"); } } void backtrack(int i) { int j; if(i > N) { showAnswer(); } else { for(j = 1; j <= N; j++) { if(column[j] == 1 && rup[i+j] == 1 && lup[i-j+N] == 1) { queen[i] = j; // 设定为占用 column[j] = rup[i+j] = lup[i-j+N] = 0; backtrack(i+1); column[j] = rup[i+j] = lup[i-j+N] = 1; } } } } */