Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
This is an extension of the N-Queen I problem, but just asks for returning the number of solutions.
Solution:
public class Solution { private int result = 0; public int totalNQueens(int n) { if (n == 0 || n == 2 || n == 3) { return 0; } int[] cols = new int[n]; totalNQueensHelper(n, 0, cols); return result; } private void totalNQueensHelper(int n, int row, int[] cols) { if (row == n) { result++; return; } for (int j = 0; j < n; j++) { if (isValid(j, row, cols)) { cols[row] = j; totalNQueensHelper(n, row + 1, cols); } } } private boolean isValid(int col, int rows, int[] cols) { for (int i = 0; i < rows; i++) { if (cols[i] == col || rows - i == Math.abs(cols[i] - col)) { return false; } } return true; } }
No comments:
Post a Comment