首页 > 代码库 > N-Queens
N-Queens
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.."]]
这里需要用到回溯（su）算法
回溯算法
1.定义一个解空间，即存放一个解的空间
2.开始遍历，DFS，如果没有一个合适的，回退上一步
这个还要多了解，多谢谢才okay
1 public class Solution { 2 int solution[]; 3 int num_queen; 4 List<String[]> result = new ArrayList<String[]>(); 5 6 public List<String[]> solveNQueens(int n) { 7 solution = new int[n + 1]; 8 num_queen = n; 9 placeQueen(1);10 return result;11 }12 13 /**放第n个皇后14 * @param n15 */16 public void placeQueen(int n){17 if(n > num_queen){18 String temp[] = new String[num_queen];19 String tempStr = "";20 21 for(int i = 1; i <= num_queen; i++){22 for(int j = 1; j <= num_queen; j++){23 if(j == solution[i])24 tempStr += "Q";25 else26 tempStr += ".";27 }28 temp[i - 1] = tempStr;29 tempStr = "";30 }31 result.add(temp);32 }else{33 for(int i = 1; i <= num_queen; i++){34 solution[n] = i; //将n个皇后放到i列35 if(isValid(n)) //如果i列有效36 placeQueen(n + 1); //放下一个皇后37 }38 }39 }40 41 /**42 * 第k个皇后的位置是否有效43 * @param k44 * @return45 */46 public boolean isValid(int k){47 for(int i = 1; i < k; i++){48 if(solution[i] == solution[k] || Math.abs(i - k) == Math.abs(solution[i] - solution[k]))49 return false;50 }51 return true;52 }53 54 }
N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。