回溯法解决“八皇后”问题

回溯法定义：

从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到" 尽头 "的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断" 回溯 "寻找解的方法，称作" 回溯法 "。

八皇后问题：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

C语言编程解法：

//by Robin @ http://spdf.sinaapp.com/
#include "stdafx.h"
/*********************************
	Ｃ编译器 中应引用以下头文件
	#include 
	#include 
	#include 
**********************************/
 
//为棋盘宽度,最大可定义到28
#define max 8

//控制输出解得个数，0为输出全部解
#define Ctrl 0

//建立辨识棋盘的数组，值为该行中皇后的位置
int queen[max];

//解的标号
int sum = 1;
 
//输出棋盘布局
void show(void)
{
    printf("第%d种解法n", sum);
    int i;
    for(i = 0; i < max; i++)
    {
        for(int j = 0; j < max; j++)
        {
            if(queen[i] == j)
	        printf("O ");
	    else
		printf("- ");
	} 
        printf("n");
    }
    printf("n");
    sum++;
}
 
//检查当前位置能否放置皇后 不能则 return 0
int check(int n)
{
    int i;
    for(i = 0; i < n; i++) { if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i)) { return 0; } } return 1; } //回溯放置棋子 int putPiece(int n) { #if Ctrl if(sum > Ctrl)
	return 0;
#endif
    int i;
    for(i = 0; i < max; i++)
    {       
        queen[n] = i;
        if(check(n)/*横竖斜均无其他王后棋子*/)
        {
            if(n != max - 1)
            {
		putPiece(n + 1);
            }         
            else
            {
                //如果全部摆好，则输出所有皇后的坐标
                show();
            }
        }
    }
    //如果没有可以放置皇后的位置，该树枝被剪除
    return 0;
}
 
int main()
{
    putPiece(0);
    return 0;
}