斜率+1,i+j={0,1,,14 斜率1,i={7,6,…,7 01234567 01234567 0 l 456 7团团区 7 皇后的控制范围 试探安排八个皇后 ●第个皇后时,前面几个皇后在各列、 ·从第0行开始,逐步安排每行皇后 各对角线上的占用情况 ·对第个皇后,找正确的位置(设为第列 bool A[n];∥前0.i-1行皇后占用列 ·A]、B[+]、c[于7]都没有被占用 bool e[2n1];∥斜率为+1的对角线 ·标记A]、B[+、C[于7为被占用状态 继续安排下一个皇后(第|1个 bool c[2+n-1];∥斜率为-1,c[ij7 ●否则,如果找不到合适位置,应该退回 (即“回溯)到第|-1行的皇后,重新安排 前面的安排不太合理 回溯过程 回溯法的框架 如果8个皇后都排好了,则打印这种方案 ·问题的解n元组(xX (k)【∥初始调 retry(0) 染璽蒼鹞空葬委排痨渎溯,重新试 置X〖k为第 可能值 e(Xk可能值没有试完) 设置X[k]所涉及的标 訂甸试探男奕第颔狀蒌复A (X[0],X1],…,Xn-1】)是解) 打印一组解; 种回溯过程将逐步返回 使得各行的皇后都能试探到各种可能的摆法 回溯,抹去X涉及的标记; 取下一个可能的X值7 斜率+1，i+j={0, 1, …, 14} 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 斜率-1，i-j={-7, 6, …, 7} 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 皇后的控制范围 z 第i个皇后时，前面几个皇后在各列、 各对角线上的占用情况 bool A[n]; // 前0..i-1行皇后占用列 bool B[2*n-1]; // 斜率为+1的对角线 bool C[2*n-1]; // 斜率为-1， C[i-j+7] 试探安排八个皇后 z 从第0行开始，逐步安排每行皇后。 z 对第i个皇后，找正确的位置(设为第j列 z A[j]、B[i+j]、C[i-j+7]都没有被占用 z 标记A[j]、B[i+j]、C[i-j+7]为被占用状态 z 继续安排下一个皇后(第i+1个) z 否则，如果找不到合适位置，应该退回 (即“回溯”)到第i-1行的皇后，重新安排 z 前面的安排不太合理 回溯过程 z 如果8个皇后都排好了，则打印这种方案 z 为了找到其它方案，应该回溯，重新试 探皇后的下一种安排方法 z 抹掉前面试探留下的标记，即恢复A[j]、 B[i+j]、C[i-j+7]为未被占用状态 z 这种回溯过程将逐步返回 z 使得各行的皇后都能试探到各种可能的摆法 回溯法的框架 z 问题的解n元组(x0, x1,…，xn-1)： void rectry(k) { // 初始调rectry(0); 置X[k]为第一个可能值； while (X[k]可能值没有试完) { 设置X[k]所涉及的标记; if ((X[0], X[1]，…，X[n-1])是解) 打印一组解; else rectry(k+1); 回溯，抹去X[k]涉及的标记； 取下一个可能的X[k]值; } }