|
Posted on 2008-11-20 21:54 阿呆 阅读(400) 评论(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个皇后 4int 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}
|