题解 | #牛吃草问题#

知识点：回溯

这道题是经典的N皇后问题，每个皇后不能出现在同一行，同一列，同一对角线上。我们遍历每一行，同时，记录已经存在皇后的其他列与两个对角线，如果满足放置条件，则可以放置，并且在列和两个对角线中记录下来，防止后续皇后冲突，当可以放置下n个皇后时，即可计数加一，回溯遍历其他的条件，直至尝试过所有的条件。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    private int n;
    private Set<Integer> col = new HashSet<>();
    private Set<Integer> diag1 = new HashSet<>();
    private Set<Integer> diag2 = new HashSet<>();

    private int count = 0;

    public int totalNCow (int n) {
        // write code here
        this.n = n;
        backTracking(0);
        return count;
    }

    private void backTracking(int row) {
        if(row == n) {
            count++;
            return;
        }
        for(int i = 0; i < n; i++) {
            int d1 = i - row;
            int d2 = i + row;
            if(col.contains(i) || diag1.contains(d1) || diag2.contains(d2)) {
                continue;
            }
            col.add(i);
            diag1.add(d1);
            diag2.add(d2);
            backTracking(row + 1);
            col.remove(i);
            diag1.remove(d1);
            diag2.remove(d2);
        }
    }
}