📄 八個皇后.mht
字号:
From: <由 Microsoft Internet Explorer 5 保存>
Subject: =?gb2312?B?sMuCgLvKuvM=?=
Date: Wed, 13 Sep 2006 01:10:25 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
boundary="----=_NextPart_000_003B_01C6D6D1.64C48EF0";
type="text/html"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1807
This is a multi-part message in MIME format.
------=_NextPart_000_003B_01C6D6D1.64C48EF0
Content-Type: text/html;
charset="big5"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/EightQueen.htm
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>=A4K=AD=D3=AC=D3=A6Z</TITLE>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Dbig5"><LINK=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/css/stdlayout.css"=20
type=3Dtext/css rel=3Dstylesheet><LINK=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/css/print.css"=20
type=3Dtext/css rel=3Dstylesheet>
<META content=3D"MSHTML 6.00.2800.1561" name=3DGENERATOR></HEAD>
<BODY>
<H3><A=20
href=3D"http://caterpillar.onlyfun.net/Gossip/index.html">http://caterpil=
lar.onlyfun.net/Gossip/index.html</A></H3>
<H1><A=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/AlgorithmGossip.htm">Algorithm=20
Gossip: =A4K=AD=D3=AC=D3=A6Z</A></H1>
<H2> =BB=A1=A9=FA</H2>=A6=E8=ACv=B4=D1=A4=A4=AA=BA=AC=D3=A6Z=A5i=A5H=
=AA=BD=BDu=ABe=B6i=A1A=A6Y=B1=BC=B9J=A8=EC=AA=BA=A9=D2=A6=B3=B4=D1=A4l=A1=
A=A6p=AAG=B4=D1=BDL=A4W=A6=B3=A4K=AD=D3=AC=D3=A6Z=A1A=ABh=B3o=A4K=AD=D3=AC=
=D3=A6Z=A6p=A6=F3=AC=DB=A6w=B5L=A8=C6=AA=BA=A9=F1=B8m=A6b=B4=D1=BDL=A4W=A1=
A1970=A6~=BBP1971=A6~=A1A=20
E.W.Dijkstra=BBPN.Wirth=B4=BF=B8g=A5=CE=B3o=AD=D3=B0=DD=C3D=A8=D3=C1=BF=B8=
=D1=B5{=A6=A1=B3]=ADp=A4=A7=A7=DE=A5=A9=A1C<BR>
<H2>=B8=D1=AAk</H2>=C3=F6=A9=F3=B4=D1=BDL=AA=BA=B0=DD=C3D=A1A=B3=A3=A5i=A5=
H=A5=CE=BB=BC=B0j=A8D=B8=D1=A1A=B5M=A6=D3=A6p=A6=F3=B4=EE=A4=D6=BB=BC=B0j=
=AA=BA=A6=B8=BC=C6=A1H=A6b=A4K=AD=D3=AC=D3=A6Z=AA=BA=B0=DD=C3D=A4=A4=A1A=A4=
=A3=A5=B2=ADn=A9=D2=A6=B3=AA=BA=AE=E6=A4l=B3=A3=C0=CB=ACd=B9L=A1A=A8=D2=A6=
p=ADY=ACY=A6C=C0=CB=ACd=B9L=A1A=B8=D3=B8=D3=A6C=AA=BA=A8=E4=A5=A6=AE=E6=A4=
l=B4N=A4=A3=A5=CE=A6A=C0=CB=ACd=A4F=A1A=B3o=AD=D3=A4=E8=AAk=BA=D9=AC=B0=A4=
=C0=A4=E4=AD=D7=B0=C5=A1C=20
<BR>
<DIV style=3D"TEXT-ALIGN: center"><IMG title=3D=A4K=AD=D3=AC=D3=A6Z=20
style=3D"WIDTH: 169px; HEIGHT: 167px" alt=3D=A4K=AD=D3=AC=D3=A6Z=20
src=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/=
images/eightQueen-1.jpg"><BR><BR><BR>=A9=D2=A5H=C0=CB=ACd=AE=C9=A1A=A5=FD=
=A7P=C2_=ACO=A7_=A6b=A4w=A9=F1=B8m=AC=D3=A6Z=AA=BA=A5i=A6=E6=B6i=A4=E8=A6=
V=A4W=A1A=A6p=AAG=A8S=A6=B3=A6A=A6=E6=A9=F1=B8m=A4U=A4@=AD=D3=AC=D3=A6Z=A1=
A=A6p=A6=B9=B4N=A5i=A4j=A4j=B4=EE=A4=D6=BB=BC=B0j=AA=BA=A6=B8=BC=C6=A1A=A8=
=D2=A6p=A5H=A4U=AC=B0=AD=D7=B0=C5=B9L=AB=E1=AA=BA=BB=BC=B0j=C0=CB=ACd=A6=E6=
=B6i=B8=F4=AE|=A1G<BR><IMG=20
title=3D=A4K=AD=D3=AC=D3=A6Z style=3D"WIDTH: 517px; HEIGHT: 229px" =
alt=3D=A4K=AD=D3=AC=D3=A6Z=20
src=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/=
images/eightQueen-2.jpg"><BR>
<DIV=20
style=3D"TEXT-ALIGN: =
left"><BR>=A4K=AD=D3=AC=D3=A6Z=AA=BA=B8=DC=A1A=B7|=A6=B392=AD=D3=B8=D1=B5=
=AA=A1A=A6p=AAG=A6=D2=BC{=B4=D1=BDL=AA=BA=B1=DB=C2=E0=A1A=ABh=B1=DB=C2=E0=
=AB=E1=A6=A9=A5h=B9=EF=BA=D9=AA=BA=A1A=B7|=A6=B312=B2=D5=B0=F2=A5=BB=B8=D1=
=A1C </DIV></DIV><BR>
<H2>=B9=EA=A7@</H2>
<UL>
<LI>C </LI></UL><PRE>#include <stdio.h> <BR>#include =
<stdlib.h> <BR>#define N 8 <BR><BR>int column[N+1]; // =
=A6P=C4=E6=ACO=A7_=A6=B3=AC=D3=A6Z=A1A1=AA=ED=A5=DC=A6=B3 <BR>int =
rup[2*N+1]; // =A5k=A4W=A6=DC=A5=AA=A4U=ACO=A7_=A6=B3=AC=D3=A6Z <BR>int =
lup[2*N+1]; // =A5=AA=A4W=A6=DC=A5k=A4U=ACO=A7_=A6=B3=AC=D3=A6Z <BR>int =
queen[N+1] =3D {0}; <BR>int num; // =B8=D1=B5=AA=BDs=B8=B9 <BR><BR>void =
backtrack(int); // =BB=BC=B0j=A8D=B8=D1 <BR><BR>int main(void) { <BR> =
int i; <BR> num =3D 0; <BR><BR> for(i =3D 1; i <=3D N; i++) =
<BR> column[i] =3D 1; <BR><BR> for(i =3D 1; i <=3D 2*N; =
i++) <BR> rup[i] =3D lup[i] =3D 1; <BR><BR> backtrack(1); =
<BR><BR> return 0; <BR>} <BR><BR>void showAnswer() {<BR> int x, =
y;<BR> printf("\n=B8=D1=B5=AA %d\n", ++num);<BR> for(y =3D 1; y =
<=3D N; y++) {<BR> for(x =3D 1; x <=3D N; x++) {<BR> =
if(queen[y] =3D=3D x) {<BR> printf(" Q");<BR> =
}<BR> else {<BR> printf(" .");<BR> =
}<BR> }<BR> printf("\n");<BR> }<BR>}<BR><BR>void =
backtrack(int i) { <BR> int j;<BR><BR> if(i > N) { <BR> =
showAnswer();<BR> } <BR> else { <BR> for(j =3D 1; j <=3D =
N; j++) { <BR> if(column[j] =3D=3D 1 && <BR> =
rup[i+j] =3D=3D 1 && lup[i-j+N] =3D=3D 1) { <BR> =
queen[i] =3D j; <BR> // =
=B3]=A9w=AC=B0=A6=FB=A5=CE<BR> column[j] =3D rup[i+j] =3D =
lup[i-j+N] =3D 0; <BR> backtrack(i+1); <BR> =
column[j] =3D rup[i+j] =3D lup[i-j+N] =3D 1; <BR> } <BR> =
} <BR> } <BR>} <BR></PRE><BR>
<UL>
<LI>Java </LI></UL><PRE>public class Queen {<BR> // =
=A6P=C4=E6=ACO=A7_=A6=B3=AC=D3=A6Z=A1A1=AA=ED=A5=DC=A6=B3 <BR> =
private int[] column;<BR> // =
=A5k=A4W=A6=DC=A5=AA=A4U=ACO=A7_=A6=B3=AC=D3=A6Z<BR> private int[] =
rup; <BR> // =A5=AA=A4W=A6=DC=A5k=A4U=ACO=A7_=A6=B3=AC=D3=A6Z<BR> =
private int[] lup;<BR> // =B8=D1=B5=AA<BR> private int[] =
queen;<BR> <BR> // =B8=D1=B5=AA=BDs=B8=B9<BR> private int =
num;<BR> <BR> public Queen() {<BR> column =3D new =
int[8+1];<BR> rup =3D new int[2*8+1];<BR> lup =3D new =
int[2*8+1];<BR> <BR> for(int i =3D 1; i <=3D 8; i++) =
<BR> column[i] =3D 1; <BR><BR> for(int i =3D 1; i =
<=3D 2*8; i++) <BR> rup[i] =3D lup[i] =3D 1; <BR> =
<BR> queen =3D new int[8+1];<BR> }<BR> <BR> public void =
backtrack(int i) {<BR> if(i > 8) { <BR> =
showAnswer();<BR> } <BR> else { <BR> for(int j =
=3D 1; j <=3D 8; j++) { <BR> if(column[j] =3D=3D 1 =
&& <BR> rup[i+j] =3D=3D 1 && <BR> =
lup[i-j+8] =3D=3D 1) { <BR> queen[i] =3D =
j; <BR> // =B3]=A9w=AC=B0=A6=FB=A5=CE<BR> =
column[j] =3D rup[i+j] =3D lup[i-j+8] =3D 0; <BR> =
backtrack(i+1); <BR> column[j] =3D rup[i+j] =3D =
lup[i-j+8] =3D 1; <BR> } <BR> } <BR> } =
<BR> }<BR> <BR> protected void showAnswer() {<BR> =
num++;<BR> System.out.println("\n=B8=D1=B5=AA " + num);<BR> =
for(int y =3D 1; y <=3D 8; y++) {<BR> for(int x =3D 1; x =
<=3D 8; x++) {<BR> if(queen[y] =3D=3D x) {<BR> =
System.out.print(" Q");<BR> }<BR> =
else {<BR> System.out.print(" .");<BR> =
}<BR> }<BR> System.out.println();<BR> =
}<BR> }<BR> <BR> public static void main(String[] args) {<BR> =
Queen queen =3D new Queen();<BR> queen.backtrack(1);<BR> =
}<BR>} </PRE><BR><BR><BR></BODY></HTML>
------=_NextPart_000_003B_01C6D6D1.64C48EF0
Content-Type: image/jpeg
Content-Transfer-Encoding: base64
Content-Location: http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/images/eightQueen-1.jpg
/9j/4AAQSkZJRgABAgAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0a
HBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIy
MjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCACnAKkDASIA
AhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQA
AAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3
ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWm
p6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEA
AwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSEx
BhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElK
U1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3
uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD1zWr7
Vx4h0/StLuLK3+0WtxcySXVs8/8Aq2hUKAsiYz5pyST0FcfdeONeN4tvper6JqXJDyR6XMiZBxhT
9oO76jjpjNS/Fi8nsk823fY50e8jJwD8r3FkjDn/AGWI/GvOfCGsRWVzG0gQKv8AeruwVCFW/MeT
muKrUY2pbnr9he+Kb35W1bSIZgu4q2jykcYzhvtOMc+x9ql0KfxhrXh/TdV/tfQ4fttrFceV/ZEz
bN6htuftIzjOM4FUn8Q2V3c2C20yCU3EY+Q4PJA6+/Sl8GXPilPA3h9bfR9GkgGm24jeTVpUZl8t
cEqLdgDjsCfqaxxFL2bWlrmmWYt4iD5ndrr3Nz7H4w/6Duh/+CaX/wCSqzp7jxfD4gs9K/tbRG+0
Ws9z5v8AZEw2+W8S7cfaec+bnOeNvfPGh9r8X/8AQD0L/wAHMv8A8i1h3d34p/4TrSi2jaMJxpt7
sUatKVK+Za7iW+zZBGFwMc5PIwM856ZuCz8Yf9BzQ/8AwTyn/wBuaQ2vi8HnXNDHv/Y8uP8A0qpR
eeL/APoB6H/4OZv/AJFpPtfjDPGh6Hz/ANRmX/5FoEUdCn8Ya14e03Vf7X0OA3trFceV/ZEreXvU
Ntz9pGcZx0FaH2Pxh/0HdD/8E0v/AMlVh+DLvxSPAvh8W2jaM8A022Eby6tKjMvlLglRbEA47ZP1
Nbf2vxf/ANAPQv8Awcy//ItAzn9X1zxfpXi/w7oH9o6HKdY+0/v/AOy5l8nyYw/3ftB3ZzjqMe9d
ALPxhgY1zQ/x0eb/AOSq4fxRceIz8UPArTaVpSXK/wBoeRGmpSMkmYBu3OYAVwOmFbPfFdwLzxeR
/wAgPQ//AAcy/wDyLQIPsni/P/Ic0M/9wib/AOSeKwPBOteL/GPhCx14ajodoLrzP3H9lyybdsjJ
977QM5256d63je+LgedD0T8NYlP/ALbVxXwhuPEcXwu0ZLDStJnth5+ySfU5Inb9/JnKiBwOc/xH
19qAO3+x+MP+g7of/gml/wDkqs6e48Xw+ILPSv7W0RvtFrPc+b/ZEw2+W8S7cfaec+bnOeNvfPGh
9r8X/wDQD0L/AMHMv/yLWHd3fin/AITrSi2jaMJxpt7sUatKVK+Za7iW+zZBGFwMc5PIwMgzcFn4
w/6Dmh/+CeU/+3NIbXxeDzrmhj3/ALHlx/6VUovPF/8A0A9D/wDBzN/8i0n2vxhnjQ9D5/6jMv8A
8i0CKOhT+MNa8Pabqv8Aa+hwG9tYrjyv7Ilby96htuftIzjOOgrQ+x+MP+g7of8A4Jpf/kquZ8N3
3jGH4baQ2maLo8xTSIfsvm6m4ZyIVK7k8kDJ443gf7QHNdH4SvPFF5pCv4q0uysL7n5LWcvn5m6r
yF4C9HfOedvSgBlrea9a+KrTS9UvdOuobmyuLgNa2TwMrRvCoHzSuCCJT6dK6TDf3/0rn7r/AJKD
o3/YKv8A/wBG2lb+B6CgZxviq70i28W6bFrl7aWljdaTf27tcziJX3SWuV3EjkjP5V5HfeDdHgvm
Oj+PfDL2pyV+1aiiOMk8HbkNgYOeMnsK9wvP+ShaN/2Cr/8A9G2dHiED+3PCf/YVf/0iuaunUlB3
izGrQhV+JHnHgu08O6Pfrf634z8NXMkRPkww6gjKrcYfcxHI+YY245BznGOs8GeM/C1r4G8P21x4
l0eGeLTbeOSOS/iVkYRqCCC2QQeoruiBk8Vwng2CbQvA3h++sopJtPl0y2kvLONSzIxiUtNCo5JJ
yXjH3uWUb8rK6lSVR3kwo0IUVywVkbn/AAnfhD/oa9D/APBjF/8AFVh3fjPws3jrSrhfEmjtBHpl
6jSi+iKqzSWxUE7uCQrED/ZPoa7i3nhuraK4t5Y5oJUDxyRsGV1IyCCOCCOc1iXn/JQ9G/7BV/8A
+jbSszYQeOvCHfxXof8A4MYf/iqQ+OvCJPHirQ8dz/aMP/xVdFSHrQBwngzxn4WtfA3h+3ufEujw
zxabbpJFJfRKyMI1BBBbIIPrW3/wnfhD/oa9D/8ABjF/8VS+BP8Aknnhr/sFWv8A6KWugoEeT+KP
Ffh24+KPgW8h8QaXLa2w1Dz5kvI2SLdAAu8g4XJGBk8mu2Xx14QA58VaED7ajF/8VWD4t/5K98O/
+4n/AOk616BigDnT458JE8eKdDPpnUIsf+hVxXwi8WeG9M+F2jWd94g0q1uY/P3w3F5HG65mkIyp
bIyCD+NerYGa4D4Jf8kh0L/t4/8ASiSgDf8A+E78If8AQ16H/wCDGL/4qsO78Z+Fm8daVcL4k0do
I9MvUaUX0RVWaS2KgndwSFYgf7J9DXe1z95/yUPRv+wVf/8Ao20oGIPHXhDv4r0P/wAGMP8A8VSH
x14RJ48VaHjuf7Rh/wDiq6KkPWgDhPBvjPwta+BvD9vc+JdGhni022SSKS+iVkYRqCCC2QQfWtv/
AITrwf8A9DVoX/gxh/8AiqXwJ/yTzw1/2CrX/wBFLXQUCONg17SNZ+IWmHStVsr8Q6Ve+Z9kuEl2
ZltcZ2k46HHrz6V1m4f89R/30P8ACsS8A/4WHo3H/MKv/wD0baVv0DMG8/5KHo3/AGCr/wD9G2dJ
4h/5DnhP/sKv/wCkVzWN4w/4SMeMdEPhg6X9t+wX3mf2n5nliPfa5x5fO7O38M1gayfil/afh8XR
8HCYX7/ZvL+048z7LPnfn+HZ5nT+Lb2zQB6x61geBP8Aknnhr/sFWv8A6KWudJ+LuRz4Iznt9rrJ
8J/8LT/4Q7Q/7O/4Q77D/Z8H2f7R9q8zy/LXbv28bsYzjjNAHd3EE2hXMt9YxSS6fKxku7KJSzRs
TlpoVHJJOS8Y+9yyjflZa8lxDdeOtBuLeWOaCXR7545I2DK6mWzIII4II5zWH/xd/wD6kb/ybrlL
uD4maH4uivY4fDUtxLZXUotbVbl4kUzW/nyKn395JjYqud21yFLsdwB7Z2pPWvO4J/izdW8dxbS+
BJoJVDxyRvdMrqRkEEcEEcg08n4u5GT4Iz7fa6AOi8Cf8k88Nf8AYKtf/RS10FeT+E/+Fp/8Idof
9nf8Id9h/s+D7P8AaPtXmeX5a7d+3jdjGccZrY/4u/8A9SP/AOTdAg8W/wDJXvh1/wBxP/0nWvQK
8P8AEX/Cx/8AhY3gw3v/AAi39p/6d9g8j7R5P+pHmebn5vu42475zxXX5+LxGR/wg5Hbm7oA9B71
5/8ABL/kkOhf9vH/AKUSUmfi90/4of8A8m65H4X/APCxx8OtKGg/8Ir/AGZ++8n7f9o87/XPu3bP
l+9uxjtigD2+ufvP+Sh6N/2Cr/8A9G2dc/8A8Xf/AOpH/wDJusa5PxS/4THTd/8Awh5vv7Pu/K2/
afL8vzLbfu77s+XjHGN2e1AHrPak9a8/H/C38f8AMj/+TdIT8XcjJ8EZ9vtdAzovAn/JPPDX/YKt
f/RS10FeT+E/+Fp/8Idof9nf8Id9h/s+D7P9o+1eZ5flrt37eN2MZxxmtj/i7/8A1I//AJN0COgv
P+Sh6N/2Cr//ANG2db1cBoh8X/8ACw7EeK/7Dz/ZV59m/srzf+etru3+Z/wHGPfPau/3f7LflQMw
bz/koejf9gq//wDRtnSeIf8AkOeEv+wq/wD6RXNU9e1bT9H8daLc6nf2tlA2m3yLLczLEpbzLU4y
xxnAP5Vn654x8Lz6x4ZeHxLo8iw6k7yFL6Ngi/ZLhcnDf3mUfUgd6AO87msDwJ/yTzw1/wBgq1/9
FLTf+E58JE5/4SrRMd8ahFx/49WL4M8aeFrXwN4ft7jxLo0M0Wm26SRSX8SsjCNQVILZBB4xQI7y
uevP+Sh6N/2Cr/8A9G2lL/wnfhD/AKGvQ/8AwYw//FVhXfjPwu3jnSrhfEujmFNNvUaUX8W1WaS2
KgndgE7Wx/un0NAHQXEE2hXEt9YxSS6fKxku7KJSzRsTlpoVHJJOS8Y+9yyjflZdi3nhureO5t5Y
5oZUDxyxsGV1IyCCOoIwc1hjx34Qxz4q0P8A8GEX/wAVWFc+NPC+h3Et7YeJdHlsJXMl3ZxX0TMj
HlpolDZJJJLxj73LKN+4Sgze8Cf8k88Nf9gq1/8ARS10FcH4M8aeFrXwL4et7jxLo0M8Wm2ySRyX
0SsjCJQQQWyCDxitz/hO/CH/AENeh/8Agxh/+KoEc/4t/wCSvfDr/uJ/+k616BXk3ijxZ4duPil4
Eu4df0qS1tf7Q8+ZL2MpFugULuYNhcngZxk13A8d+Ecc+KtDz/2EIv8A4qgDoO9cB8Ev+SQ6F/28
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -