首页 > 代码库 > N-Queens II
N-Queens II
题目
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
方法
和上题方法一样,使用回溯法,结构基本相同,只需要返回数量。public int totalNQueens(int n) { int[] queenAtCol = new int[n]; int total = getNQueens(0, n, queenAtCol); return total; } public List<String[]> solveNQueens(int n) { List <String[]> list = new ArrayList<String[]>(); return list; } private int getNQueens(int row, int n, int[] queenAtCol) { if (row == n) { return 1; } else { int tempSum = 0; for (int col = 0; col < n; col++) { if (isValid(row,col,queenAtCol)) { queenAtCol[row] = col; tempSum += getNQueens(row + 1, n, queenAtCol); } } return tempSum; } } private boolean isValid(int row, int col,int[] queenAtCol) { //row is valid. //column for (int i = 0; i < row; i++) { if (queenAtCol[i] == col) { return false; } } for (int i = 0; i < row; i++) { if (i + queenAtCol[i] == row + col) { return false; } } for (int i = 0; i < row; i++) { if (col - row == queenAtCol[i] - i) { return false; } } return true; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。