package com.leetCode;/** * Follow up for N-Queens problem.Now, instead outputting board configurations, return the total number of distinct solutions. * @author Zealot * @date 2015年7月23日 下午6:14:49 */public class NQueensII {int[] x;//当前解 int N;//皇后个数 int sum = 0;//当前已找到的可行方案数public int totalNQueens(int n) {N = n;x = new int[N+1];backTrace(1);return sum;}/** * col行这个点，x[col]列这个点，与已经存在的几个皇后，，是否符合要求，放到这个位置上， * @param col * @return */private boolean place(int col){for(int i = 1; i < col; i++){if(Math.abs(col – i)==Math.abs(x[col]-x[i])||x[col]==x[i]){return false;}}return true;}private void backTrace(int t) {if(t>N){sum++;}else {//第t行，遍历所有的节点for(int j = 1; j <= N; j++) {x[t] = j ;//如果第j个节点可以放下皇后if(place(t)){//接着放下一个backTrace(t+1);}}}}public static void main(String[] args) {NQueensII n = new NQueensII();System.out.println(n.totalNQueens(8));}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
当你能飞的时候就不要放弃飞
