回溯法 n 皇后问题（Java实现）

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种可行解为： 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