算法第八章.ppt

procedure PLACE(k) int i , k; i=1; while ( ik ) do { if (X[i]==X[k] or ABS(X[i]-X[k])==ABS(i-k)) then return (false); i=i+1; } return (true); end PLACE 若一个皇后能放在第k行和第X(k)列, 则返回true, 否则返回false X是全程数组, 进入此过程时已置入了k个值, ABS是绝对值函数 能否放置一个新皇后的算法描述: 注: 两个皇后被放置在(i, j )和(k, l )位置上 所以 j=X[i], l=X[k], |j-l| = |i-k| 即为 ABS(X[i]-X[k])==ABS(i-k) // 若两个皇后在同一列上, 或在 同一对角线上, 则说明该位置 不能放皇后, 应返回false值 求n-皇后问题的回溯算法描述 procedure NQUEENS(n) int k, n, X(1:n); X[1]=0 ; k=1; while (k0) do { X[k]=X[k]+1; while ( X[k]=n and Not PLACE(k) ) do { X[k]=X[k]+1; } if (X[k]=n) then { if (k==n) then print (X); else { k=k+1; X[k]=0; } } else k=k-1; } end NQUEENS //若是一个完整的解则打印数组X // k是当前行; X(k)是当前列 // 对所有的行执行循环语句 //移到下一列 当该位置不能放皇后时转到下一列 //找到一个位置 //否则转到下一行 // 没有合适的位置, 回溯 1 2 3 4 X 0 0 1 Q1 PLACE(1) i=1; while ( ik ) do 11 , 循环不执行 return (true); X[1]=0 ; k=1; while (k0) do { X[k]=X[k]+1; while (X[k]=n and Not PLACE(k)) do 1=n and Not true , 循环不执行 if (X[k]=n) then if (k≠n) then 不执行 else { k=k+1=2; X[2]=0; } } end while k=2; while (k0) do { X[k]=X[k]+1; while ( X[k]=n and Not PLACE(k) ) do 1=n and Not false , X[k]=X[k]+1=2; 2=n and Not false , X[k]=X[k]+1=3; 3=n and Not true , 循环不执行 1 2 3 if (X[k]=n) then if (k≠n) then 不执行 else { k=k+1=3; X[3]=0; } 0 } end while Q2 PLACE(2) i=1; while ( ik ) do if (X[i]==X[k]) then return (false); PLACE(2) i=1; while ( ik ) do if (|X[i]-X[k]|==|i-k|) then return (false); PLACE(2) i=1; while ( ik ) do { if (X[i]≠X[k] or |X[i]-X[k]|≠|i-k|) then 不执行 i=i+1=2; 结束循环 } return (true); 1 2 3 4 X 1 3 0 Q1 Q2 k=3; while (k0) do { X[k]=X[k]+1; while (X[k]=n and Not PLACE(k))