Question

八皇后问题 pascal

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:=1to 8do
write(x[k]:4);
writeln
end;
procedure try(i:integer);
var
j:integer;
begin
for j:=1to 8do
if a[j]and b[i+j]and c[i-j]
then begin
x[i]:=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[i]:=true;
b[i]:=true;
c[i]:=true
end;
try(1)
end.

既然已经定义成false了，为什么还要到最后再变成true呢？

Answer 1

因为 if a[j]and b[i+j]and c[i-j]
then begin
x[i]:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
if i<8 then try(i+1)
这个语句赋值成FALSE后，你的搜索深度进入下一层。而在最后回溯的时候，必须要把它还原，才能保证答案的正确性。举个例子来说吧，你现在在一个错综复杂的迷宫里迷路了，有两条路选择，你选择了其中一条路线，为了记录自己的位置，你在这个地方丢了一个石子，就相当于赋值成FALSE，表示你以后就不会再从这里走了，因为你刚才已经走过这里。当你发现这条路走不通的时候，你开始往回走，要走到最开始的路口。在往回走的过程中，为了不被第一次的路线所迷惑，你每见到一个以前丢下的石子，就要把它捡起来，这样才能恢复最开始的状态，就相当于在最后变成TRUE。
也许你会说，为什么要把它捡起来呢？放在原地不也可以吗？请注意，这个迷宫是错综复杂的，就像你在八皇后搜索中不断深搜建立的树一样。有可能你从另外一个路口走到上一次所走的地方，因为门变了的缘故而可以通过，所以你要把一切还原。
LZ你的搜索是最原始的回溯，回溯的意思你懂吧？
至于八皇后问题，LZ的深搜效率确实很低……普通的宽搜会稍微好一点，当然，还有更好的算法，在这里就不介绍了，你可以去看下算法艺术这本书……

Answer 2

回溯到上一个状态，开始下一次的搜索