17.11.16 八皇后问题

描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！即任何两个皇后都不会在同一行、同一列、或同一斜线上。这就是著名的八皇后问题。
关于输入
本题没有输入
关于输出
输出八皇后问题所有的解，解用一个 88 的字符方正表示，如果某个位置没有皇后，则对应的字符为“.”，如果有皇后，则对应的字符为“”。为了美观起见，同一行的两个字符之间有一个空格，解的前一行是一个数字，表示这个解的序号。（详见例子输出）解要按照皇后在第 1 列、第 2 列……第 8 列出现的行数从小到大依次排序。

 1 #include <iostream>
 2 using namespace std;
 3 int queen[9],qcount=0;
 4 void print()
 5 {
 6     for(int i=1;i<9;i++)
 7     {
 8         if (queen[i] == 1)
 9             cout << "*";
10         else
11             cout << ".";
12         for (int j = 2; j <= 8; j++)
13         {
14             if (j == queen[i])
15                 cout << " *";
16             else
17                 cout << " .";
18         }
19         cout << endl;
20     }
21 }
22 int check(int row)
23 {
24     int num[9] = { 0 };
25     for (int i = 1;i<=row;i++)
26     {
27         num[queen[i]]++;
28         if (num[queen[i]] > 1)
29             return 0;
30         if (i != row)
31         {
32             for (int j = i + 1; j < row+1; j++)
33                 if ((queen[i] - queen[j] == j - i) || (queen[j] - queen[i] == j - i))
34                     return 0;
35         }
36     }
37     return 1;
38 }
39 void eighqueen(int row)
40 {
41     for (int i = 1; i <= 8; i++)
42     {
43         queen[row] = i;
44         if (check(row) && row != 8)
45             eighqueen(row + 1);
46         else if(check(row)&&row==8)
47         {
48             qcount++;
49             cout << qcount << endl;
50             print();
51             
52         }
53     }
54 }
55 void main()
56 {
57     eighqueen(1);
58 }

View Code

看错题了……要求是列出现行数从小到大排序

看成了行……

先姑且po一下……

本题解决代码：

 1 #include <iostream>
 2 using namespace std;
 3 int queen[9],qcount=0;  //queen数组代表某列queen所在的行数
 4 void print()   //定义输出函数
 5 {
 6     for (int j = 1; j < 9; j++)        //按行输出，在queen数组中找出相应行数
 7         for (int i = 1; i < 9; i++)
 8             if (queen[i] == j)
 9             {
10                 for (int p = 1; p < i; p++)
11                     cout << ". ";
12                 cout << "*";
13                 for (int p =i + 1; p <= 8; p++)
14                     cout << " .";
15                 cout << endl;
16             }
17     }
18 int check(int col)      //定义一个检查某个方案的正确性的函数
19 {
20     int num[9] = { 0 };
21     for (int i = 1;i<=col;i++)
22     {
23         num[queen[i]]++;
24         if (num[queen[i]] > 1)
25             return 0;
26         if (i != col)
27         {
28             for (int j = i + 1; j < col+1; j++)
29                 if ((queen[i] - queen[j] == j - i) || (queen[j] - queen[i] == j - i))
30                     return 0;
31         }
32     }
33     return 1;
34 }
35 void eighqueen(int col)          //在这个函数中逐个尝试不同方案，并输出方案
36 {
37     for (int i = 1; i <= 8; i++)
38     {
39         queen[col] = i;
40         if (check(col) &&col != 8)     //当列数不为第八列时进行递归
41             eighqueen(col + 1);
42         else if(check(col)&&col==8)
43         {
44             qcount++;
45             cout << qcount << endl;
46             print();
47             
48         }
49     }
50 }
51 void main()
52 {
53     eighqueen(1);
54 }

View Code

学校的平台不让过void主函数……也是没谁了

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。