day4 leetcode52 n皇后问题

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

问题解析

经典的递归回溯算法,尝试向下去放下一步棋,不行就回溯

代码如下:

主方法调用
arr代表对应行的几号位下了棋
eg:arr[8] = 8,代表在第8行的第8列下了棋

public int totalNQueens(int n) {
        arr = new int[n];
        max = n;
        count = 0;
        check(0);
        System.out.println(count);
        return count;
    }

递归下棋,如果n==max代表得到一次答案,如果没有走到max就进行循环判断,对当前行的每一个位置进行判断,如果这一个位置可以下棋,就递归到下一行继续判断,如果整行都不满足,就会自动回溯.

public void check(int n) {
        if (n == max) {
            count++;
            return;
        } else {
            for (int i = 0; i < max; i++) {
                arr[n] = i;
                if (judge(n)) {
                    check(n + 1);
                }
            }
        }
    }

判断

private boolean judge(int n) {
        for (int i = 0; i < n; i++) {//判断和之前的皇后是否冲突,n代表现在这行,i代表之前放好的行
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {//判断是否是同一列或者是斜线上
                return false;
            }
        }
        return true;
    }