|
|
Posted on 2008-11-20 21:54 阿呆 阅读(403) 评论(0) 编辑 收藏 引用 所属分类: 编码练习题
在一个8×8国际象棋盘上，有8个皇后，每个皇后占一格；要求皇后间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法。 以下程序利用回溯法找出一组排放位置。 对每一行查找该行中符合条件的位置，如果找到，将该行的皇后放在该位置，同时设置列和两条对角线的标志；否则，说明上一行的皇后（记为i）位置不正确，再从皇后i当前位置的下一个位置找符合的位置。 如下边的矩阵，红色位置就是程序找到的放置皇后的位置。 // 00 01 02 03 04 05 06 07 //10 11 12 13 14 15 16 17 //20 21 22 23 24 25 26 27//30 31 32 33 34 35 36 37//40 41 42 43 44 45 46 47 //50 51 52 53 54 55 56 57 //60 61 62 63 64 65 66 67 //70 71 72 73 74 75 76 77
1
2//iQuenePos[i]表示第i个皇后的位置，i表示棋盘上的行
3//也就是说，第i行上的皇后称为第i个皇后
4  int iQueenPos[8] =  {-1, -1, -1, -1, -1, -1, -1, -1};
5
6//记录第i列是否被占领
7bool bIsCaptured[8] = {false, false, false, false, false, false, false, false};
8
9//从左上到右下的对角线。某个位置Pij，j-i=常数的位置在同一条对角线上
10//i-j在[-7,7]范围内，在数组中对应为bDiagnal[j-i+7]
11//对角线的条数为(n - 1) * 2 - 1
12bool bDiagnal[13] = {false, false, false, false, false, false, false, false, false, false, false, false, false};
13
14//从右上到左下的对角线，某个位置Pij，j+i=常数的位置在同一条反对角线上，
15//j+i在[1,13]范围内，在数组中对应为bBackDiagnal[j+i-1]
16//对角线的条数为(n - 1) * 2 - 1
17bool bBackDiagnal[13] = {false, false, false, false, false, false, false, false, false, false, false, false, false};
18
19
20//从第index行的第StartPos列开始查找该行的皇后放在哪个位置
21bool Try(int index, int StartPos = 0);
22
23int _tmain(int argc, _TCHAR* argv[])
24{
25 int iStartPos = 0;
26 //防治第i行的皇后
27 for (int i = 0; i < 8; i++)
28  {
29 //如果在该行没有合适的位置，那么上一行的皇后位置往后调换
30 if (!Try(i, iStartPos))
31 {
32 i -= 2;//下次针对上一行的皇后进行调换
33 iStartPos = iQueenPos[i + 1] + 1;//对上一行的皇后进行调换时，从上一行皇后的当前位置的下一个位置开始
34 //iQueenPos[i + 1] = -1;//标志上一行的皇后没有放置，此行可有可无，但调试时可更清楚些
35 }
36 else
37 {
38 //该行皇后已经找到合适位置，下一行从第0个位置开始查找
39 iStartPos = 0;
40 }
41 }
42 return 0;
43 }
44
45bool Try(int index, int StartPos/**//* = 0*/)
46{
47 for (int j = StartPos; j < 8; j++)
48 {
49 if (!bIsCaptured[j] && !bDiagnal[j - index + 7] && !bBackDiagnal[j + index - 1])
50 {
51 iQueenPos[index] = j;//将第idex行的皇后放在该行的第j个位置上
52 bIsCaptured[j] = 1;
53 bDiagnal[j - index + 7] = 1;
54 bBackDiagnal[j + index - 1] = 1;
55 return true;
56 }
57 }
58 bIsCaptured[iQueenPos[index - 1]] = 0;
59 bDiagnal[iQueenPos[index - 1] - (index - 1) + 7] = 0;
60 bBackDiagnal[iQueenPos[index - 1] + (index - 1) - 1] = 0;
61 return false;
62}
|