📄 八皇后.htm
字号:
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD></TR>
<TR>
<TD height=27>
<DIV align=center>－</DIV></TD>
<TD height=27>
<DIV align=center>－</DIV></TD>
<TD height=27>
<DIV align=center>－</DIV></TD>
<TD height=27>
<DIV align=center>▲</DIV></TD>
<TD height=27>
<DIV align=center>－</DIV></TD>
<TD height=27>
<DIV align=center>－</DIV></TD>
<TD height=27>
<DIV align=center>－</DIV></TD>
<TD height=27>
<DIV align=center>－</DIV></TD></TR>
<TR>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center>／</DIV></TD>
<TD height=27>
<DIV align=center>｜</DIV></TD>
<TD height=27>
<DIV align=center>＼</DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD></TR>
<TR>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center>／</DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center>｜<BR></DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center>＼</DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD></TR>
<TR>
<TD height=27>
<DIV align=center>／</DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center>｜</DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD>
<TD height=27>
<DIV align=center>＼</DIV></TD>
<TD height=27>
<DIV align=center> </DIV></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD height=24>
<DIV align=center>２</DIV></TD></TR>
<TR>
<TD height=24>
<DIV align=center>３</DIV></TD></TR>
<TR>
<TD height=24>
<DIV align=center>４</DIV></TD></TR>
<TR>
<TD height=24>
<DIV align=center>５</DIV></TD></TR>
<TR>
<TD height=24>
<DIV align=center>６</DIV></TD></TR>
<TR>
<TD height=24>
<DIV align=center>７</DIV></TD></TR>
<TR>
<TD height=24>
<DIV align=center>８</DIV></TD></TR></TBODY></TABLE>
<P align=left> 对于一组布局我们可以用一个一维数组来表示：X:ARRAY [1..8] OF
INTEGER;X[I]的下标I表示第I个皇后在棋盘的第I行，X[I]的内容表示在第I行的第X[I]列，例如：X[3]=5就表示第3个皇后在第3行的第5列。在这种方式下，要表示两个皇后A和B不在同一列或斜线上的条件可以描述为：X[A]<>X[B]
AND ABS(A-B)<>ABS(X[A]-X[B]){A和B分别表示两个皇后的行号}<BR><SPAN
class=style3>【解法】<FONT
color=#000000>有了上面的分析，相信大家可以找到不同的</FONT></SPAN><FONT
color=#000000>算法</FONT><SPAN class=style3><FONT
color=#000000>，这里我们提供三种，当然稍加改动就可推广到Ｎ皇后问题</FONT></SPAN><BR>PROGRAM
QN(INPUT,OUTPUT);{<SPAN class=style1>递归算法</SPAN>}<BR>CONST
N=8;<BR>VAR<BR> CONT,I:INTEGER;<BR> A:ARRAY[1..N] OF
BYTE;{存放正确的一组解}<BR> C:ARRAY[1..N] OF
BOOLEAN;{存放某一列放皇后的情况，用于判断是否有同列的情况}<BR> L:ARRAY[1-N..N-1] OF
BOOLEAN;{存放某一斜线上放皇后的情况，用于判断是否有同斜线的情况；斜线的方向为＼}<BR> R:ARRAY[2..2*N] OF
BOOLEAN;{存放某一斜线上放皇后的情况，用于判断是否有同斜线的情况；斜线的方向为／}</P>
<P align=left> PROCEDURE PR;<BR> VAR<BR> I:INTEGER;<BR> BEGIN<BR> FOR
I:=1 TO N DO WRITE(A[I]:4);<BR> INC(CONT);<BR> WRITELN('
CONT=',CONT);<BR> END; </P>
<P align=left> PROCEDURE TRY(I:INTEGER);<BR> VAR<BR> J:INTEGER; </P>
<P align=left> PROCEDURE
ERASE(I:INTEGER);<BR> BEGIN<BR> C[J]:=TRUE;<BR> L[I-J]:=TRUE;<BR> R[I+J]:=TRUE;<BR> END;<BR> BEGIN<BR> FOR
J:=1 TO N DO<BR> BEGIN<BR> IF C[J] AND L[I-J] AND R[I+J]
THEN<BR> BEGIN<BR> A[I]:=J;<BR> C[J]:=FALSE;<BR> L[I-J]:=FALSE;<BR> R[I+J]:=FALSE;<BR> IF
I<N THEN TRY(I+1) ELSE
PR;<BR> ERASE(I);<BR> END;<BR> END;<BR> END; </P>
<P align=left>BEGIN<BR> FOR I:=1 TO N DO C[I]:=TRUE;<BR> FOR I:=1-N TO N-1
DO L[I]:=TRUE;<BR> FOR I:=2 TO 2*N DO
R[I]:=TRUE;<BR> CONT:=0;<BR> I:=1;<BR> TRY(I);<BR> WRITELN;<BR> WRITELN('PROGRAM
END.');<BR> READLN;<BR>END.
<P align=left>PROGRAM HUANGHOU(INPUT,OUTPUT);{<SPAN
class=style2>迭代回溯算法</SPAN>}<BR>CONST
N=8;<BR>VAR<BR> K:INTEGER;<BR> X:ARRAY[1..N] OF INTEGER;
<P align=left> FUNCTION
PLACE(K:INTEGER):BOOLEAN;<BR> VAR<BR> I:INTEGER;<BR> BEGIN<BR> I:=1;<BR> WHILE
I<K DO<BR> BEGIN<BR> IF (ABS(X[I]-X[K])=ABS(I-K)) OR (X[I]=X[K])
THEN<BR> BEGIN<BR> PLACE:=FALSE;<BR> EXIT;<BR> END;<BR> I:=I+1;<BR> END;<BR> PLACE:=TRUE;<BR> END;</P>
<P align=left> PROCEDURE PRN;<BR> VAR<BR> I:INTEGER;<BR> BEGIN<BR> FOR
I:=1 TO N DO WRITE(X[I]:4);<BR> WRITELN;<BR> END;</P>
<P align=left> PROCEDURE
NQUEENS(N:INTEGER);<BR> BEGIN<BR> X[1]:=0;<BR> K:=1;<BR> WHILE K>0
DO<BR> BEGIN<BR> X[K]:=X[K]+1;<BR> WHILE ((X[K]<=N) AND (NOT
PLACE(K))) DO X[K]:=X[K]+1;<BR> IF X[K]<=N THEN<BR> BEGIN<BR> IF
K=N THEN
PRN<BR> ELSE<BR> BEGIN<BR> K:=K+1;<BR> X[K]:=0;<BR> END;<BR> END<BR> ELSE
K:=K-1;<BR> END;<BR> END;</P>
<P align=left>BEGIN<BR> NQUEENS(N);<BR> READLN;<BR>END.</P>
<P align=left>program bahh;{<SPAN
class=style2>递归回溯算法</SPAN>}<BR>var<BR> stack:array[1..20] of
byte;<BR> n,total:integer;<BR><BR> procedure
make(l:integer);<BR> var<BR> i,j:integer;<BR>
att:boolean;<BR> begin<BR> if l=n+1 then<BR>
begin<BR> inc(total);<BR>
writeln('No:',total);<BR> for j:=1 to n do writeln('
',stack[j],'*');<BR> writeln;<BR> exit;<BR>
end;<BR> for i:=1 to n do<BR> begin<BR>
att:=false;<BR> stack[l]:=i;<BR> for j:=1 to l-1
do<BR> if(abs(l-j)=abs(stack[j]-i))or(i=stack[j])
then<BR> begin<BR>
att:=true;<BR> j:=l-1;<BR>
end;<BR> if not att then make(l+1);<BR>
end;<BR> end;<BR>begin<BR> total:=0;<BR> fillchar(stack,sizeof(stack),0);<BR> write('n=');<BR> readln(n);<BR> make(1);<BR> writeln('Total=':9,total);<BR> readln;<BR>end.</P>
<P align=left>PROGRAM BHH(INPUT,OUTPUT);{<SPAN class=style2>穷举算法<FONT
color=#000000><SPAN
style="FONT-WEIGHT: 400">：最好理解，但效率最低</SPAN></FONT></SPAN>}<BR>CONST
N=8;<BR>VAR<BR> I1,I2,I3,I4,I5,I6,I7,I8:INTEGER;<BR> X:ARRAY [1..N] OF
INTEGER;</P>
<P align=left> PROCEDURE
PRINT;{输出正确的解}<BR> VAR<BR> I:INTEGER;<BR> BEGIN<BR> FOR I:=1 TO N DO
WRITE(X[I]);<BR> WRITELN;<BR> END;</P>
<P align=left> FUNCTION
CHECK():BOOLEAN;<BR> VAR<BR> A,B:INTEGER;<BR> BEGIN<BR> FOR A:=2 TO N
DO<BR> BEGIN<BR> FOR B:=1 TO A-1 DO<BR> BEGIN<BR> IF
(ABS(X[A]-X[B])=ABS(A-B)) OR (X[A]=X[B])
THEN<BR> BEGIN<BR> CHECK:=FALSE;<BR> EXIT;<BR> END;<BR> END;<BR> END;<BR> CHECK:=TRUE;<BR> END;</P>
<P align=left>BEGIN<BR> FOR I1:=1 TO N DO<BR> FOR I2:=1 TO N DO<BR> FOR
I3:=1 TO N DO<BR> FOR I4:=1 TO N DO<BR> FOR I5:=1 TO N
DO<BR> FOR I6:=1 TO N DO<BR> FOR I7:=1 TO N DO<BR> FOR
I8:=1 TO N
DO<BR> BEGIN<BR> X[1]:=I1;<BR> X[2]:=I2;<BR> X[3]:=I3;<BR> X[4]:=I4;<BR> X[5]:=I5;<BR> X[6]:=I6;<BR> X[7]:=I7;<BR> X[8]:=I8;<BR> IF
CHECK() THEN PRINT;<BR> END;<BR> READLN;<BR>END.</P></DIV></TD></TR>
<TR>
<TD background=八皇后_files/main_center.gif height=45> </TD></TR>
<TR>
<TD background=八皇后_files/main_bottom.gif height=102>
<DIV align=center>
<DIV align=center>
<TABLE id=table3 width=457 border=0>
<TBODY>
<TR>
<TD width=57 rowSpan=3><IMG height=31 src="八皇后_files/noilogo.gif"
width=88 border=1></TD>
<TD width=127>
<DIV align=center>MSN：root@xm818.com</DIV></TD>
<TD width=86>
<DIV align=center>QQ：76455837</DIV></TD>
<TD width=137>
<DIV align=center><FONT color=#000000><A
href="mailto:root@xm818.com">mailto:root@xm818.com</A></FONT></DIV></TD></TR>
<TR>
<TD colSpan=3>
<DIV align=center><FONT color=#ff0000><A
href="http://www.xm818.com/" target=_blank><FONT
color=#ff0000>厦门八一八</FONT></A> </FONT><FONT
color=#0000ff>二00五年元月一日</FONT>
</DIV></TD></TR></TBODY></TABLE></DIV></DIV></TD></TR></TBODY></TABLE></DIV></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -