51. N皇后

https://leetcode-cn.com/problems/n-queens/

四皇后的解

n个皇后， n×n 的棋盘上根据要求

每行有且仅有一个皇后（如果有一行没有那么必有一行至少两个皇后，不符合）

递归回溯，每次尝试在一行中摆放皇后，如果不能摆放回退到上一行

有些位置没必要去尝试，比如下面这张图当第一行选择的是(0, 0) 第二行(1, 0)(1, 1)是没必要尝试的位置，直接从(1, 3)开始也就是2 3 位置

通过辅助数组我们可以快速判断这个点是否合法

右上到左下

i 行
j 列

左上到右下

i 行
j 列

/// 51. N-Queens
/// https://leetcode.com/problems/n-queens/description/
/// 时间复杂度: O(n^n)
/// 空间复杂度: O(n)
public class Solution {//行private boolean[] col;//左下 <- 右上private boolean[] dia1;//左上 -> 右下private boolean[] dia2;private ArrayList<List<String>> res;public List<List<String>> solveNQueens(int n) {res = new ArrayList<>();col = new boolean[n];//2*n-1个斜线dia1 = new boolean[2 * n - 1];dia2 = new boolean[2 * n - 1];LinkedList<Integer> row = new LinkedList<>();putQueen(n, 0, row);return res;}/*** 尝试在一个n皇后问题中, 摆放第index行的皇后位置* @param n n皇后* @param index index行* @param row 这个皇后放在这一行的哪一列*/private void putQueen(int n, int index, LinkedList<Integer> row) {if (index == n) {res.add(generateBoard(n, row));return;}for (int i = 0; i < n; i++)// 尝试将第index行的皇后摆放在第i列if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {row.addLast(i);col[i] = true;dia1[index + i] = true;dia2[index - i + n - 1] = true;putQueen(n, index + 1, row);col[i] = false;dia1[index + i] = false;dia2[index - i + n - 1] = false;row.removeLast();}}/*** 构建出这个解* @param n n皇后* @param row 每个值代表 皇后放哪一行的哪一列 （i=0 是值为 3 代码第一行的皇后在4列的位置）*/private List<String> generateBoard(int n, LinkedList<Integer> row) {//assert row.size() == n;ArrayList<String> board = new ArrayList<>();for (int i = 0; i < n; i++) {char[] charArray = new char[n];Arrays.fill(charArray, '.');charArray[row.get(i)] = 'Q';board.add(new String(charArray));}return board;}//private static void printBoard(List<String> board) {//    for (String s : board) {//        System.out.println(s);//    }//    System.out.println();//}//public static void main(String[] args) {//    int n = 4;//    List<List<String>> res = (new Solution()).solveNQueens(n);//    for (List<String> board : res) {//        printBoard(board);//    }//}
}

P1219 八皇后

https://www.luogu.org/problem/P1219

import java.util.Scanner;
public class Main {private static int counts = 0;//统计次数private static int n;private static int outputNum = 0;private static boolean[] row;//col 行private static boolean[] dia1;//左下 <- 右上private static boolean[] dia2;//左上 -> 右下public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();row = new boolean[n];dia1 = new boolean[2 * n - 1];dia2 = new boolean[2 * n - 1];int[] tempRow = new int[n];queen(0, tempRow);System.out.println(counts);input.close();}private static void queen(int index, int[] tempRow) {if (index == n) {outputNum++;counts++;//只输出前面3个if (outputNum <= 3) {for (int i = 0; i < n; i++) {//我下标是重0开始的所以这里需要+1System.out.print(tempRow[i] + 1 + " ");}System.out.println();}return;}for (int j = 0; j < n; j++) {if (!row[j] && !dia1[index + j] && !dia2[index - j + n - 1]) {tempRow[index] = j;row[j] = true;dia1[index + j] = true;dia2[index - j + n - 1] = true;queen(index + 1, tempRow);row[j] = false;dia1[index + j] = false;dia2[index - j + n - 1] = false;}}}
}

52. N皇后 II

https://leetcode-cn.com/problems/n-queens-ii/

public class Solution {//行private boolean[] col;//左下 <- 右上private boolean[] dia1;//左上 -> 右下private boolean[] dia2;private int totalCount = 0;public int totalNQueens(int n) {col = new boolean[n];//2*n-1个斜线dia1 = new boolean[2 * n - 1];dia2 = new boolean[2 * n - 1];int[] row = new int[n];putQueen(n, 0, row);return totalCount;}/*** 尝试在一个n皇后问题中, 摆放第index行的皇后位置* @param n     n皇后* @param index index行* @param row   这个皇后放在这一行的哪一列*/private void putQueen(int n, int index, int[] row) {if (index == n) {totalCount++;return;}for (int i = 0; i < n; i++)// 尝试将第index行的皇后摆放在第i列if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {row[index] = i;col[i] = true;dia1[index + i] = true;dia2[index - i + n - 1] = true;putQueen(n, index + 1, row);col[i] = false;dia1[index + i] = false;dia2[index - i + n - 1] = false;}}//public static void main(String[] args) {//    int n = 8;//    System.out.println(new Solution().totalNQueens(n));//}
}