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:
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 | 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