首页 > 代码库 > [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.."]]
Solution:
大神的做法：
http://blog.csdn.net/xift810/article/details/22187633
1 public class Solution { 2 public List<String[]> solveNQueens(int n) { 3 List<String[]> result = new ArrayList<String[]>(); 4 if (n == 0) 5 return result; 6 int[] rCol = new int[n]; 7 queens(result, rCol, 0, n); 8 return result; 9 }10 11 private void queens(List<String[]> result, int[] rCol, int row, int n) {12 // TODO Auto-generated method stub13 if (row == n) {14 printQueens(result, rCol, n);15 return;16 }17 for (int col = 0; col < n; ++col) {18 rCol[row] = col;19 if (check(rCol, row)) {20 queens(result, rCol, row + 1, n);21 }22 }23 }24 25 private boolean check(int[] rCol, int row) {26 // TODO Auto-generated method stub27 for (int i = 0; i < row; ++i) {28 if (rCol[i] == rCol[row])29 return false;30 if (Math.abs(row - i) == Math.abs(rCol[row] - rCol[i])) {31 return false;32 }33 }34 return true;35 }36 37 private void printQueens(List<String[]> result, int[] rCol, int n) {38 // TODO Auto-generated method stub39 String[] s = new String[n];40 for (int i = 0; i < n; ++i) {41 String temp = "";42 for (int j = 0; j < n; ++j) {43 if(rCol[i]==j){44 temp+="Q";45 }else{46 temp+=".";47 }48 }49 s[i]=temp;50 }51 result.add(s);52 }53 }
[Leetcode] N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。