在软件编程中，这种思路确是一种解决问题最简单的算法，它通过一种类似于蛮干的思路，一步一步地往前走，每走一步都更靠近目标结果一些，直到遇到障碍物，我们才考虑往回走。
正文
C#用递归算法解决八皇后问题
1.引子
中国有一句古话，叫做“不撞南墙不回头"，生动的说明了一个人的固执，有点贬义，但是在软件编程中，这种思路确是一种解决问题最简单的算法，它通过一种类似于蛮干的思路，一步一步地往前走，每走一步都更靠近目标结果一些，直到遇到障碍物，我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法，最终达到目的地。当然整个过程需要很多往返，这样的前进方式，效率比较低下。
2.适用范围
适用于那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题。
3.应用场景
在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。国际象棋的棋盘如下图所示：
4.分析
基本思路如上面分析一致，我们采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉
1）x=row(在纵向不能有两个皇后)
2）y=col（横向）
3）col + row = y+x;（斜向正方向）
4）col - row = y-x;（斜向反方向）
遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。
我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，c(64,80) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置，而第五列，我们会发现找不到皇后的安全位置了，前面四列的摆放如下:
第五列的时候，摆放任何行都会上图所示已经存在的皇后的攻击，这时候我们认为我们撞了南墙了，是回头的时候了，我们后退一列，将原来摆放在第四列的皇后（3，4）拿走，从（3，4）这个位置开始，我们再第四列中寻找下一个安全位置为（7，4），再继续到第五列，发现第五列仍然没有安全位置，回溯到第四列，此时第四列也是一个死胡同了，我们再回溯到第三列，这样前进几步，回退一步，最终直到在第8列上找到一个安全位置（成功）或者第一列已经是死胡同，但是第8列仍然没有找到安全位置为止
总结一下，用回溯的方法解决8皇后问题的步骤为：
1）从第一列开始，为皇后找到安全位置，然后跳到下一列
2）如果在第n列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯
3）如果在第8列上找到了安全位置，则棋局成功。
8个皇后都找到了安全位置代表棋局的成功，用一个长度为8的整数数组queenlist代表成功摆放的8个皇后，数组索引代表棋盘的col向量，而数组的值为棋盘的row向
量，所以(row,col)的皇后可以表示为(queenlist[col],col),如上图中的几个皇后可表示为：
queenlist[0] = 0; queenlist[1] = 3; queenlist[2] = 1; queenlist[3] = 4; queenlist = 2;
我们看一下如何设计程序:
首先判断(row,col)是否是安全位置的算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
bool issafe(int col,int row,int[] queenlist){ //只检查前面的列 for (int tempcol = 0; tempcol < col; tempcol++) { int temprow = queenlist[tempcol]; if (temprow == row) { //同一行 return false; } if (tempcol == col) { //同一列 return false; } if (temprow - tempcol == row - col || temprow + tempcol == row + col) { return false; } } return true;} |
设定一个函数，用于查找col列后的皇后摆放方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
/// <summary>/// 在第col列寻找安全的row值/// </summary>/// <param name="queenlist"></param>/// <param name="col"></param>/// <returns></returns>public bool placequeue(int[] queenlist, int col){ int row = 0; bool foundsafepos = false; if (col == 8) //结束标志 { //当处理完第8列的完成 foundsafepos = true; } else { while (row < 8 && !foundsafepos) { if (issafe(col, row, queenlist)) { //找到安全位置 queenlist[col] = row; //找下一列的安全位置 foundsafepos = placequeue(queenlist, col + 1); if (!foundsafepos) { row++; } } else { row++; } } } return foundsafepos;} |
调用方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
static void main(string[] args){ eightqueen eq = new eightqueen(); int[] queenlist = new int[8]; for (int j = 0; j < 8; j++) { console.writeline("-----------------"+j+"---------------------"); queenlist[0] = j; bool res = eq.placequeue(queenlist, 1); if (res) { console.write(" "); for (int i = 0; i < 8; i++) { console.write(" " + i.tostring() + " "); } console.writeline(""); for (int i = 0; i < 8; i++) { console.write(" "+i.tostring()+" "); for (int a = 0; a < 8; a++) { if (i == queenlist[a]) { console.write(" q "); } else { console.write(" * "); } } console.writeline(""); } console.writeline("---------------------------------------"); } else { console.writeline("不能完成棋局，棋局失败！"); } } console.read();} |
递归算法placequeue,完成这样的功能：它寻找第col列后的皇后的安全摆放位置，如果该函数返回了false,表示当前进入了死胡同，需要进行回溯，直到为0-7列都找
到了安全位置或者找遍这些列都找不到安全位置的时候终止。
用递归算法解决8皇后问题的示例程序：
eightqueens.rar
发表评论