N皇后问题

//当个乐子看就行了

public int Nqueen (int n) {
        // write code here
        switch(n){
            case 1:
                return 1;
            case 2:
                return 0;
            case 3:
                return 0;
            case 4:
                return 2;
            case 5:
                return 10;
            case 6:
                return 4;
            case 7:
                return 40;
            case 8 : 
                return 92;
            case 9:
                return 352;
        }
        return 0;
    }

 int ans=0;
    public int Nqueen (int n) {
        //在build()中，放置第i个皇后
        int[] arr=new int[n];//arr[i]表示第i个皇后在第j列
        build(0,n,arr);//放置第0个皇后，总共放置n个皇后，arr[n]表示第n个皇后的列数
        return ans;
    }
    public void build(int i,int n,int[] arr){
        if(i==n){
            ans++;
            return;
        }
        for(int j=0;j<n;j++){
            arr[i]=j;//把第i个皇后放到第j列
            if(check(i,arr)==true){//如果第i个皇后可以放置
                build(i+1,n,arr);  //如果可以放置，那就递归调用放置第i+1个皇后
            }
        }
    }
    public boolean check(int i,int[] arr){
        for(int j=0;j<i;j++){//只需要遍历0~i
            if(arr[i]==arr[j]){  //第i个皇后和第j个皇后在同一列上
                return false;
            }
            if(Math.abs(i-j)==Math.abs(arr[i]-arr[j])){  // |行i-行j|=|列i-列j|，则在一条斜线上
                return false;
            }
        }
        return true;
    }

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int count = 0;
    public int Nqueen (int n) {
        // write code here
        //创建一个二维数组用来模拟棋盘并占位
        int[][] board = new int[n][n];
        
        dfs(n, 1, board);
        return count;
    }
    public void dfs(int n, int row, int[][] board) {
        //如果row等于n + 1，则计数+1
        
        if (row > n) {
            count++;
            return;
        }
        //遍历本行棋盘
        for (int i = 0; i < n; i++) {
            //System.out.print("行:" + row);
            //System.out.print("列:" + (i+1) + "   ");
            if (board[row - 1][i] == 1) {
                continue;
            }
            int[][] newBoard = new int[n][n];
            for (int q = 0; q < n; q++){
                for (int p = 0; p < n; p++) {
                    newBoard[q][p] = board[q][p];
                }
            }
            //将该棋子下方同列同斜线所有格子都标记
            for (int below = row -1; below < n; below++) {
                //正下方标记
                newBoard[below][i] = 1;
                //左斜下方标记
                if (i - (below- row + 1) >= 0) {
                    newBoard[below][i - (below-row + 1)] = 1;
                }
                //右斜下方标记
                if (i + (below- row + 1) < n) {
                    newBoard[below][i + (below-row + 1)] = 1;
                }
            } 
            //进入下一层
            
            dfs(n,row+1,newBoard);    
        }   
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int n;
    int cnt =0;
    boolean[] col;
    boolean[] line1;
    boolean[] line2;
    public int Nqueen (int n) {
        // write code here
        this.n = n;
        col = new boolean[n];
        line1 = new boolean[2*n-1];
        line2 = new boolean[2*n-1];
        backtraking(0);
        return cnt;
    }

    //固定到第n行
    public void backtraking(int index){
        //成功了一种
        if(index==n){
            cnt++;
            return;
        }
        //摆放第index行的皇后
        //同一斜线：row+col(index+i)相等，或者col-row(index-i)相等
        //用三个数组存储列(i)，index+i(范围是0到2n-2),index-i(-n+1到n-1)
        for(int i=0;i<n;i++){
            //列或者斜线上有
            if(col[i]||line1[i+index]||line2[index-i+n-1]) continue;
            col[i] = true;
            line1[i+index] = true;
            line2[index-i+n-1] = true;
            backtraking(index+1);
            col[i] = false;
            line1[i+index] =false;
            line2[index-i+n-1] = false;
        }
    }
}

public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    int count = 0; // 记录共有多少种解法
    public int Nqueen (int n) {
        int[] arr = new int[n]; // 初始化一维数组保存皇后所在第几列， 下标正好表示皇后处在第几行，而下标对应的值是皇后在第几列
        getNqueen (0, n, arr); // 递归求解
        return count;
    }
    /**
     *
     * @param i 要插入数组元素的下标索引，
     * @param n 最大n个皇后问题
     * @param arr 保存皇后位置的数组
     * @return
     */
    public void getNqueen (int i, int n, int[] arr) {
        if(i == n){ // i为要插入第i个皇后，如果i 等于最大数量n时，表示这一轮的解已然获取到，则count++
            count++;
            return;
        }
        for(int k = 0; k < n; k++){ // 从0开始，这里的循环0 - n 就是皇后要放入的那一列
            arr[i] = k; // 先将第i个皇后放入第k列
            if(check(i, arr)){ // 判断改皇后的位置是否冲突
                getNqueen (i + 1, n, arr); // 如果不冲突，则递归放置下一个皇后的位置
            }
        }
    }

    /**
     *
     * @param i 检查第i个皇后 位置是否冲突
     * @param arr 储存皇后位置的数组
     * @return
     */
    public boolean check(int i, int[] arr){
        // 从第0个皇后位置开始检查 与 第i个皇后 位置是否冲突
        for(int j = 0; j < i; j++){
            // 1. 只要第j个皇后 和 第i个皇后的位置相等
            // 2.判断解读: Math.abs(i - j) == Math.abs(arr[i] - arr[j]) 意思如下:
            //      Math.abs(i - j) 实际上获取的是两个皇后相差多少行，因为下标就是表示皇后在第几行上
            //      Math.abs(arr[i] - arr[j]) 取出第i个皇后所在的列，和第j个皇后所在列 相减得出的差 只要等于他们相差的行数，那就是在斜线上
            //   举例子说明:
            //   列号:  0 1 2 3 4 5 6 7
            //  行号2:  0 0 1 0 0 0 0 0    这一行的 1 就与最下面一行的1 处于斜线。
            //  行号1:  0 0 0 0 1 0 0 0
            //  行号0:  1 0 0 0 0 0 0 0
            //  行号2的1 与 行号0的1 两者之间相差行数为2，  并且行号2的1 所在列为2, 行号0的1 所在列为0
            //   所以列的差2 - 0 = 2，行的差2 - 0 = 2，相等则两个在一个斜线
            if(arr[i] == arr[j] || Math.abs(i - j) == Math.abs(arr[i] - arr[j])){
                return false; // 符合条件就返回false，表示位置冲突
            }
        }
        return true;
    }
}

import java.util.*;


public class Solution {
   int result = 0;
    public int Nqueen (int n) {
        //用一个一维数组模拟二维数组，数组下标表示第I行,arr[i]的值表示放在第j列
        int[] arr = new int[n];
        backTracking(arr,0);
        return result;
    }
    public void backTracking(int[] arr,int i){
        int x = arr.length;
        if(arr[x-1] > 0){
            //最后一个棋子放完后，检查棋盘是否冲突，无冲突则将结果+1
            if( check(arr,x-1)){
                result ++;
            }
            return;
        }

        for(int j = 0;j < x;j ++){
            arr[i] = j+1;
            if(check(arr,i)){//无冲突则向下搜索
                backTracking(arr,i+1);
            }
            //一列搜索完毕后回溯，进入下一次循环检测下一列是否符合要求
            arr[i] = 0;
        }
    }
    //检查当前棋盘是否存在冲突
    //如果进入检查阶段，那么只需要检测最后一个棋子和前面的是否有冲突
    //index为最后一个棋子的下标
    public static boolean check(int[] arr,int index){
        for(int i =0;i < index;i ++){
            if(arr[i] == arr[index] || (Math.abs((index-i)) == Math.abs((arr[index] - arr[i])))){
                return false;
            }
        }
        return true;
    }
  
}

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型 the n
     * @return int整型
     */
    int nums = 0;
    public int Nqueen (int n) {
        // write code here
        // 思路  矩阵呢个 看作是n*n的二维数组
        // 长度为n的矩阵必须放n个
        // 根据规则  一行只能放一个  且必须有一个
        // for循环遍历每一行  递归一次加一行
        // 每一行找到数组中为零的位置 没有就继续遍历  直到遍历完
        // 找到位置之后把该行 列  斜线 全部加1 表示这些位置不可用
        // 为什么是加1  而不是等于1
        // 因为 最后能返回的条件就是所递归的行数走到了最后  表示已经找到了一条路径
        // 这时需要回溯 回溯的时候就需要把当前加1 的值减去
        // 节点中在赋值的时候会出现交叉情况  如果直接置为零会把前面的部分已赋值的节点所改变
        int[][] a = new int[n][n];
        count(a, 0);
        return nums;
    }

    public void count(int[][] a, int num) {
        if (num == a.length) {
            ++nums;
            return;
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i][num] == 0) {
                addOne(a, i, num, 1);
                count(a, num + 1);
                addOne(a, i, num, -1);
            }
        }
    }

    public void addOne(int[][] a, int i, int j, int t) {
        add1(a, i, j, t);
        add2(a, i, j, t);
        add3(a, i, 0, t);
        add4(a, 0, j, t);
        add5(a, i, j, t);
        add6(a, i, j, t);
    }

    public void add1(int[][] a, int i, int j, int t) {
        if (i < 0 || j < 0 || i > a.length - 1 || j > a[0].length - 1) {
            return;
        }
        a[i][j] += t;
        add1(a, --i, --j, t);
    }
    public void add6(int[][] a, int i, int j, int t) {
        if (i < 0 || j < 0 || i > a.length - 1 || j > a[0].length - 1) {
            return;
        }
        a[i][j] += t;

        add6(a, ++i, --j, t);

    }
    public void add2(int[][] a, int i, int j, int t) {
        if (i < 0 || j < 0 || i > a.length - 1 || j > a[0].length - 1) {
            return;
        }
        a[i][j] += t;

        add2(a, --i, ++j, t);
    }
    public void add3(int[][] a, int i, int j, int t) {
        if (i < 0 || j < 0 || i > a.length - 1 || j > a[0].length - 1) {
            return;
        }
        a[i][j] += t;
        add3(a, i, ++j, t);
    }
    public void add4(int[][] a, int i, int j, int t) {
        if (i < 0 || j < 0 || i > a.length - 1 || j > a[0].length - 1) {
            return;
        }
        a[i][j] += t;
        add4(a, ++i, j, t);
    }
    public void add5(int[][] a, int i, int j, int t) {
        if (i < 0 || j < 0 || i > a.length - 1 || j > a[0].length - 1) {
            return;
        }
        a[i][j] += t;
        add5(a, ++i, ++j, t);
    }
}

import java.util.*;
public class Solution {
    int count = 0;
    public int Nqueen (int n) {
        char[][] chars = new char[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                chars[i][j] = '-';
            }
        }
        backtrack(chars, n, 0);
        return count;
    }
    
    public void backtrack(char[][] chars, int n, int i){
        if(i==n){
            count++;
            return;
        }
        
        for(int j=0; j<n; j++){
            if(!isValid(chars, i, j)) continue;
            chars[i][j] = 'Q';
            backtrack(chars, n, i+1);
            chars[i][j] = '-';
        }
    }
    
    // 合法性判断
    public boolean isValid(char[][] chars, int x, int y){
        for(int i=0; i<x; i++){
            if(chars[i][y]=='Q') return false;
            if(y-x+i>=0 && chars[i][y-x+i]=='Q') return false;
            if(y+x-i< chars.length && chars[i][y+x-i]=='Q') return false;
        }
        return true;
    }
}

public class Solution {
    int res = 0;
    public int Nqueen (int n) {
         //创建棋盘，并初始化填充'.'
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        backtracking(board, 0);
        return res;
    }
    void backtracking(char[][] board, int row) {
        //遍历到叶子节点（即最后一层），记录结果并返回
        if (row == board.length) {
            res++;
            return;
        }
        //在每一行的列中做选择
        for (int col = 0; col < board[0].length; col++) {
            //选择无效，判断当前列、左上和右上
            if (!isValid(board, row, col)) {
                continue;
            }
            //做选择
            board[row][col] = 'Q';
            //递归下一行
            backtracking(board, row + 1);
            //撤销选择
            board[row][col] = '.';
        }
    }

    //判断该位置是否可以放皇后：该列、左上和右上都没有皇后才可以
    boolean isValid(char[][] board, int row, int col) {
        //当前列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        //左上方
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0 ; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        //右上方
        for (int i = row - 1, j = col + 1; i >= 0 && j < board[0].length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

// 烂代码，凑合看
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    private static int counter =0;
    public int Nqueen (int n) {
        List<Pos> pool  = new ArrayList<>();
        //Integer counter = new Integer(0);
        backtrack(n,pool,1);
        return counter;
    }

    private void backtrack (int n,List<Pos>pool,int currRow) {
        if (currRow==n+1) {
            counter++;
            return;
        }
        for (int c = 1; c <=n ; c++) {
            if (!valid(pool,new Pos(currRow,c))) {
                continue;
            }
            pool.add(new Pos(currRow,c));
            backtrack(n,pool,currRow+1);
            pool.remove(pool.size()-1);
        }
    }

    private boolean valid(List<Pos>pool,Pos currPos) {
        for (Pos pos : pool) {
            if (pos.r==currPos.r || pos.c==currPos.c ||
            currPos.c- currPos.r==pos.c- pos.r ||
            currPos.c+ currPos.r== pos.c+ pos.r) {
                return false;
            }
        }
        return true;
    }

    class Pos {
        public int r;
        public int c;

        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pos pos = (Pos) o;
            return r == pos.r && c == pos.c;
        }

        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
     int cnt =0;
    public int Nqueen (int n) {
        // write code here
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return cnt;
        
    }
  

    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            cnt++;
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }




    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
    
}

简单粗暴： DFS + 回溯
思路： 其实主要是判断正反对角线，放入一个元素之后，把不能放元素的位置加入到set集合中，然后遍历的时候，看是否在集合中，若在集合中，则表示不能放Q，若不在，则可以放，知道放入Q的数量和n维数组的长度相同即可。
正反对角线规律：可参看数学中坐标系
正对角线为：(0,0)、（1,1）、（2,2）, 相差为0
反对角线为：（2，-2）(1,-1)、（0，0）, 相加为0

import java.util.*;
/**
 * N 皇后问题
 *
 * N皇后规则：所在行、列、对角线中不能存在元素
 *
 * 思路：DFS + 回溯
 * 递归行，遍历列
 */

public class Solution {
    private static int result = 0;
    private static Set<Integer> columns = new HashSet<>(); // 列
    private static Set<Integer> positiveDiagonal = new HashSet<>(); // 正对角线
    private static Set<Integer> negativeDiagonal = new HashSet<>(); // 反对角线
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        // write code here
        dfs(0, n);
        return result;
    }

    private void dfs(int row, int n) {
        // 结束标志
        if (row == n) {
            result++;
            return;
        }
        for (int i = 0; i < n; i++) {
            // 判断该列中已经放过Q || 处于正反对角线上
            // 正对角线为：(0,0)、（1,1）、（2,2）, 相差为0
            // 反对角线为：（2，-2）(1,-1)、（0，0）, 相加为0
            if (columns.contains(i) || positiveDiagonal.contains(row - i) || negativeDiagonal.contains(row + i)) {
                continue;
            }
            columns.add(i);
            positiveDiagonal.add(row - i);
            negativeDiagonal.add(row + i);
            dfs(row + 1, n);
            negativeDiagonal.remove(row + i);
            positiveDiagonal.remove(row - i);
            columns.remove(i);
        }
    }
}

//向大佬学习
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    //计数
    private static Integer c=new Integer(0);
    
    public int Nqueen (int n) {
        // dfs遍历
        formN(n);
        return c;
    }
    
    //创建棋盘
    public void formN(int n){
        char[][] chess=new char[n][n];
        for(int i=0;i<chess.length;i++)
            for(int j=0;j<chess.length;j++)
                chess[i][j]='a';
        dfsN(chess,0);
    }
    
    //dfs遍历，按行寻找，若能找到底即x==n(chess.length)则计数加1
    public void dfsN(char[][] chess,int x){
        if(x==chess.length){
            c++;
            return;
        }
        for(int y=0;y<chess.length;y++){
            if(findN(chess,x,y)){
                chess[x][y]='b';
                dfsN(chess,x+1);
                chess[x][y]='a';//回溯
            }
        }
    }
    
    //按行+1的找，所以只需判断上面、左上、右上有无重复
    private boolean findN(char[][] chess,int x,int y){
        //up
        for(int i=x-1;i>=0;i--){
            if(chess[i][y]=='b'){return false;}
        }
        //upright
        for(int i=x-1,j=y+1;i>=0&&j<chess.length;i--,j++){
            if(chess[i][j]=='b'){return false;}
        }
        //upleft
        for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--){
            if(chess[i][j]=='b'){return false;}
        }
        return true;
    }
}

评论区大佬好多
import java.util.*;
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    Set<Integer> column = new HashSet<Integer>(); //标记列不可用
    Set<Integer> posSlant = new HashSet<Integer>();//标记正斜线不可用
    Set<Integer> conSlant = new HashSet<Integer>();//标记反斜线不可用
    int result = 0;

    public int Nqueen (int n) {
        // write code here
        compute(0, n);
        return result;
    }
    private void compute(int i, int n){
        if(i == n){
            result++;
            return;
        }
        for(int j = 0; j < n; j++){
            if(column.contains(j) || posSlant.contains(i - j) || conSlant.contains(i + j)){
                continue;
            }
            column.add(j);//列号j 
            posSlant.add(i - j);//行号i - 列号j 正斜线
            conSlant.add(i + j);//行号i + 列号j 反斜线
            compute(i + 1, n); //计算下一行
            column.remove(j); //完成上一步递归计算后，清除
            posSlant.remove(i - j);
            conSlant.remove(i + j);
        }
    }
}

   static  int count=0;//全局属性
   static  int arr[];
   public int Nqueen (int n) {
        // write code here
        if(n==0)
            return 0;
        arr = new int[n];
		put(arr,0,n);
        return count;
	}
	public  boolean judge(int arr[],int s){
		for(int i=0;i<s;i++){
			if(arr[s]==arr[i] || s-i==Math.abs(arr[s]-arr[i])){//遍历s以上元素，判断放置是否合理，不合理则回溯
				return false;
			}
		}
		return true;
    }
	public void put(int arr[],int i,int n){
		if(i == n){//满足条件则通过
            count++;//增加count的个数
            return;
        }
        for(int j=0;j<n;j++){
			arr[i]=j;//在第i+1行的j+1出放置
			if(judge(arr,i)){//判断放置是否合理
				put(arr,i+1,n);
			}
		}
  }

public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int res = 0;            //    计数，作为返回结果
    
    public int Nqueen (int n) {
        // write code here
        int[] graph = new int[n];
        backTracking(0, graph);
        return res;
    }
    
    public void backTracking(int n, int[] array){
        if (n == array.length){
            res += 1;
            return ;
        }
        for (int i = 0; i < array.length; i++){            //    从第一列开始放置
            array[n] = i;                    //    第n行皇后放在第i列
            if (isConflict(n, array)){
                backTracking(n + 1, array);
            }else {
                continue ;
            }
        }
    }
            
    public boolean isConflict(int n, int[] array){                //    判断第n行是否冲突
        for (int i = 0; i < n; i++){
            if (array[n] == array[i] || Math.abs(n - i) == Math.abs(array[n] - array[i])){
                return false;
            }
        }
        return true;
    }
 }