n 皇后问题

问题分析

• 在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

• x[i] 表示皇后i 放在棋盘的第i 行的第x[i] 列

  • 不能在同一行
  • 不能在同一列 x[i] 互不相同
  • 不能在同一斜线
    • 斜率为1 和值相等
    • 斜率为-1 差值相等
    • 若两个点 (i, j) (k, l), 则有
      • i - j = k - l => i - k = j - l
      • i + j = k + l => i - k = l -j
    • 即 |i - k| = |j - l| 成立即可

Java 源代码

/*
 * 若尘
 */
package nqueen;

/**
 * n 皇后问题
 * @author ruochen
 * @version 1.0
 */
public class NQueen {

	/** 皇后个数  */
	static int n;
	/** 当前解 */
	static int[] x;
	/** 当钱已找到的可行方案数 */
	static long sum; public static void main(String[] args) {
		nQueen(5);
		System.out.println("可行方案个数为： " + sum);
	} /**
	 * 初始化及返回可行解个数
	 * @return 可行解个数
	 */
	public static long nQueen(int nn) {
		n = nn;
		sum = 0;
		x = new int[n + 1];
		for (int i = 0; i <= n; i++) { // 初始化 x[i] = 0;
		}
		backTrack(1);
		return sum;
	} /**
	 * 可行性约束
	 * @param k
	 * @return 是否可行
	 */
	public static boolean place(int k) { for (int j = 1; j < k; j++) { // 对应公式 |i - k| = |j - l| && 列号不能相同  if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || x[j] == x[k]) return false;
		}
		return true;
	} /**
	 * 回溯搜索
	 * @param i
	 */
	public static void backTrack(int t) {
		if (t > n) { // 已经找到一种可行解 long temp = sum + 1; System.out.print("第" + temp + "种可行解为： "); for (int k = 1; k <= n; k++) { System.out.print(x[k] + " "); } System.out.println(); sum++;
		} else { for (int i = 1; i <= n; i++) { x[t] = i; if (place(t)) backTrack(t + 1); }
		}
	}
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
 

第1种可行解为： 1 3 5 2 4 
第2种可行解为： 1 4 2 5 3 
第3种可行解为： 2 4 1 3 5 
第4种可行解为： 2 5 3 1 4 
第5种可行解为： 3 1 4 2 5 
第6种可行解为： 3 5 2 4 1 
第7种可行解为： 4 1 3 5 2 
第8种可行解为： 4 2 5 3 1 
第9种可行解为： 5 2 4 1 3 
第10种可行解为： 5 3 1 4 2 
可行方案个数为： 10

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/106599206