package com.iflytek.nqueue;


import java.util.ArrayList;
import java.util.List;


public class NQueueProblem {
private int N;
private int solutionNum = 0;
public NQueueProblem(int N){
this.N = N;
}

public void solve(){
@SuppressWarnings("unused")
Node node = new Node(-1, N);
func(node);
}
private void func(Node node){
//递归出口
if(node.floor == N - 1){
System.out.println("solution" + ++this.solutionNum);
node.printf();
}

//根据限界函数选取下一层节点
List nodes = this.constraint(node);
for(Node nextNode :nodes){
func(nextNode);
}
}

public List constraint(Node node) {
List nodes = new ArrayList();
int[] usedColumn = new int[N];
if (node.floor != -1) {
for (int i = 0; i <= node.floor; i++) {
// 本列
usedColumn[node.flag[i]] = 1;
// 左对角线
int x = node.flag[i] - (node.floor + 1 - i);
int y = node.floor + 1;
if (x >= 0 && y <= N - 1) {
usedColumn[x] = 1;
}
// 右对角线
x = node.flag[i] + (node.floor + 1 - i);
y = node.floor + 1;
if (x <= N - 1 && y <= N - 1) {
usedColumn[x] = 1;
}
}
}
for (int i = 0; i < N; i++) {
if (usedColumn[i] == 0) {
Node newNode = node.deepCopy();
newNode.floor++;
newNode.flag[node.floor + 1] = i;
nodes.add(newNode);
}
}
return nodes;
}

public static void main(String[] args){
new NQueueProblem(8).solve();
}
}


package com.iflytek.nqueue;


public class Node {
public int floor; 
public int[] flag;
private int N;
public Node(int floor, int N){
this.floor = floor;
this.N = N;
this.flag = new int[N];
}

public Node deepCopy(){
Node node = new Node(this.floor, this.N);
for(int i = 0; i < this.N; i++)
node.flag[i] = this.flag[i];
return node;
}


public void printf(){
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~");
for(int i = 0; i < N; i++)
System.out.println(i + " " + flag[i]);
}
}