八皇后问题-回溯法

1.利用二维数组保存棋盘上的状态

 1 #include<cstdio>
 2 
 3 int arry[8][8] = { 0 };//棋盘，放皇后
 4 int result = 0;//存放结果数量
 5 
 6 bool check(int row, int col);
 7 void print();
 8 
 9 void FindQueen(int row)
10 {
11     if (row > 7)
12     {
13         //有解
14         result++;
15         print();
16         return;
17     }
18 
19     for (int col = 0; col < 8; col++)
20     {
21         //回溯递归
22         if (check(row, col))
23         {
24             arry[row][col] = 1;
25             FindQueen(row + 1);
26             arry[row][col] = 0;//清零，以免回溯的时候出现脏数据
27         }
28     }
29 }
30 
31 bool check(int row, int col)
32 {
33     //检查列冲突
34     for (int i = 0; i < 8; i++)
35         if (arry[i][col] == 1)
36             return false;
37 
38     //检查左对角线
39     for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
40         if (arry[i][j] == 1)
41             return false;
42     for (int i = row + 1, j = col + 1; i < 8 && j < 8; i++, j++)
43         if (arry[i][j] == 1)
44             return false;
45 
46     //检查右对角线
47     for (int i = row + 1, j = col - 1; i < 8 && j >= 0; i++, j--)
48         if (arry[i][j] == 1)
49             return false;
50     for (int i = row - 1, j = col + 1; i >= 0 && j < 8; i--, j++)
51         if (arry[i][j] == 1)
52             return false;
53 
54     return true;
55 }
56 
57 void print()
58 {
59     printf("方案%d:
", result);
60     for (int i = 0; i < 8; i++)
61     {
62         for (int j = 0; j < 8; j++)
63             if (arry[i][j] == 1)
64                 printf("O ");
65             else
66                 printf("+ ");
67         printf("
");
68     }    
69 }
70 
71 int main()
72 {
73     FindQueen(0);
74     return 0;
75 }

2.使用一维数组存放皇后的位置，下标表示行，值表示列

 1 #include<iostream>
 2 using namespace std;
 3 
 4 static int chessboardQueen[8] = { 0 };//存储每行皇后的位置
 5 static int nCount = 0;//存储方法数
 6 
 7 void print()
 8 {
 9     cout << "方案" << nCount << ":" << endl;
10     for (int i = 0; i < 8; i++)
11     {
12         int inner;
13         for (inner = 0; inner < chessboardQueen[i]; inner++)
14             cout << "o";
15         cout << "*";
16         for (inner = chessboardQueen[i] + 1; inner < 8; inner++)
17             cout << "o";
18         cout << endl;
19     }
20     cout << "================================" << endl;
21 }
22 
23 int isSafePosition(int loop, int value)
24 {
25     int index;
26     int data;
27     for (index = 0; index < loop; ++index)
28     {
29         data = chessboardQueen[index];
30         //同一列有两个皇后
31         if (value == data)
32             return 0;
33         //主对角线有两个皇后
34         if ((index + data) == (loop + value))
35             return 0;
36         //副对角线有两个皇后
37         if ((index - data) == (loop - value))
38             return 0;
39     }
40     return 1;
41 }
42 
43 void eightQueen(int index)
44 {
45     int loop;
46     for (loop = 0; loop < 8; ++loop)
47     {
48         if (isSafePosition(index, loop))
49         {
50             chessboardQueen[index] = loop;
51             if (7 == index)//如果index等于7则说明已经成功从第一行遍历到第八行了
52             {
53                 nCount++;
54                 print();
55                 chessboardQueen[index] = 0;
56                 return;
57             }
58             eightQueen(index + 1);//递归调用
59             chessboardQueen[index] = 0;//当不再递归时，说明index+1位置不满足条件
60         }
61     }
62 }
63 
64 int main()
65 {
66     eightQueen(0);
67     cout << "total=" << nCount << endl;
68     return 0;
69 }