用递归回溯法求N后问题 先国顺递归回溯法的一般形式: ■做挑选候选者的准备; while(未成功且还有候选者){ 挑选下一个候选者next; if(next可接受){ 记录next; if(满足成功条件){成功并输出结果} else Try(s+1) if(不成功)删去next的记录;} return成功与否} 2021/22 计算机算法设计与分析 16
2021/2/21 计算机算法设计与分析 16 用递归回溯法求N后问题 ◼ Try(s){ ◼ 做挑选候选者的准备； ◼ while (未成功且还有候选者) { ◼ 挑选下一个候选者next； ◼ if (next可接受) { ◼ 记录next； ◼ if (满足成功条件) {成功并输出结果} ◼ else Try(s+1); ◼ if (不成功) 删去next的记录; }} ◼ return 成功与否} 先回顾递归回溯法的一般形式：
用递归回溯法求N后问题 Try(S 列税列数不到n就还有候选者 j=0;,q=0 列 while(aq&&j<n){各后都安全,便可接受 下该行后的位置列数 if(safe(s,j){n行后都放完不成功,删 Record(s, j 去后在该行 if(s=n){q=1, output(的位置。 else Try(s+1) if(q Move-Off(S,1:)N) a return q) 2021/22 计算机算法设计与分析 17
2021/2/21 计算机算法设计与分析 17 用递归回溯法求N后问题 ◼ Try(s){ ◼ 做挑选候选者的准备； ◼ while (未成功且还有候选者) { ◼ 挑选下一个候选者next； ◼ if (next可接受) { ◼ 记录next； ◼ if (满足成功条件) {成功并输出结果} ◼ else Try(s+1); ◼ if (不成功) 删去next的记录; }} ◼ return 成功与否} s为准备放置后的行数 候选者为1到n列。 j = 0; q = 0; 令列标记列数不到 j = 0；q n表示未成功。 就还有候选者 (!q && j < n ) { 列数加1 j++; 各后都安全，便可接受 (Safe(s, j)) { 记下该行后的位置(列数) Record(s, j); n行后都放完就成功了 (s = = n) {q = 1; output( );} 不成功，删 去后在该行 的位置。 (!q) Move-Off(s, j); }}} q }
求解N后问题中的数据表示 ■数组B[n表示棋盘。若B[j,1≤,jn,表示 棋盘的第第j列上有皇后。 ■数组Ci]1表示第j列上无皇后,1≤n 数组D|k=1表示第k条下行(y)NNN 对角线上无皇后 这里, k=i+j,2≤k<2no 23456 2021/22 计算机算法设计与分析 18
2021/2/21 计算机算法设计与分析 18 求解N后问题中的数据表示 ◼ 数组B[n]表示棋盘。若B[i]=j，1≤i, j≤n，表示 棋盘的第i行第j列上有皇后。 ◼ 数组C[j]=1表示第j列上无皇后，1≤j≤n。 ◼ 数组D[k]=1表示第k条下行(↘) 对角线上无皇后。 1 2 3 4 5 6 1 2 3 4 5 6 k = i + j ，2≤k≤2n。 这里
求解N后问题中的数据表示 ■数组B[m表示棋盘。若B=j,1si,jn,表 示棋盘的第行第上有皇后 数组Ci]=1表示第例上无皇后,1≤n 数组D|k]=1表示第k条下行6 (y)对角线上无皇后。这里, k=1+j,2≤≤2no 数组U队]=1表示第条上行3 (x)对角线上无皇后。这里,1 k=i-j, -n+lsksn 2021/22 计算机算法设计与分析 19
2021/2/21 计算机算法设计与分析 19 求解N后问题中的数据表示 ◼ 数组B[n]表示棋盘。若B[i] = j，1≤i, j≤n，表 示棋盘的第i行第j列上有皇后。 ◼ 数组C[j] = 1表示第j列上无皇后，1≤j≤n。 ◼ 数组D[k] = 1表示第k条下行 (↘)对角线上无皇后。 k = i + j ，2≤k≤2n。 这里， ◼ 数组U[k] = 1表示第k条上行 (↗)对角线上无皇后。 1 2 3 4 5 6 k = i – j ， –n+1≤k≤n–1。 1 2 3 4 5 6 这里
求解N后问题中的子程序 a Record(s,jik=s-j+n-1 B[S]=j,Ci]=0;D[s+j-1]=0;U]=0;} Move-Off(s,D<k=s-i+n-1,Uk=l;) B[S]=0;CD]=1;D[s+j-1]=1 Safe(s,jk=s-j+n-1; if(Clil &&uk]&& ds +j-1Dreturn true else return false; i 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 20 求解N后问题中的子程序 ◼ Record(s, j) { k = s – j + n – 1; B[s] = j; C[j] = 0; D[s + j – 1] = 0; U[k] = 0; } ◼ Move-Off(s, j) {k = s – j + n – 1; B[s] = 0; C[j] = 1; D[s + j – 1] = 1; U[k] = 1; } ◼ Safe(s, j) {k = s – j + n – 1; if (C[j] && U[k] && D[s + j – 1]) return true else return false; }