首页 > 代码库 > [LeetCode]51 N-Queens
[LeetCode]51 N-Queens
https://oj.leetcode.com/problems/n-queens/
http://blog.csdn.net/linhuanmars/article/details/20667175
public class Solution { public List<String[]> solveNQueens(int n) { List<String[]> result = new ArrayList<>(); int[] qcols = new int[n]; solve(n, 0, qcols, result); return result; } private void solve(int n, // number of queen int row, // current row iteration, [0 -> n-1] int[] qcols, // describing queens positions List<String[]> result) { if (row == n) { // all [0, n-1] has fulfilled, a solution found. result.add(toBoard(qcols)); return; } // We are on row // try to put Q in each columns, and check for (int i = 0 ; i < n ; i ++) { qcols[row] = i; boolean valid = checkBoard(qcols, row); if (valid) { // Enter next iteration solve(n, row + 1, qcols, result); } } } // 此方法检查新增的Q(row)是否符合已有的棋盘 // 因为一行只保存一个Q的位置,所以行一定符合 // 检查列:qcols[i] != qcols[row] // 检查对角线 abs(i - row) != abs(qcols[i] - qcols[row]) // Check new Q(on row) can fit existing board. private boolean checkBoard(int[] qcols, int row) { for (int i = 0 ; i < row ; i ++) { if ((qcols[i] == qcols[row]) || Math.abs(i - row) == Math.abs(qcols[i] - qcols[row])) return false; } return true; } // Build the board. private String[] toBoard(int[] qcols) { int n = qcols.length; String[] b = new String[n]; for (int i = 0 ; i < n ; i ++) { int qcol = qcols[i]; StringBuilder sb = new StringBuilder(); for (int j = 0 ; j < qcol ; j ++) sb.append("."); sb.append("Q"); for (int j = qcol + 1 ; j < n ; j ++) sb.append("."); b[i] = sb.toString(); } return b; } }
[LeetCode]51 N-Queens
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。