The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
1 class Solution { 2 private int cnt = 0; 3 public int totalNQueens(int n) { 4 char[][] board = new char[n][n]; 5 for(int i = 0; i < n; i++) 6 for(int j = 0; j < n; j++) 7 board[i][j] = '.'; 8 dfs(board, 0); 9 return cnt; 10 11 } 12 private void dfs(char[][] board, int col) { 13 if(col==board.length){ 14 cnt++; 15 return; 16 } 17 for(int i = 0;i<board.length;i++){ 18 if(validate(board,i,col)){ 19 board[i][col] = 'Q'; 20 dfs(board,col+1); 21 board[i][col] = '.'; 22 } 23 } 24 } 25 26 private boolean validate(char[][] board, int x, int y) { 27 for(int i = 0;i<board.length;i++) 28 for(int j = 0;j<y;j++) 29 if(board[i][j]=='Q'&&(x==i||x+j==y+i||x+y==i+j)) 30 return false; 31 return true; 32 } 33 34 35 }