/*八皇后问题的实现，回溯算法 8*8格的国际象棋， 使其不能相互攻击，即任意两个皇后不能处于同一行，同一列，或同意斜线上*/ #include <stdio.h> #include<stdlib.h> #define N 8 // 定义棋盘的格数, 通过改变,也可以是4皇后, 16皇后, 9皇后什么的. int chess[N][N] = {0}; // 棋盘 int count = 0; // 有多少种放法 int canput(int row, int col) // 确定某一格能不能放 { int i,j; for(i = 0; i < N; i ++) { if(chess[i][col] == 1) //有同列的 { return 0;//不管是主函数还是子函数，只要执行return，就会结束该函数 } for(j = 0; j < N; j++) { if(chess[row][j]==1) //有同行的 { return 0; } if(((i-row)==(j-col)||(i-row)==(col-j))&&chess[i][j]==1) // 对角线上有的 { return 0; } } } return 1; } void print_chess() // 打印放置的方案// { int i, j; for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { printf("%d ", chess[i][j]); } printf(" "); } printf(" "); } int put(int row) // 放置棋子, row是从哪一行开始, 通常是0 { int j, s; for(j = 0; j < N; j++) // 此一行的每一个格子都要试试能不能放 { if(canput(row, j)) // 假如这格能放的话 { chess[row][j] = 1; // 放置 if(row == N-1) // 已经到了最后一行, 那么肯定成功****************************************************** { count = count +1; print_chess(); chess[row][j] = 0; //成功后, 寻找下一种方法 continue; } s= put(row+1); // 放置下一行的 if(s == 0) // 假如下一行不能放 { chess[row][j] = 0; // 那么这格是放错了的, 清除 continue; // 找本行的下一个方格 } else { break; } } } if(j==N) // 如果这一行的每个空格都不能放置 { return 0; // 那么本行放置失败 } else { return 1; // 本行放置成功 } } int main()// { int s ; s = put(0); // 放置 printf("the number of put way is %d ",count); //打印信息 system("pause"); return 0; }
#include <iostream> using namespace std; #define MAX 15 char map[MAX][MAX]; int column[MAX];//标记：该行已经有皇后则为1，否则为0 int zxie[MAX];//标记：该主斜线已经有皇后则为1，否则为0 int fxie[MAX];//标记：该辅斜线已经有皇后则为1，否则为0 int N; int sum; void output() { for(int i=0;i<N;++i) { for(int j=0;j<N;++j) cout<<map[i][j]; cout<<sum; cout<<endl; } cout<<endl; } void queue8(int row)//形式参数是row行数 { for(int i=0;i<N;i++)//列 { if(column[i]==0 && zxie[i-row+N-1]==0 && fxie[i+row]==0)//不冲突 { map[row][i]='@'; column[i]=1; zxie[i-row+N-1]=1; fxie[i+row]=1; if(row<(N-1)) queue8(row+1); else { output(); sum++; } //回溯 map[row][i]='*'; column[i]=0; zxie[i-row+N-1]=0; fxie[i+row]=0; } } } int main() { while(cin>>N && N!=0) { memset(map, '*', sizeof(map)); memset(column, 0, sizeof(column)); memset(zxie, 0, sizeof(zxie)); memset(fxie, 0, sizeof(fxie)); sum=0; queue8(0); cout<<"总共有"<<sum<<"种摆法。"<<endl; } return 0; }