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.
解法
经典的算法问题:N皇后问题。先解释一下:皇后不能同时出现在同一列,同一行或在同一条斜边上。为了找出所有可能的摆放,我们按行进行搜索,每一行寻找一个可以摆放的位置,如果合法,则进行下一行的搜索,当那一行不存在合法的摆放时,回溯归位。就是典型的回溯法解题啦~此题的关键在于数据结构的设计,巧妙地使用一维数组记录每一行皇后的j坐标可以将算法的设计大大简化。
具体代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
class { List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { int [] jpos = new int [n]; searchline(0 , n, jpos); return res; } void searchline (int k, int n, int [] jpos) { if (k == n) { List<String> s = new ArrayList<>(); for (int i = 0 ; i < n; i++) { StringBuffer tmp = new StringBuffer("" ); for (int j = 0 ; j < n; j++) { if (j == jpos[i]) { tmp.append("Q" ); } else { tmp.append("." ); } } s.add(tmp.toString()); } res.add(s); return ; } for (int j = 0 ; j < n; j++) { jpos[k] = j; if (canplace(k, jpos)) { searchline(k + 1 , n, jpos); } jpos[k] = 0 ; } } Boolean canplace (int k, int [] jpos) { for (int i = 0 ; i < k; i++) { if (jpos[i] == jpos[k] || Math.abs(jpos[i] - jpos[k]) == Math.abs(k - i)) { return false ; } } return true ; } }
近期评论