• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

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

 问题描述:

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

样例:

input.txt

4

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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap