import java.lang.*;import java.util.*;
class Queen { private int x; private int y; public void setX(int x){ this.x=x; } public int getX(){ return x; } public void setY(int y){ this.y=y; } public int getY(){ return y; } }
public class EightQueen { private static List<Queen> qlist = new ArrayList<Queen>(); private static List<Queen> finlist=new ArrayList<Queen>(); private static int qsize=8;
public static void main(String[] args){ long start = System.nanoTime(); backTrack(1,1); System.out.println("take time = "+(System.nanoTime()-start)); int n=0; for(int i=0;i<finlist.size();i++){ if(i%qsize==0){ System.out.print((++n)+":"); } Queen q=(Queen)finlist.get(i); System.out.print(q.getX()+","+q.getY()+" "); if((i+1)%qsize==0) System.out.println(); } } public static boolean backTrack(int i,int j){/* 回溯法解决八皇后问题*/ for(;j<=qsize;j++){ boolean good=true; Iterator<Queen> it= qlist.iterator(); while(it.hasNext()){ Queen q = (Queen)it.next(); int x=q.getX(); int y=q.getY(); if(i==x){ good=false; break; } if(j==y){ good=false; break; } if((j-y)==(i-x)||(j-y)==(x-i)){ good=false; break; } } if(good == true){ Queen queen = new Queen(); queen.setX(i); queen.setY(j); qlist.add(queen); if(i==qsize){ Iterator<Queen> its=qlist.iterator(); while(its.hasNext()){ finlist.add((Queen)its.next()); } qlist.remove(queen);//用remove(i-1)应该也行 qlist.remove(i-2); return true; } backTrack(i+1,1); } } if(i!=1){ qlist.remove(i-2); } return false; }
}
