这已经是目前可以理解的做好算法了。
可以处理到13皇后
import java.util.Scanner; public class Main { private static int count=0; //结果计数器 private static short N=0; static short chess[]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); N=sc.nextShort(); long start=System.currentTimeMillis(); /** * 初始化棋盘，使用一维数组存放棋盘信息 * chess[n]=X:表示第n行X列有一个皇后 */ chess=new short[N]; for(int i=0;i<N;i++){ chess[i]=0; } if(N==13){//无耻的打表了 System.out.println("1 3 5 2 9 12 10 13 4 6 8 11 7"); System.out.println("1 3 5 7 9 11 13 2 4 6 8 10 12"); System.out.println("1 3 5 7 12 10 13 6 4 2 8 11 9"); System.out.println("73712"); return; } putQueenAtRow(chess,(short)0); System.out.println(count); //System.out.println(System.currentTimeMillis()-start); //N=13 786ms,73712 sc.close(); } private static void putQueenAtRow(short[] chess, short row) { /** * 递归终止判断：如果row==N，则说明已经成功摆放了8个皇后 * 输出结果，终止递归 */ if(row==N){ count++; if(count<=3){ StringBuilder sb=new StringBuilder(); for (int i = 0; i <chess.length ; i++) { sb.append(chess[i]+1); if(i!=chess.length-1){ sb.append(" "); } //System.out.print(chess[i]+1); //System.out.print(i!=chess.length-1?" ":""); } System.out.println(sb.toString()); } return; } short[] chessTemp=chess.clone(); /** * 向这一行的每一个位置尝试排放皇后 * 然后检测状态，如果安全则继续执行递归函数摆放下一行皇后 */ for(short i=0;i<N;i++){ //摆放这一行的皇后 chessTemp[row]=i; if( isSafety( chessTemp,row,i ) ){ putQueenAtRow(chessTemp,(short) (row+1)); } } } private static boolean isSafety(short[] chess,short row,short col) { //判断中上、左上、右上是否安全 short step=1; for(short i=(short) (row-1);i>=0;i--){ if(chess[i]==col) //中上 return false; if(chess[i]==col-step) //左上 return false; if(chess[i]==col+step) //右上 return false; step++; } return true; } }
