//指针实例搜索算法

//迷宫算法

//搜索是最长的使用深度优先搜索和广度优先搜索

//作为名称作为一个深度优先搜索，每路一直在寻找到底。

//为了防止想法，这样的数据结构

//使得每次找到思路的时候还能够退出到出发点。

//

//

//广度优先搜索

//广度优先搜索就是利用队列性质先进先出的性质,把每次的搜索结果放入队列，

//排除思路等条件

//

//回溯法

//就是枚举每一个可能的推断，假设能够就运行，不能够就返回開始的地方

//八皇后的实现：回溯法

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int a[9] = {100};

//用来存放解的个数

int count = 0;

int Place(int i, int value)

{

int j;

if(i == 1)

return 1;

for(j = 1; j < i; ++j)

{

if(a[j] == value)

return 0;

if(abs(i - j) == abs(value - a[j]))

return 0;

}

return 1;

}





void ShowResult()

{

int i, j;

for(j = 1; j <= 8; ++j)

{

for(i = 1; i < a[j]; ++i)

{

printf("* ");

}

printf("Q");

for(i = i + 1; i <= 8; ++i)

{

printf("* ");

}

printf("\n");

}

}





void Backtrack(int t)

{

int i;

if(t > 8)

{

printf("*********************");

ShowResult();

count++;

return;

}

else

{

for(i = 1; i <= 8; ++i)

{

if(Place(t, i))

{

a[t] = i;

Backtrack(t + 1);

}

}

}

}













void ShowCount()

{

printf("\n八皇后的问题共同拥有%d个解:\n", count);

}





int main()

{

Backtrack(1);

ShowCount();

return 0;





}