人工智能的示例——八皇后问题
人工智能的一类应用问题是搜索问题。其中的一个实例就是有名的数学问题，它是八皇后问题。
它是一个有历史渊源的著名问题，许多的大数学家研究过它。
在网上千篇一律的文章中说，一百多年前，没有计算机时，有人曾用图论的方式求出了全部的92个解。
但是没有找到具体的做法。本文中，猜测性地讨论一下，古人可能用的人工构造法。
总结人工法为两个步骤，在低阶时，采用马跳棋盘的方法直接构造出来结果，例如4阶的情况。再逐一升阶，采用
数学归纳法，总结出构造的规律，再推广采用到更高阶的构造中去。
在计算机程序的解决方式中，我提到的是在全排列的基础上的筛法求解。可以保证在解空间比较小的
情况下，实现高效率。
1 普通做法
穷举法是最暴力的做法，纯靠计算机的强大的计算力解决问题。有人证明多皇后的问题是NP问题。
它的算法复杂度是指数级的。回溯法是在穷举法的基础上，进行优化，消除了许多不可能的搜索空间的部分。
2人工构建法
采用数学归纳法从低阶到高阶依次构造。
1 个皇后的问题是不用说的。2，3个皇后时是无解的。4个皇后的时候，采用马踏棋盘的方法，得到两个解。
在得到一个解的情况下，可以通过几何变换的方法得到其它的解。变换有90，180，270度的旋转变换。
上下对称变换，左右对称变换，以对角线为轴的变换。
几何变换的性质有：
1 皇后的位置关系不变，相邻的关系仍然是相邻的关系，相攻击的位置关系，还是相互攻击的位置关系。
2 在八皇后的的棋盘上形成了从内向到外的四层回路，在变换的过程中，一个位置变换到新的位置后，它所属的
回路的编号是保持不变的。
棋盘上的每个位置的皇后都控制行和列的7个位置，但是它能控制的斜行的位置的数量是不同的。第一回路控制的斜行的
位置有13个，第2回路是11个，第3回路是9，第4回路是7。
这意味着一个人工构造时的放置皇后的位置的技巧。皇后优先放在外侧的回路上，最好空出中心地带。这样冲突的可能性更小。
等价类的概念定义
能通过各种几何变换后，从一个解得到的其它的新解，这些解，它们处在一个等价类中。
一个等价类中可能有2或者4或者是8个解。解的多少取决于解的旋转性的对称性。
为什么要判断解的等价类的情况？
是为了判断目前构造出的几个解能够通过变换生成多少个新的解，例如，有3个解在同一个等价类中，
可能再生成1或者是5个新的解。如果3个解在三个等价类中，最多还可以生成21个新的解。在构造新解的过程中
发现新的等价类中的解是很重要的，如果构造的解，属于原来的等价类，意味着构造解的工作无进展。
如何判断两个解是否在同一个等价类中呢？也就是如何对一个等价类进行标识呢？
根据前面介绍的几何变换的两个性质，也就是两个在变换中的不变量，得到对等价类的特征分类的两种方法。
1马跳法分类
如果两个皇后位置关系为日字形，即中国象棋中，马跳一步的位置，则两个皇后用线连结，否则不连结。
还样的话，八个皇后的结点，形成了几个子图，记录每个子图的皇后数，数量从大到小排序，例如记号（3，2，2，1）
表示形成了4个子图，每个子图中的皇后数分别为3，2，2，1。
2 回路法分类
统计第1回路到第4回路中，每个回路的皇后数。例如记号【1，0，3，4】表示第一回路有1个皇后，第2回路没有。
如果两个解的两种分类法的记号组成的标识符完全一致，那么它们很可能是在一个等价类中，否则
它们一定不是在同一个等价类中。
构造技巧有优先尝试把新的行列放在原来的低阶棋盘的外围处。新的皇后必须斜向穿过原来的棋盘的斜向的空白通道。
人工构造的优势在于极大程度上减少了多余的计算量，使之能在人脑可控的计算量内完成。
缺点在于技巧性太强，不利于程序化，不容易编程，而且不能保证得到全部解。为了证明是全部解，就退化为穷举遍历了。
八皇后问题的程序化解决方法
不利用约束条件的遍历，搜索空间大小为8的8次幂，大小为1600多万种可能的排查。利用上行列不得冲突的约束条件，转化为1到8的8个数字的全排列的问题，搜索空间的大小为8的阶乘，大小为4万多种可能性的排查。
把棋盘上的皇后位置的几何布局转化为计算机的数据结构为一个数组，例如【1，2，3，4，5，6，7，8】
它的含义是表示数组的第一个元素为棋盘上第一列的皇后的情况，数组中元素的数值表示皇后所在的行。
在全排列中，1到8，各出现一次，这样可以保证，每个皇后独占一个列，也独占一个行。这是满足行与列各自不冲突的约束条件。只采用列交换的方式，可以减少直到消除对角线与斜行的冲突。
这样所有的棋局对应于1到8的全排列。
程序设计的思路是分为两个部分，第一个部分是全排列的生成过程，利用检查子程序，筛掉不合格的排列。
第二个部分是检查斜行冲突的子程序。它是一个两重循环的检查 。一旦发现两个皇后的列号的差等于行号的差的绝对值，
即停止检查 ，判为不合格。
详细细节见如下的javascript的源代码。
<html>
<head>
<title>
八皇后问题
</title>
</head>
<body οnkeyup="whichButton(event)">
<textarea id='txt2' rows="20" cols="80"></textarea>
<input type=button οnclick="test()" value="get_token">click me</input>
<script>
function test()
{
var list_str= full_permutation([1,2,3,4,5,6,7,8],0,[]);
document.getElementById("txt2").innerText=list_str;
//test_dagon([1,2,3]);
}
count=0;
function full_permutation(str,start,results) {
var res= new Array(0);
if (start == str.length - 1) {
if(test_dagon(str)==1)
{ count++;
console.log("[num]="+count+"[str]"+str);
}
} else if (start < str.length - 1){
for (var i = start; i < str.length; i++) {
//从下标为start的数开始，分别与它后面的数字交换
var k=i;
str=swap(str,start,k);
res=full_permutation(str,start +1,results);
str=swap(str,start,k);
}
}
return res;
}
function swap(str,start,i)
{
var res=str;
var t=res[start];
res[start]=res[i];
res[i]=t;
return res;
}
function test_dagon(arr)
{
var result=1;
for(var i=0;i<arr.length-1;i++)
for(var j=i+1;j<arr.length;j++)
{
var distance=Math.abs(arr[i]-arr[j]);
if(distance==j-i)
return 0;
}
return result;
}
</script>
</body>
</html>
六皇后的问题结果如下：
八皇后问题的部分解的数组形式如下：
