首页 > 代码库 > LeetCode N-Queens
LeetCode N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens‘ placement, where ‘Q‘ and ‘.‘ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."]]
1 public class Solution { 2 List<String[]> result; 3 int[] A; 4 public List<String[]> solveNQueens(int n) { 5 result = new ArrayList<String[]>(); 6 A = new int[n]; 7 nqueens(0, n); 8 return result; 9 } 10 public void nqueens(int cur, int n){ 11 if(cur==n) printres(n); 12 else { 13 for(int i=0;i<n;i++){ 14 A[cur] = i; 15 if(valid(cur)){ 16 nqueens(cur+1, n); 17 } 18 } 19 } 20 } 21 public void printres(int n){ 22 String[] tem = new String[n]; 23 for(int i=0;i<n;i++){ 24 StringBuffer sBuffer = new StringBuffer(); 25 for(int j=0;j<n;j++){ 26 if(j==A[i]) sBuffer.append(‘Q‘); 27 else sBuffer.append(‘.‘); 28 } 29 tem[i] = sBuffer.toString(); 30 } 31 result.add(tem); 32 } 33 public boolean valid(int r){ 34 for(int i=0;i<r;i++){ 35 if(A[i]==A[r]|| Math.abs(A[i]-A[r])==r-i){ 36 return false; 37 } 38 } 39 return true; 40 } 41 }
LeetCode N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。