N皇后

在一个N×N的棋盘上,放置N个皇后,皇后的攻击范围是处于相同行、相同列和同一斜线上的棋子。

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

在解这道题前,我们可以先思考一下结果的表达方式,正常我们会用二维数组来表示一个平面,但是这里每一种解我们是可以用一维数组来表示,示例八皇后:[0,6,3,5,7,1,4,2] 其中下标0~7可以表示对应1~8行,每个下标对应数字可以表示皇后所在的列数,然后将解放在一个集合中即可

正常来说我们是可以直接列出所有皇后在棋盘上的所有情况然后一一判断,但是这样做的话时间复杂度就非常高,需要使用条件来优化

首先是解决问题的大致思路 : 从棋盘上的[0][0]位置开始一个一个的放上皇后棋,一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后,而且同一斜线上是不能有多个棋子的,一一排除之后我们可以在[1][2]这个地方放上一个棋子,接下来第二行肯定是不能再放棋子,我们要在[2][i]上面试着去放棋子,假设遇到行不通的情况,我们就要回到刚才的情况,在[1][3]这个地方放上棋子,这里就能看出解决这个问题需要回溯的方式来寻找可能的解。

第二个问题是我们如何判断一条斜线上有多个棋子,首先斜线分为两种 ①从左上到右下 ②从右上到左下两种。对于①,这条斜线上的棋子可以找到它们的一个共同点:行下标-列下标 这个差值相等,那么我们只要在放棋子的时候记录这个差值,并且在之后放上棋子的时候判断该棋子的行下标-列下标的值是否已经存在,如果存在那么这个位置就不行,不存在的话再记录差值,防止后放的棋子与该棋子位于同一条斜线 ②同一,该斜线上的特征为行下标+列下标 这个值相等

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<int []> solutions = new ArrayList<int []>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }

    public void backtrack(List<int []> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            solutions.add(queens);
        } else {
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }
 
}