一个pascal语言的8皇后问题

显示全部楼层 · 2011-10-16 09:12:58

vart,i,j,k:integer;b,c,d:array[-7..16]ofinteger;a:array[1..8,1..8]ofboolean;procedureprint;begint:=t1;writeln(t);fori:=1to8doforj:=1to8doifa[i,j]thenwrite(i:3,\',\',j,\'\');fillchar(a,sizeof(a),false);writeln;end;proceduretry(i:integer);beginforj:=1to8doif(b[j]=0)and(c[i-j]=0)and(d[ij]=0)thenbegina[i,j]:=true;b[j]:=1;c[i-j]:=1;d[ij]:=1;ifi8thentry(i1)elseprint;b[j]:=0;c[i-j]:=0;d[ij]:=0;end;end;begint:=0;fillchar(a,sizeof(a),false);fork:=-7to16dobeginb[k]:=0;c[k]:=0;d[k]:=0;end;try(1);readln;end.也是用回溯，但我改用a作为布尔行标记数组。问题在于运行没有结果。求改错

千问 · 2011-10-16 09:12:58

proceduretry(i:integer);beginforj:=1to8doif(b[j]=0)and(c[i-j]=0)and(d[ij]=0)thenbegina[i,j]:=true;b[j]:=1;c[i-j]:=1;d[ij]:=1;为什么他们都=1？追问标记占领啊不过好像是我提问的，怎么有点反过来了

千问 · 2011-10-16 09:12:58

c,d数组什么意思嘛，没看懂难不成表示左倾45°，右倾45°？你可以计算当前要考虑的i，j与已经放置的皇后的i，j求斜率，若为±1则不能放另：你想继续优化的话，考虑对称，usaco第一章最后一题，13皇后1s够

千问 · 2011-10-16 09:12:58

b，表示占领行或者当成列也行。c，d分别表示占领的两种斜线\'\\\',\'/\'经你提示对称，我立即想到了4种对称方法（上下，左右，双斜线），但如何避免搜索到重复的（有对称得出的皇后位置）这个剪枝好像有点难，没想出。

千问 · 2011-10-16 09:12:58

其实我只是实现过左右对称，其他的我也不会，自己想想，就在深搜的退出条件里加就行了

千问 · 2011-10-16 09:12:58

你可以吧usaco那道题的链接发过来吗？我找不到，英文太多了。给你说一下我的理解，你可以把它当作棋盘，搜出一种情况后，顺时针分别旋转90，180，270，360°，这些情况必然同样成立。但，这样的话，退出条件就复杂了。这点我没弄懂。

千问 · 2011-10-16 09:12:58

http://ace.delos.com/usacoprob2?a=yfE6jP8MhMfdefds123S=checker要知道虽然在判退出时费点时间，但是判掉的东西如果运行会更费时间。左右对称好编写，省大约50%时间

千问 · 2011-10-16 09:12:58

你没学好搜索吧，j应该要写成局部变量。另外皇后问题的构造方法是有的，当然更简单而高效的算法是随机化算法，这个是优化后的搜索，还有try好像是不建议使用的程序名，尽量避免吧。再者你的a数组在try后要重新变为false，然后可以去掉print里面的初始，不然你会看到放了不止8个皇后。追问搜索学的本来觉得倒也还凑合。如今发现确实还很不够。print里对a的初始应该是不能省的，虽然这样也不对，所以这个问题让我很纠结。其实我会一种一维标记的写法，只是想练习才写个二维的，没想到问题这么多？