算法总结——八皇后问题（三种解法）

#include <stdio.h>
#include <math.h>
int queenPlaces[92][8]; //存放92种皇后棋子的摆放方法
int count = 0;
int board[8][8]; //仿真棋盘
void putQueen(int ithQueen); //递归函数，每次摆好一个棋子

void main()
{
   int n, i, j;  
    for(i = 0; i < 8; i++){  // 初始化
	    for(j = 0; j < 8; j++)
	        board[i][j] = -1;
	    for(j = 0; j < 92; j++)
	        queenPlaces[j][i] = 0;
    }
    putQueen(0); //从第0个棋子开始摆放，运行的结果是将queenPlaces生成好
   scanf("%d", &n);
   for(i = 0; i < n; i++){
        int ith;
        scanf("%d", &ith);
        for(j = 0; j < 8; j++)
           printf("%d", queenPlaces[ith - 1][j]);
        printf("\n");
    }
}
void putQueen(int ithQueen){
     int i, k, r;
     if(ithQueen == 8){
	     count ++;
	     return;
     }
     for(i = 0; i < 8; i++){
         if(board[i][ithQueen] == -1){
			 //摆放皇后
             board[i][ithQueen] = ithQueen;
			 //将其后所有的摆放方法的第ith个皇后都放在i+1的位置上
			 //在i增加以后，后面的第ith个皇后摆放方法后覆盖此时的设置
		     for(k = count; k < 92; k++)
		         queenPlaces[k][ithQueen] = i + 1;
			 //设置控制范围
	         for(k = 0; k < 8; k++)
			 for(r = 0; r < 8; r++)
				 if(board[k][r] == -1 && 
					 (k == i || r == ithQueen || abs(k - i) == abs(r - ithQueen))) 
		             board[k][r] = ithQueen;
			 //向下级递归
             putQueen(ithQueen + 1);
             //回溯，撤销控制范围
             for(k = 0; k < 8; k++)
			 for(r = 0; r < 8; r++)
					 if(board[k][r] == ithQueen) board[k][r] = -1;
		 }
	 }
}

#include <stdio.h>
int  record[92][9], mark[9], count = 0; //record记录全部解，mark记录当前解；
bool range[9], line1[17], line2[17]; //分别记录列方向，45度，135度方向上被控制的情况
void tryToPut(int ); //求全部解的过程
void main()
{
	int i, testtimes, num;
	scanf("%d", &testtimes);
	
	for(i = 0; i <=8; i++)
		range[i] = true;
	for(i = 0; i < 17; i ++)
		line1[i] = line2[i] = true;

	tryToPut(1);

	while(testtimes --){
		scanf("%d", &num);
		for(i = 1; i <=8; i++)
			printf("%d", record[num - 1][i]);
		printf("\n");
	}
}

void tryToPut(int i){
    if(i > 8){ //如果最后一个皇后被放置完毕，将当前解复制到全部解中
	    for(int k = 1; k < 9; k ++) 
		    record[count][k] = mark[k];
	    count ++;
     }					
     for(int j=1; j<=8; j++){ 逐一尝试将当前皇后放置在不同列上
	     if(range[j] && line1 [i + j] && line2[i - j + 9]){ //如果与前面的不冲突，
                                               //则把当前皇后放置在当前位置
		    mark[i] = j;
		    range[j] = line1[i + j] = line2[i - j + 9] = false;
            tryToPut(i + 1);
		    range[j] = line1[i + j] = line2[i - j + 9] = true;
	    }
    }
}

#include <stdio.h>
int ans[92][8], n, b, i, j, num, hang[8];
void queen(int i){
	int j, k;
	if(i == 8){ //一组新的解产生了
		for(j = 0; j < 8; j++)  ans[num][j] = hang[j] + 1;
		num++;
		return;
	}
	for (j=0; j<8; j++){ //将当前皇后i逐一尝试放置在不同的列
        for(k=0; k<i; k++) //逐一判定i与前面的皇后是否冲突
            if( hang[k] == j || (k - i) == (hang[k] - j) || (i - k) == (hang[k] - j )) break;
		if (k == i) {  //放置i，尝试第i+1个皇后
			hang[i] = j;
			queen(i + 1);
		}
	}
}
void main( ){
	num=0;
	queen(0);
	scanf(“%d”, &n);
	for(i = 0; i < n; i++){
		scanf(“%d”, &b);
		for(j = 0; j < 8; j++)  printf(“%d”, ans[b - 1][j]);
		printf(“\n”);
	}
}