n皇后问题pascal

Description 在一个nXn的国际象棋棋盘上放置n(n<=12)个皇后，使它们不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。试求出第一种（皇后在第i行最靠前的情况下，以后各行也尽量靠前）排列方案，和所有方法。Input输入一个数n .(n<=12)Output输出所有的排列方案总数。Sample Input Copy 4Sample Output Copy 2HINTSource

做法就是深搜，逐行枚举每个皇后的位置，然后用数组记录每列，每个斜线是否有皇后存在以判断当前的位置是否能够放皇后。代码我去写一下，等会补充过来。。。

n皇后问题（非递归） top := 1; // 从第一个皇后开始尝试 while (top > 0) do // 当还有活动节点时循环 if (top > n) then // 是否n个皇后都放置在棋盘了 begin inc(count); // 找到一组解，总数加一 dec(top); // 回到上一皇后继续 end else // n个皇后还没有都放置好 begin inc(x[top]); // 当前皇后到下一列 if (x[top] > n) then // 是否超出棋盘 dec(top) // 超出棋盘，回到上一个皇后继续 else // 没有超出棋盘 if check(top) then // 检查当前位置是否可以放皇后 begin inc(top); // 可以放置，继续尝试下一个皇后 x[top] := 0; // 下一个皇后从第一列开始尝试 end; end; n皇后问题（边界判定） function check(pos: integer): boolean; var i: integer; begin check := true; for i := 1 to pos - 1 do if (x[pos] = x[i]) or (abs(x[pos] - x[i]) = abs(pos - i)) then begin check := false; break; end; end; n皇后问题（递归） procedure search(k: integer); var i: integer; begin if k > n then // 是否前n个皇后都已经放下 inc(count) else // 还有皇后没放 for i := 1 to n do // 从第1列开始逐列尝试 begin x[k] := i; // 把第k个皇后放在第i列 if check(k) then // 第k个皇后是否可以放在第i列 search(k + 1); // 可以放，继续处理第k+1个皇后 end; end;