回溯法-八皇后问题

本例以八皇后为例，可推广位n皇后
解向量 s{s0,s1,s2,s3,s4,s5,s6,s7}
显示约束 0=<s[i]<8
隐式约束 各元素不能相等，且s[index]-s[i]!=index-i,注意取绝对值
树。。表示不知道用什么工具画。八叉树，回溯时候注意条件判断
递归出口，当第八个棋子成功放下。
思路：
回溯是优化的穷举。。肯定要遍历所有值，for（int i;i<s.length;i++）
每放一枚棋子的处理情况都相同，判断是否可以放下（显示约束，隐式约束条件）
另外。。八皇后问题，因为棋盘是正方形，实际求出23个解其他对称就可得到全部的92个解。不过代码上进行动态优化有点麻烦。。回溯熟练再研究，晾着

package cn.edu.cqupt.huisu;

public class Queen {
private int num;
private int s[] = null;
private int count ;
public Queen(int count)
{
this.count= count;
s=new int[count];
for(int i=0;i<count;i++)
{
s[i]=-1;
}
}
public void queen(int n)
{
if(n==count)
{
num++;
printResult();
return ;
}
for(int i=0;i<count;i++)
{
s[n]=i;
if(isFit(n))
queen(n+1);
}
}

public boolean isFit(int index)
{
for(int i=0;i<index;i++)
{
if(s[i]==s[index])
return false;
if(Math.abs(s[index]-s[i])==index-i)
return false;
}
return true;
}
public void printResult()
{
System.out.print("num "+num+" :");
for(int i =0; i<s.length;i++)
System.out.print(s[i]+"\t");
System.out.println();
}
public static void main(String args[])
{
Queen q =new Queen(4);
q.queen(0);
}
}