N-Queens II

LeetCode Q 52 - N-Queens II

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..”]
]

Solution : DFS

Code:

private int res;
public int totalNQueens(int n) {
	if (n <= 1) return n;
	
	char[][] board = new char[n][n];
	for (char[] row: board) {
		for (int j = 0; j < n; j++) row[j] = '.';
	}
	
	solve(board, n, 0);
	return res;
}

private void solve(char[][] board, int N, int row) {
	if (row == N) {
		res++; return;
	}

	for (int col = 0; col < N; col++) {
		if (board[row][col] == '.' && isValid(board, N, row, col)) {
			board[row][col] = 'Q';
			solve(board, N, row + 1);
			board[row][col] = '.';
		}
	}

	return;
}

private boolean isValid(char[][] board, int N, int row, int col) {
	// check row
	for (int j = 0; j < N; j++) {
		if (board[row][j] == 'Q') return false;
	}

	// check col
	for (int i = 0; i < N; i++) {
		if (board[i][col] == 'Q') return false;
	}

	// check diagonal
	int r = row, c = col;
	while (r >= 0 && c >= 0) {
		if (board[r--][c--] == 'Q') return false;
	}
	r = row; c = col;
	while (r < N && c < N) {
		if (board[r++][c++] == 'Q') return false;
	}

	// check another diagonal
	r = row; c = col;
	while (r < N && c >= 0) {
		if (board[r++][c--] == 'Q') return false;
	}
	r = row; c = col;
	while (r >= 0 && c < N) {
		if (board[r--][c++] == 'Q') return false;
	}

	return false;
}