题解 | #N皇后问题# 简单的dfs
N皇后问题
https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6
import java.util.*; 主要细节点是注意左上方、右上方是否有重叠 public class Solution { /** * * @param n int整型 the n * @return int整型 */ int[][]arr; int tot=0; public int Nqueen (int n) { // write code here arr=new int[n][n]; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { arr[i][j]=-1; } } backtrack(arr,0); return tot; } public void backtrack(int[][]arr,int row){ if(row==arr.length) { tot++; return;} for(int i=0;i<arr.length;i++){ if(!valid(arr,i,row)) continue; arr[row][i]=0; backtrack(arr,row+1); arr[row][i]=-1; } } private boolean valid(int[][] arr, int col, int row) { for(int index=0;index<arr.length;index++){ if(arr[index][col]==0){ return false; } } for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){ if(arr[i][j]==0){ return false; } } for(int i=row-1,j=col+1;i>=0&&j<arr.length;i--,j++) { if(arr[i][j]==0) return false; } return true; } }