〖編程·C++〗回溯算法：排列树-N皇后问题

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

问题描述：

输入n，表示n*n的棋盘上面有n个皇后，n个皇后不能再同一行、同一列、同一条对角线上，例如下图，使用回溯法输出所有可能的皇后排列情况和可排列的总数。

样例：

input.txt

output.txt

输出美化的问题解决：当n=4时候

【由于网页与txt中空格所占的宽度不一致所以使用文本文档截图】

1）第一行
1个"┌" 　　　　 1
3个"─┬" 　　　　n-1
1个"─┐" 　　　　1
fout<<endl ;

2.1）数字行皇后在x[i]处

无皇后(右边两个空格)"│ " 　　　　　　　　　　　　　　 1~x[i]-1（x[i]>1）　　x[i]+1~n（x[i]<n）
有皇后(右边没有空格)fout<<"│"<<"Q"<<(i%10); 　　　　x[i]处
fout<<endl;

2.2）非最后一个皇后下一行
fout<<"├─" 1个
fout<<"┼─" n-1个
fout<<"┤" 1个

3）最后一行
1个"└" 　　　　 1
3个"─┴" 　　　　n-1
1个"─┘" 　　　　1
fout<<endl;　　
fout<<endl;　　

改进后的输出代码如下：

改进后的输出代码

 1 int output(int *m)
 2 {/*
 3     int i;
 4     for(i=1;i<=n;i++)
 5         fout<<m[i]<<' ';
 6 
 7 
 8     fout<<endl<<endl;
 9 
10     return 1;
11     */
12 
13     int i,j;
14     //输出第一行
15     fout<<"┌";
16     for(j=1;j<n;j++)
17         fout<<"─┬";
18     fout<<"─┐"<<endl;
19 
20 
21     //输出除了最后一个皇后的行和皇后下一行
22     for(i=1;i<n;i++)
23     {
24         //输出除了最后一个皇后的行
25         if(x[i]>1)
26             for(j=1;j<x[i];j++)
27                 fout<<"│  ";
28         //else fout<<"│";
29         fout<<"│"<<"Q"<<(i%10);
30 
31         if(x[i]<n)
32             for(j=x[i];j<n;j++)
33                 fout<<"│  ";
34         fout<<"│"<<endl;
35 
36         //输出皇后下一行
37         fout<<"├─"    ;
38         for(j=1;j<n;j++)
39             fout<<"┼─";
40         fout<<"┤"<<endl;
41         
42     }
43     //输出最后一个皇后的行
44     if(x[n]>1)
45         for(j=1;j<x[n];j++)
46             fout<<"│  ";
47     //else fout<<"│";
48     fout<<"│"<<"Q"<<(n%10);
49 
50     if(x[n]<n)
51         for(j=x[n];j<n;j++)
52             fout<<"│  ";
53     fout<<"│"<<endl;
54 
55 
56 
57 
58     //输出最后一行
59     fout<<"└"    ;
60     for(j=1;j<n;j++)
61         fout<<"─┴";
62     fout<<"─┘"<<endl;
63 
64 
65     return 1;
66 }

程序源代码总体如下：

程序源代码

  1 #include <fstream>
  2 #include <math.h>
  3 using namespace std;
  4 
  5 ifstream fin("f:\\nhou\\input.txt");
  6 ofstream fout("f:\\nhou\\output.txt");
  7 
  8 int *x;
  9 int sum;
 10 int n;
 11 
 12 
 13 bool place (int k)
 14 {
 15     int i;
 16     for(i=1;i<k;i++)
 17         if(abs(x[k]-x[i])==abs(k-i))
 18             return false;
 19     return true;
 20 }
 21 
 22 int output(int *m)
 23 {/*
 24     int i;
 25     for(i=1;i<=n;i++)
 26         fout<<m[i]<<' ';
 27 
 28 
 29     fout<<endl<<endl;
 30 
 31     return 1;
 32     */
 33 
 34     int i,j;
 35     //输出第一行
 36     fout<<"┌";
 37     for(j=1;j<n;j++)
 38         fout<<"─┬";
 39     fout<<"─┐"<<endl;
 40 
 41 
 42     //输出除了最后一个皇后的行和皇后下一行
 43     for(i=1;i<n;i++)
 44     {
 45         //输出除了最后一个皇后的行
 46         if(x[i]>1)
 47             for(j=1;j<x[i];j++)
 48                 fout<<"│  ";
 49         //else fout<<"│";
 50         fout<<"│"<<"Q"<<(i%10);
 51 
 52         if(x[i]<n)
 53             for(j=x[i];j<n;j++)
 54                 fout<<"│  ";
 55         fout<<"│"<<endl;
 56 
 57         //输出皇后下一行
 58         fout<<"├─"    ;
 59         for(j=1;j<n;j++)
 60             fout<<"┼─";
 61         fout<<"┤"<<endl;
 62         
 63     }
 64     //输出最后一个皇后的行
 65     if(x[n]>1)
 66         for(j=1;j<x[n];j++)
 67             fout<<"│  ";
 68     //else fout<<"│";
 69     fout<<"│"<<"Q"<<(n%10);
 70 
 71     if(x[n]<n)
 72         for(j=x[n];j<n;j++)
 73             fout<<"│  ";
 74     fout<<"│"<<endl;
 75 
 76 
 77 
 78 
 79     //输出最后一行
 80     fout<<"└"    ;
 81     for(j=1;j<n;j++)
 82         fout<<"─┴";
 83     fout<<"─┘"<<endl;
 84 
 85 
 86     return 1;
 87 }
 88 
 89 
 90 int backtrack(int t)
 91 {
 92     int i;
 93 
 94 
 95     if(t>n){sum++;output(x);}
 96     else
 97     {
 98         for(i=t;i<=n;i++)
 99         {
100             swap(x[t],x[i]);
101             if(place(t)) backtrack(t+1);
102             swap(x[t],x[i]);
103         }
104             
105     }
106 
107     
108     return 1;
109 }
110 
111 int main()
112 {
113     fin>>n;
114     int i;
115     sum=0;
116     x = new int[n+1];
117 
118 
119     for(i=1;i<=n;i++)
120         x[i]=i;
121     backtrack(1);
122 
123     fout<<sum;
124 
125     delete x;
126 
127     return 1;
128 }