[算法学习]8皇后问题

算法

问题描述： 国际象棋的“8皇后问题”：在8x8的国际象棋上摆放8个皇后，使其不能互相攻击，即8个皇后中任意两个不得处在同一行、同一列或同一对角线上。共有多少种符合条件的摆法？
解法与分析：

  1. 首先是不能同一列同一行，那么每个皇后必须各独占一行一列，使用二维数组来描述就有点浪费空间了。这里我们使用一个8个元素的一维数组来表示每个皇后的每一行。
  2. 那么独占一列的情况，描述起来就像是实现{0,1,2,3,4,5,6,7}这个一维数组的全排列。
  3. 最后要解决的是不能在同一对角线的判断：假设两个数载一维数组nums位置i，j，那么i，j在同一对角线的条件是 i-j = nums[i]-nums[j] || j-i = nums[i]-nums[j]。

参考代码如下

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
/**
 * @Description: 打印所有"8皇后"的可能位置
 * @param
 * @return void
 */
public static void eightQueen()
{
    int[] queens = { 0, 1, 2, 3, 4, 5, 6, 7};
    getAllArrange(queens, 0, queens.length - 1);
}

/**
 * @Description: 数组全排列筛选
 * @param @param nums
 * @return void
 */
private static void getAllArrange(int[] nums, int start, int end)
{
    if (start > end)
    {
        System.out.println(Arrays.toString(nums));
        return;
    }
    boolean isContinue = false;
    for (int i = start; i <= end; isContinue=false,i++)
    {
        exch(nums, start, i);
        for (int a = start - 1; a >= 0; a--)
        {
            if (isDiagonal(nums, a, start))
            {
                exch(nums, start, i);
                isContinue=true;
                break;
            }
        }
        if(isContinue)
        {
            continue;
        }
        getAllArrange(nums, start + 1, end);
        exch(nums, start, i);
    }
}

/**
 *
 * @Description: 判断两个位置是否在同一对角线上
 * @param @param nums
 * @param @param i
 * @param @param j
 * @param @return
 * @return boolean
 */
private static boolean isDiagonal(int[] nums, int i, int j)
{
    int result = nums[i] - nums[j];
    return (i - j) == result || (j - i) == result;
}

/**
 *
 * @Description: 交换数组中的两个数的值
 * @param @param nums
 * @param @param i
 * @param @param j
 * @return void
 */
private static void exch(int[] nums, int i, int j)
{
    if (i == j) return;
    nums[i] ^= nums[j];
    nums[j] ^= nums[i];
    nums[i] ^= nums[j];
}