八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）
放置第ｉ个(行)皇后的算法为：
1. int search(i) 2. { 3. int j; 4. for(第i个皇后的位置j=1;j<=8;j++) //在i行的8列中逐个去试 5. if(本行本列允许放置皇后){ 6. 放置第i个皇后; 7. 对放置位置进行标记; 8. if(i==8) 输出;//已放完 9. else search(i+1);//放置第i+1个皇后 10. 释放放置皇后的位置 进行下了一个位置尝试; 11. } 12. }
【算法分析】问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同。如下图所示：
考虑每行有且仅有一个皇后，设一维数组Ａ[1..8]表示皇后的放置：第ｉ行皇后放在第ｊ列，用Ａ[i]＝j来表示，即下标是行数，内容是列数。例如：A[3]=5就表示第3个皇后在第3行第5列上。
判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组ｂ[1..8]控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组ｃ[1..16]、ｄ[-7..7]控制同一对角线上只能有一个皇后。
如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下，要表示两个皇后i和j不在同一列或斜线上的条件可以描述为：(a[i]!=a[j])&&( abs(i-j)!=abs(a[i]-a[j]){i和j分别表示两个皇后的行号}
1. #include<iostream> 2. #include<cstdio> 3. #include<iomanip> 4. using namespace std; 5. int a[9]={0},sum=0; 6. bool b[9]={0},c[17]={0},d[17]={0}; 7. int print() 8. { 9. sum++; 10. cout<<sum<<endl; 11. for(int i=1;i<=8;i++) cout<<setw(3)<<a[i]; 12. cout<<endl; 13. } 14. int search(int i) 15. { 16. int j; 17. for(j=1;j<=8;j++){ 18. if((!b[j])&&(!c[i+j])&&(!d[i-j+7])){ 19. a[i]=j; 20. b[j]=1; 21. c[i+j]=1; 22. d[i-j+7]=1; 23. if(i==8) print(); 24. else search(i+1); 25. b[j]=0; 26. c[i+j]=0; 27. d[i-j+7]=0; 28. } 29. } 30. } 31. int main() 32. { 33. search(1); 34. return 0; 35. }
马的遍历
中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8…
【算法分析】
如图4（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：
1: （i,j）→（i+2,j+1）； (i<3,j<8)
2: （i,j）→（i+1,j+2）； (i<4,j<7)
3: （i,j）→（i-1,j+2）； (i>0,j<7)
4: （i,j）→（i-2,j+1）； (i>1,j<8)
搜索策略：
S1:Ａ[１]:=(0,0);
S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；
S3:打印路径。
1. #include<iostream> 2. #include<cstdio> 3. #include<iomanip> 4. using namespace std; 5. int a[100][3],sum=0; 6. int x[4]={2,1,-1,-2}; 7. int y[4]={1,2,2,1}; 8. int print(int ii) 9. { 10. sum++; 11. cout<<sum<<": "; 12. for(int i=1;i<ii;i++) cout<<a[i][1]<<","<<a[i][2]<<">"; 13. cout<<"4,8"<<endl; 14. } 15. int search(int i) 16. { 17. int j; 18. for(j=0;j<=3;j++){ 19. if(a[i-1][1]+x[j]>=0&&a[i-1][1]+x[j]<=4 20. &&a[i-1][2]+y[j]>=0&&a[i-1][2]+y[j]<=8){ 21. a[i][1]=a[i-1][1]+x[j]; 22. a[i][2]=a[i-1][2]+y[j]; 23. if(a[i][1]==4&&a[i][2]==8) print(i); 24. else search(i+1); 25. } 26. } 27. } 28. int main() 29. { 30. a[1][1]=0; 31. a[1][2]=0; 32. search(2); 33. return 0; 34. }
