N皇后问题

【八皇后问题】

在棋盘上放置8个皇后，使得她们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，要求找出所有解。

【回溯】：当把问题分成若干步骤并递归求解时，如果当前步骤没有合法选择，则函数将返回上一级递归调用，这种现象称为回溯。递归枚举算法通常被称为回溯法。

  1 #include <stdio.h>
  2 
  3 #define QUEEN_N     (8)
  4 
  5 int queen[QUEEN_N][QUEEN_N] = {
  6     {0, 0, 0, 0, 0, 0, 0, 0},
  7     {0, 0, 0, 0, 0, 0, 0, 0},
  8     {0, 0, 0, 0, 0, 0, 0, 0},
  9     {0, 0, 0, 0, 0, 0, 0, 0},
 10     {0, 0, 0, 0, 0, 0, 0, 0},
 11     {0, 0, 0, 0, 0, 0, 0, 0},
 12     {0, 0, 0, 0, 0, 0, 0, 0},
 13     {0, 0, 0, 0, 0, 0, 0, 0},
 14 };
 15 
 16 int queen_check(int x, int y)
 17 {
 18     int i;
 19 
 20     for(i = 0; i < QUEEN_N; i++)
 21     {
 22         if(queen[i][y] == 1 && i != x) // 检测列
 23             return 0;
 24         if(queen[x][i] == 1 && i != y) // 检测行
 25             return 0;
 26     }
 27 
 28     // 检测对角线,x正向方向
 29     for(i = x+1; i < QUEEN_N; i++)
 30     {
 31         if(y + i - x < QUEEN_N)
 32             if(queen[i][y+i-x] == 1)
 33                 return 0;
 34         if(y - (i - x) >= 0)
 35             if(queen[i][y-i+x] == 1)
 36                 return 0;
 37     }
 38     // 检测对角线,x反向方向
 39     for(i = x-1; i >=0; i--)
 40     {
 41         if(y + (x-i) < QUEEN_N)
 42             if(queen[i][y+x-i] == 1)
 43                 return 0;
 44         if(y - (x-i) >= 0)
 45             if(queen[i][y-x+i] == 1)
 46                 return 0;
 47     }
 48     return 1;
 49 }
 50 
 51 void queen_print(int queen[QUEEN_N][QUEEN_N]) // 输出棋盘布局
 52 {
 53     int i, j;
 54 
 55     for(i = 0; i < QUEEN_N; i++)
 56     {
 57         for(j = 0; j < QUEEN_N; j++)
 58         {
 59             if(queen[i][j] == 1)
 60             {
 61                 printf("O ");
 62             }
 63             else
 64             {
 65                 printf("x ");
 66             }
 67         }
 68         printf("
");
 69     }
 70 }
 71 
 72 // 输出所有棋盘
 73 void queen_fill(int n)
 74 {
 75     int i;
 76     static int iCount = 0;
 77     if(n >= QUEEN_N) // 递归边界。只要走到了这里，所有皇后必然不冲突。
 78     {
 79         printf("queen_print <%d>
", iCount++);
 80         queen_print(queen);
 81     }
 82     else
 83     {
 84         for(i = 0; i < QUEEN_N; i++) // 尝试把第n行的皇后放在第i列
 85         {
 86             queen[n][i] = 1;
 87             if(queen_check(n, i) == 1)
 88             {
 89                 queen_fill(n+1); // 如果合法，则继续递归，放置下一行
 90             }
 91             queen[n][i] = 0;
 92         }
 93     }
 94 }
 95 // 输出第1个棋盘
 96 int queen_fill_1(int n)
 97 {
 98     int i;
 99     if(n >= QUEEN_N)
100     {
101         queen_print(queen);
102         return 1;
103     }
104     else
105     {
106         for(i = 0; i < QUEEN_N; i++)
107         {
108             queen[n][i] = 1;
109             if(queen_check(n, i) == 1)
110             {
111                 if(queen_fill_1(n+1) == 1)
112                     return 1;
113             }
114             queen[n][i] = 0;
115         }
116     }
117     return 0;
118 }
119 
120 // 对于原始棋盘,判断是否能输出满足的棋盘
121 int queen_fill_x(int n)
122 {
123     int i;
124     if(n >= QUEEN_N)
125     {
126         queen_print(queen);
127         return 1;
128     }
129     else
130     {
131         for(i = 0; i < QUEEN_N; i++)
132         {
133             if(queen[n][i] == 0)
134             {
135                 queen[n][i] = 1;
136                 if(queen_check(n, i) == 1)
137                 {
138                     if(queen_fill_x(n+1) == 1)
139                         return 1;
140                 }
141                 queen[n][i] = 0;
142             }
143             else
144             {
145                 if(queen_check(n, i) == 1)
146                 {
147                     if(queen_fill_x(n+1) == 1)
148                         return 1;
149                 }
150             }
151         }
152     }
153     return 0;
154 }
155 
156 int main(void)
157 {
158     int iRet;
159     printf("init queen:
");
160     queen_print(queen);
161 
162     printf("queen_fill_x:
");
163     iRet = queen_fill_x(0);
164     if(iRet != 1)
165     {
166         printf("xxx err
");
167     }
168 
169     printf("queen_fill_1:
");
170     queen_fill_1(0);
171 
172     printf("queen_fill_all:
");
173     queen_fill(0);
174 
175     return 0;
176 }

在编写递归枚举程序之前，需要深入分析问题，对模型精雕细琢。一般还应对解答树的结点数有一个粗略的估计，作为对评价模型的重要依据。

递归解决问题的思想：

if 问题足够简单：

　　直接解决问题

　　返回解

else：

　　将问题分解为与原问题同构的一个或多个更小的问题

　　逐个解决这些更小的问题

　　将结果组合为，获得最终的解

　　返回解