题解 | #牛吃草问题# Java

这个问题实际上是一个经典的问题，被称为n皇后问题。这个问题的解决方案是在n×n的棋盘上放置n个皇后，使得它们不能互相攻击。皇后可以攻击同一行、同一列或对角线上的其他皇后。这个问题可以使用回溯法来解决。

参考<https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E6%80%9D%E8%B7%AF>

public class Solution {

    public int totalNCow (int n) {
        int[] result = new int[1];
        int[] cows = new int[n];
        placeCows(cows, 0, result);
        return result[0];
    }

    private void placeCows(int[] cows, int row, int[] result) {
        if (row == cows.length) { // 结束条件
            result[0]++;
            return;
        }
        for (int col = 0; col < cows.length; col++) {
            if (isValid(cows, row, col)) {
                cows[row] = col; // 放置
                placeCows(cows, row + 1, result);
                cows[row] = -1;  // 回溯
            }
        }
    }

    private boolean isValid(int[] cows, int row, int col) {
        for (int i = 0; i < row; i++) { 
		  	//        检查列    ||  检查45°和135°
            if (cows[i] == col || Math.abs(row - i) == Math.abs(col - cows[i])) {
                return false;
            }
        }
        return true;
    }
}

我能看懂的写法

public class Solution {

    private HashMap<Integer, Boolean> cols = new HashMap<>();
    private HashMap<Integer, Boolean> bias1 = new HashMap<>();
    private HashMap<Integer, Boolean> bias2 = new HashMap<>();

    public int totalNCow (int n) {
        int[]  ans = new int[1];
        dfs(0, n, ans);
        return ans[0];
    }
    private void dfs(int i, int n, int[]  ans) {
        if (i == n) {
            ans[0]++;
            return;
        }
        for (int j = 0; j < n; j++) {
            // 结束条件
            if (cols.get(j) != null) continue;
            if (bias1.get(i - j) != null) continue;
            if (bias2.get(i + j) != null) continue;

            // 放置
            cols.put(j, true);
            bias1.put(i - j, true);
            bias2.put(i + j, true);

            dfs(i + 1, n, ans);

            // 回溯
            cols.remove(j);
            bias1.remove(i - j);
            bias2.remove(i + j);
        }
    }
}