八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。 该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

解法：回溯法

#include
     
      #include
      
       using namespace std;int n=8;int total=0;int *c=new int(n);//c[i]==j表示这个皇后处于第i行第j列 bool is_ok(int row){    for(int j=0;j!=row;j++){    	//(c[row]-c[j])/(row-j)==1||(c[row]-c[j])/(row-j)==-1		//就是数学上的斜率k=(f(x)-f(x0))/(x-x0)         if(c[row]==c[j] || row-c[row]==j-c[j] || row+c[row]==j+c[j])//同列、同副对角线、同主对角线             return false;    }    return true;}void queen(int row){//按行进行选择八皇后的位置     if(row==n){	total++;	}            else        for(int col=0;col!=n;col++){            c[row]=col;            if(is_ok(row)){                queen(row+1);//继续摆放下一行的皇后	            				}        }       }int main(){    queen(0);    cout<
      
     

维基百科的解法：

#include 
     
      #define QUEENS       8 /*皇后数量*/#define IS_OUTPUT    1 /*(IS_OUTPUT=0 or 1)，Output用于选择是否输出具体解,为1输出，为0不输出*/int A[QUEENS + 1], B[QUEENS * 3 + 1], C[QUEENS * 3 + 1], k[QUEENS + 1][QUEENS + 1];int inc, *a = A, *b = B + QUEENS, *c = C;void lay(int i) {  int j = 0, t, u;  while (++j <= QUEENS)    if (a[j] + b[j - i] + c[j + i] == 0) {      k[i][j] = a[j] = b[j - i] = c[j + i] = 1;      if (i < QUEENS) lay(i + 1);      else {        ++inc;        if (IS_OUTPUT) {          for (printf("(%d)\n", inc), u = QUEENS + 1; --u; printf("\n"))            for (t = QUEENS + 1; --t; ) k[t][u] ? printf("Q ") : printf("+ ");          printf("\n\n\n");        }      }      a[j] = b[j - i] = c[j + i] = k[i][j] = 0;    }}int main(void) {  lay(1);  printf("%d皇后共计%d个解\n", QUEENS, inc);  return 0;}　
     

回溯法（非递归）

#include
     
      #define PRINTF_IN 1 //定义是否打印，1：打印，0：不打印int queens(int Queens){    int i, k, flag, not_finish=1, count=0;    //正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素	int a[Queens+1];    //八皇后问题的皇后所在的行列位置，从1幵始算起，所以加1    i=1;    a[1]=1;  //为数组的第一个元素赋初值    printf("%d皇后的可能配置是:",Queens);    while(not_finish){  //not_finish=l:处理尚未结束        while(not_finish && i<=Queens){  //处理尚未结束且还没处理到第Queens个元素            for(flag=1,k=1; flag && k
      
       1 && a[i]==Queens)                        a[i]=1;  //当a[i]为Queens时将a[i]的值置1                    else                        if(i==1 && a[i]==Queens)                            not_finish=0;  //当第一位的值达到Queens时结束                        else                            a[i]++;  //将a[il的值取下一个值                }else if(a[i] == Queens)                    a[i]=1;                else                    a[i]++;  //将a[i]的值取下一个值            }else if(++i<=Queens)                if(a[i-1] == Queens )                    a[i]=1;  //若前一个元素的值为Queens则a[i]=l                else                    a[i] = a[i-1]+1;  //否则元素的值为前一个元素的下一个值        }        if(not_finish){            ++count;			if(PRINTF_IN){				printf((count-1)%3 ? "   [%2d]:" : "\n[%2d]:", count);								for(k=1; k<=Queens; k++) //输出结果                printf(" %d", a[k]); 			}               if(a[Queens-1]