同一列、或者同一斜线上。试编写一个递归算法,求解并输出此问题的所有合法布局。(提 示:用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向 反斜线方向的安放状态,若当前布局合法,可向下一行递归求解,否则可移走这个棋子 恢复安放该棋子前的状态,试探本行的第+1列。) 【解答】此为典型的回溯法问题 次对角线 1#次对角线 2#次对角线 3#次对角线 4#次对角线 5#次对角线 6#次对角线 0#主对角线 #主对角线 2#主对角线 主对角线 4#主对角线 5#主对角线 6#主对角线 在解决8皇后时,采用回溯法。在安放第i行皇后时,需要在列的方向从1到n试 探(j=1,…,n):首先在第j列安放一个皇后,如果在列、主对角线、次对角线方向有其它 皇后,则出现攻击,撤消在第j列安放的皇后。如果没有出现攻击,在第j列安放的皇后 不动,递归安放第计1行皇后 解题时设置4个数组 coln]:coll标识第i列是否安放了皇后 md2n-1]:muk]标识第k条主对角线是否安放了皇后 sd2n-1]:sak]标识第k条次对角线是否安放了皇后 q]:q[记录第i行皇后在第几列 利用行号和列号j计算主对角线编号k的方法是k=n+i-1;计算次对角线编号k的 方法是k=计j。n皇后问题解法如下 void Queen( int i)i for intj=1; j i(co=0&&md叶r1=0&&sd==0){∥第i行第j列没有攻击 col=m+r1=s汁=l;q= ∥在第i行第j列安放皇后 出一个布局 forG=0;j<=n;+)cout≤<q<∵,; cout << endl else Queen(i+1); ∥在第计1行安放皇后 co]=md叶+广1=sd=0;q[=0; ∥撤消第i行第j列的皇后5 同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。(提 示：用回溯法。在第 n 行第 j 列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、 反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子， 恢复安放该棋子前的状态，试探本行的第 j+1 列。) 【解答】此为典型的回溯法问题。 在解决 8 皇后时，采用回溯法。在安放第 i 行皇后时，需要在列的方向从 1 到 n 试 探( j = 1, …, n )：首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其它 皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后 不动，递归安放第 i+1 行皇后。 解题时设置 4 个数组： col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] ：md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] ：sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] ：q[i] 记录第 i 行皇后在第几列 利用行号 i 和列号 j 计算主对角线编号 k 的方法是 k = n+i-j-1；计算次对角线编号 k 的 方法是 k = i+j。n 皇后问题解法如下： void Queen( int i ) { for ( int j = 1; j <= n; j++ ) { if ( col[j] == 0 && md[n+i-j-1] == 0 && sd[i+j] == 0 ) { //第 i 行第 j 列没有攻击 col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; //在第 i 行第 j 列安放皇后 if ( i == n ) { //输出一个布局 for ( j = 0; j <= n; j++ ) cout << q[j] << ‘,’; cout << endl; } else Queen ( i+1 ); //在第 i+1 行安放皇后 } col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; //撤消第 i 行第 j 列的皇后 } } 0# 主对角线 1# 主对角线 2# 主对角线 3# 主对角线 4# 主对角线 5# 主对角线 6# 主对角线 6# 次对角线 5# 次对角线 4# 次对角线 3# 次对角线 2# 次对角线 0# 次对角线 1# 次对角线 0 1 2 3 0 1 2 3    