算法笔记_07: 蓝桥杯练习 王、后传说

引用

1. 算法训练 王、后传说.大神用数组，用的出神入化啊。
2. 8皇后以及N皇后算法探究

---

1. 问题描述

<blockquote>
　　地球人都知道，在国际象棋中，后如同太阳，光芒四射，威风八面，它能控制横、坚、斜线位置。
　　看过清宫戏的中国人都知道，后宫乃步步惊心的险恶之地。各皇后都有自己的势力范围，但也总能找到相安无事的办法。
　　所有中国人都知道，皇权神圣，伴君如伴虎，触龙颜者死......
　　现在有一个n*n的皇宫，国王占据他所在位置及周围的共9个格子，这些格子皇后不能使用（如果国王在王宫的边上，占用的格子可能不到9个）。当然，皇后也不会攻击国王。
　　现在知道了国王的位置（x,y）（国王位于第x行第y列，x,y的起始行和列为1），请问，有多少种方案放置n个皇后，使她们不能互相攻击。
输入格式
　　一行，三个整数，皇宫的规模及表示国王的位置
输出格式
　　一个整数，表示放置n个皇后的方案数
样例输入
8 2 2
样例输出
10
数据规模和约定
　　n<=12
</blockquote>
<p>

---

2. 解决方案

<u>实现java代码</u>

import java.util.Scanner;

public class 王后传说 {
    static int n, x, y, ans;
    static int palace[][] = new int[20][20];

    static void init() {

        int i, j;
        for (i = 0; i < 20; i++) { // 初始化一个20*20的矩阵
            for (j = 0; j < 20; j++) {
                palace[i][j] = 0;
            }
        }
        for (i = x - 1; i <= x + 1; i++) { // 将国王周围的棋子置位1000000
            for (j = y - 1; j <= y + 1; j++) {
                palace[i][j] = 1000000;
            }
        }
        ans = 0;
    }

    static int judge(int row, int col) {
        int i, j;
        for (i = row - 1, j = col - 1; i >= 1 && j >= 1; i--, j--) { // 判断主对角线是否有其他皇后
            if (palace[i][j] == 1) {
                return 0;
            }
        }
        for (i = row - 1, j = col + 1; i >= 1 && j <= n; i--, j++) { // 判断负数对角线是否有其他皇后
            if (palace[i][j] == 1) {
                return 0;
            }
        }
        for (i = row - 1, j = col; i >= 1; i--) { // 判断当前列是否有其他皇后
            if (palace[i][j] == 1) {
                return 0;
            }
        }
        return 1;
    }

    static void countScheme(int r) {
        if (r > n) { // 当r=n+1时，得到一个解。
            ans++;
            return;
        }
        int i;

        for (i = 1; i <= n; i++) { // 从第一列到第n列
            if (palace[r][i] == 1000000) { // 国王的管辖范围，跳过。
                continue;
            }

            if (judge(r, i) == 1) { // 判断r行i列满足条件
                palace[r][i] = 1; // 满足，置该位置为“1”
                countScheme(r + 1); // 递归进入下一行
                palace[r][i] = 0; // 递归返回后，将r行i列置位0，再循环判断r行i+1列。
            } else { // else段，可省略。
                continue;
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        init();
        countScheme(1); // 从第一行开始
        System.out.println(ans);
    }

}

---

3. 补充： N皇后

import java.util.Scanner;

public class 皇后N {
    int[] x;
    int N;
    int sum = 0;

    public int totalNQueens(int n) {
        N = n;
        x = new int[N + 1];
        backTrace(1);
        return sum;
    }
    // col行这个点，x[col]列这个点，与已经存在的几个皇后，是否符合要求，放到这个位置上，

    private boolean place(int col) {
        for (int i = 1; i < col; i++) {
            if (Math.abs(col - i) == Math.abs(x[col] - x[i]) || x[col] == x[i]) {
                return false;
            }

        }
        return true;
    }

    private void backTrace(int t) {
        if (t > N) {
            sum++;
        } else {
            // 第t行，遍历所有的节点
            for (int j = 1; j <= N; j++) {
                x[t] = j;
                // 如果第j个节点可以放下皇后
                if (place(t)) {
                    // 接着放下一个
                    backTrace(t + 1);
                }
            }
        }

    }

    public static void main(String[] args) {
        皇后N test = new 皇后N();
        // System.out.println(n.totalNQueens(8));
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        System.out.println(test.totalNQueens(n));
    }
}