一、问题

一个 8×8 的棋盘，希望往里放 8 个棋子，每个棋所在的行、列、对角线上都不能有其他棋子。找出所有满足要求的布局。

二、分析与解

首先画出下面这样一个棋盘：

行、列的下标都是从 0 开始。

逐行摆放棋子，比如当前要摆放第 R 行的棋子时，认为 0 至 R-1 行的棋子是符合要求的，那么对于第 R 行，尝试把棋子摆放到第 C 列，检测是否满足要求，如果满足则继续下一行摆放下一行，不满足则则尝试放至 C+1 列。如果摆放到了第 8 行，则认为得到了一个解。

检测算法：从上图可以看出，只需要检查三种场景，对于位置(row, col)：

1. 左下对角线；该对角线上的点符合 col >= 0 && (row--, col--)。
2. 垂直列；(row–, col)， 行 渐减，列不变。
3. 右下对角线。该对角线上的点符合 col < 8 && (row--, col++)。

三、解法一

以一个二维数组作为棋盘，摆放有棋子的位置设为 1，没有的为 0 。

import java.util.Arrays;

public class NQueen {
    private final int[][] arr;
    private final int num;
    private int resultCount = 0; // 解空间数量

    public NQueen(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("n < 1");
        }
        num = n;
        arr = new int[num][num];
    }

    public void play() {
        // 从第 0 行开始摆放
        run(0);
    }

    /**
     * 以 行 为步骤，逐行放置棋子。
     *
     * @param row
     */
    private void run(int row) {
        if (row == 8) {
            resultCount++;
            print();
            return;
        }

        for (int c = 0; c < num; c++) {
            // 对于给定的行，遍历所有的列，如果行、列组合满足则进入下一行。
            if (isValid(row, c)) {
                arr[row][c] = 1;
                run(row + 1);

                // 回溯到当前行，继续下一列
                arr[row][c] = 0;
            }
        }
    }

    private boolean isValid(int row, int col) {
        int leftDown = col - 1;
        int rightDown = col + 1;

        for (int r = row - 1; r >= 0; r--) {
            if (arr[r][col] == 1) { // 检测列上是否有
                return false;
            }

            if (leftDown >= 0 && arr[r][leftDown] == 1) { // 检测左下对角线
                return false;
            }

            if (rightDown < num && arr[r][rightDown] == 1) { // 检测右下对角线
                return false;
            }

            leftDown--;
            rightDown++;
        }

        return true;
    }

    private void print() {
        System.out.println("第 " + resultCount + " 个解");
        for (int r = 0; r < arr.length; r++) {
            String s = Arrays.toString(arr[r]);
            System.out.println(s.substring(1, s.length() - 1).replaceAll(",", ""));
        }
    }

}

输出的第一个解如图：

四、解法二

这个解法来自极客时间专栏《数据结构与算法之美》。

从解法一的输出结果可以看到，二维数组里基本全是 0，同一行只有一个列上有值，因此我们可以用一维数组来表示行，用数组元素的值表示把棋子放到哪一列。比如 arr[1] = 3 表示第 1 行、第 3 列上放棋子。

代码如下：

public class GeekTimeNQueen {
    private int num;
    private int[] arr;
    private int resultCount;

    public GeekTimeNQueen(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("n < 1");
        }
        num = n;
        arr = new int[num];
    }

    public void play(){
        run(0);
    }

    private void run(int row) {
        if (row == num) {
            resultCount++;
            print();
            return;
        }

        for (int c = 0; c < num; c++) {
            if(isValid(row, c)) {
                arr[row] = c;
                run(row + 1);
            }
        }
    }

    private boolean isValid(int row, int col) {
        int leftDown = col - 1;
        int rightDown = col + 1;

        for(int r = row - 1; r >= 0; r--) {
            if (arr[r] == col) { // 检测垂直列
                return false;
            }

            if (leftDown >= 0 && arr[r] == leftDown) { // 检测左下
                return false;
            }

            if (rightDown < num && arr[r] == rightDown) { // 检测右下
                return false;
            }

            leftDown--;
            rightDown++;
        }

        return true;
    }

    private void print() {
        System.out.println("第 " + resultCount + " 个解");
        for (int r = 0; r < num; r++) {
            for (int c = 0; c < num; c++) {
                if (arr[r] == c) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

}

欢迎关注我的微信公众号: coderbee笔记，可以更及时回复你的讨论。