一 问题描述

二 算法说明

本问题为 N 皇后问题，可采用回溯法（排列树）解决。

三 代码

package com.platform.modules.alg.alglib.had2553;

public class Hdu2553 {
    private final int M = 105;
    // n表示n个皇后
    private int n;
    // x[i]表示第i个皇后放置在第i行第x[i]列
    int x[];
    // count 表示 n 皇后问题可行解的个数
    long count;

    public String output = "";

    public String cal(String input) {
        String[] line = input.split("\n");
        for (int i = 0; i < line.length; i++) {
            x = new int[M];
            n = Integer.parseInt(line[i]);
            if (n == 0) {
                break;
            }
            count = 0;
            Backtrack(1);
            output += count + "\n";
        }
        return output;
    }

    // 判断第 t 个皇后能否放置在第 i 个位置
    boolean Place(int t) {
        boolean ok = true;
        for (int j = 1; j < t; j++)   //判断该位置的皇后是否与前面t-1个已经放置的皇后冲突
        {
            // 判断列、对角线是否冲突
            if (x[t] == x[j] || t - j == Math.abs(x[t] - x[j])) {
                ok = false;
                break;
            }
        }
        return ok;
    }

    void Backtrack(int t) {
        // 如果当前位置为 n,则表示已经找到了问题的一个解
        if (t > n) {
            count++;
        } else
            // 分别判断 n 个分支,特别注意 i 不要定义为全局变量,否则递归调用有问题
            for (int i = 1; i <= n; i++) {
                x[t] = i;
                if (Place(t))
                    Backtrack(t + 1); // 如果不冲突的话进行下一行的搜索
            }
    }
}

四 测试