nqueentree.java

用回溯法解决N皇后问题

import java.io.*;
import java.lang.Math;
import javax.swing.*;
import javax.swing.tree.*;


public class NQueenTree extends JFrame{
	int k,n,x[],node;
	JTree tree;
	DefaultMutableTreeNode branch[];
	JScrollPane scrollPane;
	NQueenTree(int n){
	this.n=n;
	k=0;
	x=new int[n+1];
    x[0]=0;
    node=0;
	branch=new DefaultMutableTreeNode[n+1];
    branch[0]=new DefaultMutableTreeNode("0");
    tree=new JTree(branch[0]);
    JScrollPane scrollPane=new JScrollPane();
    scrollPane.setViewportView(tree);
   getContentPane().add(scrollPane);
   setVisible(true);
   pack();
    
}		
boolean PLACE(int z){
	int i=1;

	while(i<z){
		if((x[i]==x[z])||(Math.abs(x[i]-x[z])==Math.abs(i-z)))
	    return false;
	     i++;
	}
	return true;
}
void solution(){
	x[1]=0;
	k=1;
	while(k>0){
		x[k]=x[k]+1;
		while((x[k]<=n)&&!PLACE(k))
		x[k]=x[k]+1;
	
	    if(x[k]<=n)
		  {	node++;
		  	if(k==n)
		  	{branch[k]=new DefaultMutableTreeNode((char)(x[k]+48),false);
		branch[k-1].add(branch[k]);
		  		for(int i=1;i<=n;i++)
		  		System.out.print(x[i]);
		  	System.out.println();
		  	}
		  	else {
		  		
		branch[k]=new DefaultMutableTreeNode((char)(x[k]+48));
		branch[k-1].add(branch[k]);
		  		k++;x[k]=0;
		     }
	       }
	    else k--;
    }
    System.out.println("the number of created node is "+node);
    
  }	
  
 public  static void main(String args[]){
 	NQueenTree Queen=new NQueenTree(10);
 	Queen.solution();
 
 	}
 	
 }