java实现N皇后问题 - JAVA

N皇后问题描述：
将 n 个皇后摆放在一个 n x n 的棋盘上，使得每一个皇后都无法攻击到其他皇后。
深度优先遍历的典型案例。

程序输入：
n的个数(需>4)
棋盘上任意一个位置
程序输出：
满足问题需求的棋盘坐标

程序代码如下：
Node类用于封装皇后的棋盘位置信息
[java]
public class Node {
private int x;
private int y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
@Override
public String toString() {
return "(" + x + "," + y + ")";
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
}
Searcher类用于查询指定起始位置的N皇后坐标
[java]
public class Searcher {
private int num=0;
public Searcher(int num){
this.num=num;
}
public List search(Node node){
List solution=new ArrayList();
if(qualified(node,solution)){
return solution;
}else{

return null;
}
}
/**
* 先序遍历
*/
private boolean qualified(Node node,List solution){
if(attach(node,solution)){
return false;
}
solution.add(node);
if(solution.size()==num){//是否是最后一个节点
return true;
}
//获取node的子节点
boolean res=false;
for(Node child:obtainChild(node)){
if(qualified(child,solution)){
res=true;
break;
}
}
if(!res){
solution.remove(node);
}
return res;
}
private List obtainChild(Node node) {
List res=new ArrayList();
for(int i=0;i if(i==node.getX()){//过滤同一行
continue;
}
for(int j=0;j if(j==node.getY()){//过滤同一列
continue;
}
if(Math.abs(node.getX()-i)==Math.abs(node.getY()-j)){//过滤对角线;
continue;
}
res.add(new Node(i,j));
}
}
return res;
}
private boolean attach(Node node,List nodes){
if(nodes.size()==0){//跳过首节点
return false;
}
for(Node tempNode:nodes){
if(node.getX()==tempNode.getX() ||//同一行
node.getY()==tempNode.getY() ||//同一列
Math.abs(node.getX()-tempNode.getX())==Math.abs(node.getY()-tempNode.getY())){//对角线
return true;
}
}
return false;
}
} www.2cto.com
Main类用于编码测试
[java]
public class Main {
public static void main(String[] args) {
Searcher searcher=new Searcher(6);
List res=searcher.search(new Node(2,0));
System.out.println(res);
}
}
打印输出:[(2,0), (0,4), (1,2), (3,5), (

java实现N皇后问题(一)