本文主要是介绍【LeetCode】N-Queens II 【九度】题目1254：N皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
N-Queens II
Total Accepted: 2737 Total Submissions: 10408 My Submissions
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
这个其实比N-Queens要简单，只需要输出个数就可以。
BFS超时，DFS很快就过了，和九度题目1254：N皇后问题一样，也是DFS。
Java DFS AC
public class Solution {public int totalNQueens(int n) {if(n <= 0){return 0;}int []queen = new int[n + 1];count = 0;for(int i = 1; i < n+1 ; i++){queen[1] = i;dfs(queen,2,n);}return count;}public int count ;public void dfs(int queen[], int line, int n) {if(line == n+1){count ++;return;}for(int i = 1; i < n+1; i++){if(valid(line, i, queen)){queen[line] = i;dfs(queen ,line+1, n);queen[line] = 0;}}}public boolean valid(int row, int col, int []queen) {for (int i = 1; i < row; i++) {if (queen[i] != 0 && (queen[i] == col || Math.abs(i - row) == Math.abs(queen[i] - col))) return false; }return true;}
}九度题目1254：N皇后问题
Java DFS AC
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main{/** 1254*/public static int count;public static void main(String[] args) throws Exception {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));while (st.nextToken() != StreamTokenizer.TT_EOF) {int n = (int) st.nval;count = 0;solveNQueens(n);System.out.println(count);}}public static void solveNQueens(int n) {if(n <= 0){return;}int []queen = new int[n + 1];for(int i = 1; i < n+1 ; i++){queen[1] = i;dfs(queen,2,n);}}public static void dfs(int queen[], int line, int n) {if(line == n+1){count++;return;}for(int i = 1; i < n+1; i++){if(valid(line, i, queen)){queen[line] = i;dfs(queen,line+1, n);queen[line] = 0;}}}public static boolean valid(int row, int col, int []queen) {for (int i = 1; i < row; i++) {if (queen[i] != 0 && (queen[i] == col || Math.abs(i - row) == Math.abs(queen[i] - col))) return false; }return true;}
}/**************************************************************Problem: 1254User: wangzhenqingLanguage: JavaResult: AcceptedTime:2860 msMemory:17600 kb
****************************************************************/这篇关于【LeetCode】N-Queens II 【九度】题目1254：N皇后问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
