package com.main;
import java.util.LinkedList;
public class NoQueue {
public LinkedList<Node> getQueue(int n){
LinkedList<Node> queues = new LinkedList<Node>();
int m=0;
boolean p = true; // 是否需要向上回溯
while(m < n){
if(m == 0){
Node q= new Node(0,0);
queues.add(q);
m++;
}
if(n >0){
Node q = queues.getLast();
if(p){
p=false; // 默认没找到
for(int i=0;i<n;i++){
Node q1 = new Node(q.x+1,i);
// 比较
if(checkQueue(q1,queues)){ // 找到结果，向下一步追踪
queues.add(q1);
m++;
p=true;
break;
}
}
}else{ // 没有找到结果向上回溯
q =queues.removeLast(); // 把最后一个取出来
for(int i=q.y+1;i<n;i++){
Node q1= new Node(q.x,i);
if(checkQueue(q1,queues)){ // 找到结果，向下一步追踪
queues.addLast(q1);
p=true;
break;
}
}
if(!p){
m--;
}
}
}
}
return queues;
}
public boolean checkQueue(Node q1,LinkedList<Node> queues){
boolean b = true;
if(queues.size() == 0){
return b;
}
for(int i=0;i<queues.size();i++){
Node q = queues.get(i);
if(q1.x==q.x || q1.y==q.y || q1.x-q.x == q1.y-q.y || q1.x-q.x == -1*(q1.y-q.y)){
b=false;
break;
}
}
return b;
}
public static void main(String[] args) {
NoQueue noq = new NoQueue();
int n= 4;
LinkedList<Node> l = noq.getQueue(n);
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
Node node= l.get(i);
if(j == node.y){
System.out.print(" Q");
}else{
System.out.print(" 1");
}
}
System.out.println();
}
}
class Node {
int x;
int y;
public Node(int i,int j){
this.x=i;
this.y=j;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return x+","+y;
}
}
}
n-Queens（n皇后）问题的简单回溯的相关教程结束。
