求PASCAL八皇后问题程序
- 提问者网友：皆是孤独
- 2021-04-23 02:44
- 五星知识达人网友：傲气稳了全场
- 2021-04-23 03:39
procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin
if row<>upperlim then
begin
pos:=upperlim and not (row or ld or rd);
while pos<>0 do
begin
p:=pos and -pos;
pos:=pos-p;
test(row+p,(ld+p)shl 1,(rd+p)shr 1);
end;
end
else inc(sum);
end;
Var
sum,upperlim:longint;
Begin
readln(n);
upperlim:=(1 shl n)-1
test(0,0,0);
writeln(sum);
End.
如果是做8皇后，就输入8就行。
上面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。
拿这个去交USACO，0.3s，暴爽。（Ps:一般的八皇后usaco上交，都要1.0s+，就算是cpp/c写的代码，也要RP爆高才会0.99999999……s过掉。）
=====================以上摘自matrix67 Blog并稍做修改。===========================
“Matrix67原创
转贴请注明出处”
- 1楼网友：走死在岁月里
- 2021-04-23 04:38
这时我以前做过的
附上程序和解释
|
program eightqueens; var x:array[1..8] of integer; a,b,c:array[-7..16] of boolean; i:integer; procedure print; var k:integer; begin for k:=1 to 8 do write(x[k]:4); writeln; end; procedure try(i:integer); var j:integer; begin for j:=1 to 8 do if a[j] and b[i+j] and c[i-j] then begin x:=j; a[j]:=false; b[i+j]:=false; c[i-j]:=false; if i<8 then try(i+1) else print; a[j]:=true; b[i+j]:=true; c[i-j]:=true end end; begin for i:=-7 to 16 do begin a:=true; b:=true; c:=true end; try(1); end. 现在循环从 i=1 ,j:=1 to 8 do 开始 此时 计算机检测到 i=1 j=1 简化为（1，1）为空，占用该位置并令该位置对应的斜线和水平方向的位置为 false ，然后程序就开始去执行try（2），注意此时计算机在i=1 这层仅仅走拉一个循环（j=1）就跳到拉i=2 这层里此时计算机从j：=1 to 8 do 又开始循环，排除 j=1，j=2 得到 （2，3）注意计算机在层里也只是走拉3（j=3）个循环然后又跳到拉i=3 这层依次类推得到（3，5），（4，2）（5，4）而在i=6 这层里计算机从j：= 1 to 8 do 都没有找到合适的位置，此时注意在i=6 这层里计算机计算机将返回到i=5 这层里，（因为用拉递归）并且释放（5，4）该位置，为什么要释放呢？因为原因很简单如果不释放的话 该位置对应的斜线和水平方向会对以后的几层造成影响，让计算机误认为为false。此时的在i=5这层里 j=4才是结束,然后计算机又会从j=5到 8 开始去找合适的位置 ，如果找不到又会返回到上一层依次类推直到计算机找到一组解 输出，假设在（8，3）这个位置是计算机找到的一组解，此时计算机又会从j=4到8 开始循环，如果找不到 计算机就会返回上一层的即i=7这层接着上一次的跳出位置走完以后的循环，依次类推不断的返回，跳出， 求解，（即令前几个位置不变，从第8个位置变换，没有空位置的。接会返回上一层）最后返回到i=1这层里，注意此时在这层里也只是走拉j=1个循环然后计算机就又开始从j= 2 去试着找....大家有没有算过求出所有的解要走过多少个循环？我想估计也不下1000个吧。其实整个过程就是一个重复的过程（即递归）倒着想在i=7 这层里的j=1 位置即（7，1） 计算机会去试从（8，1）到（8，8）这8 个位置，而在（7，2）也同样会去试这8 个位置 等等在（6，1）会试（7，1）到（7，8） 等。 这是正着考虑（1，1）这里计算机会试着从（2，1）到（2，8）这8个位置而在这8 个位置里并没有试完就有空位置 （2，3）此时计算机会在这个位置对下一层里开始试（3，1）..（3，8）依次类推，试不通的返回，接着走完上一层直到试完所有的位置！ |