主页 > 编程 > Java

n后问题回溯法java

167 2024-03-08 17:16

java public class NQueens { private int[] cols; private List> result = new ArrayList<>(); public List> solveNQueens(int n) { cols = new int[n]; solveNQueensHelper(0, n); return result; } private void solveNQueensHelper(int row, int n) { if (row == n) { List solution = new ArrayList<>(); for (int i = 0; i < n; i++) { StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { sb.append(cols[i] == j ? 'Q' : '.'); } solution.add(sb.toString()); } result.add(solution); return; } for (int i = 0; i < n; i++) { cols[row] = i; if (isValid(row)) { solveNQueensHelper(row + 1, n); } } } private boolean isValid(int row) { for (int i = 0; i < row; i++) { if (cols[i] == cols[row] || Math.abs(cols[i] - cols[row]) == row - i) { return false; } } return true; } }
顶一下
(0)
0%
踩一下
(0)
0%
相关评论
我要评论
点击我更换图片