N皇后问题

 1 import java.util.LinkedList;
 2 import java.util.Scanner;
 3 
 4 // N皇后问题
 5 public class Solution1 {
 6     public static int n;
 7     public static int cnt = 0;     // 统计组合总数
 8     public static int[] arr;       // arr[i]表示第i个皇后的列数,0表示第0个皇后
 9 
10     //  判断第k个皇后当前所在列是否和前面的皇后的位置有冲突
11     public static boolean place(int k, int col){
12         for(int i = 0; i < k; i++){
13             // 同一列或者行号之差等于列号之差则返回false
14             if(col == arr[i] || Math.abs(k - i) == Math.abs(col - arr[i]))
15                 return false;
16         }
17         return true;
18     }
19 
20     // 了利用回溯递归求解第k个皇后的位置
21     public static void FindNQueue(int k){
22         if(k == n){
23             cnt++;      // 说明找到了一组可行解
24             for(int i : arr){
25                 System.out.print(i + " ");
26             }
27             System.out.println();
28             return;
29         }
30         for(int i = 0; i < n; i++){
31             if(place(k, i)){        // 如果第k个皇后可以放在第i列
32                 arr[k] = i;         // 第k个皇后的列号为i
33                 FindNQueue(k + 1);  // 放置下一个皇后
34             }
35         }
36     }
37 
38     public static void main(String[] args) {
39         // 输入
40         Scanner in = new Scanner(System.in);
41         n = in.nextInt();
42         arr = new int[n];
43 
44         // 求解
45         FindNQueue(0);
46         System.out.println(n + "皇后问题共有" + cnt + "种可行解");
47     }
48 }

N皇后问题

原文：https://blog.51cto.com/u_14201949/2832640