N-Queens - LeetCode Solution in Java

1. Introduction

The N-Queens puzzle is a classic problem that involves placing n queens on an n x n chessboard in a way that no two queens attack each other. A solution to the puzzle requires that no two queens share the same row, column, or diagonal.

2. Problem

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

3. Solution Steps

1. Use backtracking to solve the problem.

2. Create a chessboard represented by a 2D array or list of strings.

3. Place a queen in a row and move to the next row.

4. Check if the placement is safe (no other queen in the same column, diagonal, or anti-diagonal).

5. If safe, place the queen and move to the next row.

6. If not, try the next column.

7. Backtrack if no column is safe in a row, and move the queen in the previous row.

8. Add the board to the result when all queens are placed.

4. Solution in Java

public List<List<String>> solveNQueens(int n) {
    char[][] board = new char[n][n];
    for(int i = 0; i < n; i++)
        Arrays.fill(board[i], '.');
    List<List<String>> result = new ArrayList<>();
    backtrack(result, board, 0);
    return result;
}

private void backtrack(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(result, board, row + 1);
            board[row][col] = '.'; // backtrack
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == 'Q' && (col == j || Math.abs(row - i) == Math.abs(col - j)))
                return false;
        }
    }
    return true;
}

private List<String> construct(char[][] board) {
    List<String> res = new ArrayList<>();
    for (char[] row : board) {
        res.add(new String(row));
    }
    return res;
}

This solution employs backtracking to place queens one row at a time, checking at each step whether the placement is valid, and backtracking as needed until all queens are successfully placed.

Explanation:

1. The backtrack method attempts to place queens row by row.

2. The isValid method checks if a queen can be placed at the given row and col without being attacked.

3. The check includes the same column, diagonal, and anti-diagonal checks.

4. If it's valid, place the queen ('Q'), and move to the next row.

5. If it's not valid, or if the end of the board is reached without finding a valid place, backtrack by removing the queen and trying the next position.

6. The construct method converts the board to a list of strings representing the board configuration.

7. Once all queens are placed (when row == board.length), the current board configuration is added to the result.