1 八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有 76种方案。1854年在柏林的象棋杂志上不同的作者发表了 40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种方法可以解决此问题。 下面本人所用的就是回溯的思想来解决八皇后问题的。8行8列的棋盘上放八个皇后,且不相互攻击, 即每一列每一行只能放一个皇后,且必须要放一个皇后。采用循环回溯的方法,现在第一列放一个皇后,然后再在第二列放一个皇后,以此类推,直到八个皇后都放完为止。每个for循环语句都有一条 continue语句,用来继续跳出本次循环。 // Queen.cpp(main) #include using std::cout; using std::endl; #include using std::setw; 2 #include // using std::abs; int main() { static int queen[9]; static int count=1; for (int A=1;A<=8;A++) { for (int B=1;B<=8;B++) { if (B==A) { continue; } queen[2]=B; if ((abs(B-A))==1) { continue; 3 } queen[1]=A; for (int C=1;C<=8;C++) { if ((C==B) || (C==A)) { continue; } if ((abs(C-B)==1)||(abs(C-A)==2)) { continue; } queen[3]=C; for (int D=1;D<=8;D++) { if ((D==C)||(D==B)||(D==A)) { continue; } 4 if ((abs(D-C)==1)||(abs(D-B)==2)||(abs(D-A)==3)) { continue; } queen[4]=D; for (int E=1;E<=8;E++) { if ((E==D)||(E==C)||(E==B)||(E==A)) { continue; } if ((abs(E-D)==1)||(abs(E-C)==2)||(abs(E-B)==3)||(abs(E-A)==4)) { continue; } queen[5]=E; for (int F=1;F<=8;F++) { if ((F==E)||(F==D)||(F==C)||(F==B)||(F==A)) 5 { continue; } if ((abs(F-E)==1)||(abs(F-D)==2)||(abs(F-C)==3)||(abs(F-B)==4)||(abs(F-A)==5)) { continue; } queen[6]=F; for (int G=1;G<=8;G++) { if ((G==F)||(G==E)||(G==D)||(G==C)||(G==B)||(G==A)) { continue; } if ((abs(G-F)==1)||(abs(G-E)==2)||(abs(G-D)==3)||(abs(G-C)==4)||(abs(G-B)==5)||(abs(G-A)==6)) 6 { continue; } queen[7]=G; for (int I=1;I<=8;I++) { if ((I==G)||(I==F)||(I==E)||(I==D)||(I==C)||(I==B)||(I==A)) { continue; } if ((abs(I-G)==1)||(abs(I-F)==2)||(abs(I-E)==3)||(abs(I-D)==4)||(abs(I-C)==5) ||(abs(I-B)==6)||(abs(I-A)==7)) { continue; } queen[8]=I; cout<<" NO."<