N-Queens

LeetCode Q 51 - N-Queens

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 all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example:
Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution : DFS

Code:

private List<List<String>> res;

public List<List<String>> solveNQueens(int N) {
	res = new ArrayList<>();
	if (N <= 0) return res;
	
	// build graph
	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) {
		List<String> list = new ArrayList<>();
		for (int i = 0; i < board.length)
			list.add(String.valueOf(board[i]));
		res.add(list);
	}

	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;
}