LeetCode Hard – N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

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.

Example 1:

Input: n = 4 Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:Input: n = 1 Output: [[“Q”]]

Constraints:

• 1 <= n <= 9

Java Solution

import java.util.ArrayList;
import java.util.List;

public class NQueens {
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        solveNQueensHelper(board, 0, result);
        return result;
    }

    private static void solveNQueensHelper(char[][] board, int row, List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            result.add(constructSolution(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                solveNQueensHelper(board, row + 1, result);
                board[row][col] = '.';
            }
        }
    }

    private static boolean isValid(char[][] board, int row, int col) {
        int n = board.length;

        // Check if there is a queen in the same column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // Check if there is a queen in the left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        // Check if there is a queen in the right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

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

    public static void main(String[] args) {
        int n1 = 4;
        List<List<String>> result1 = solveNQueens(n1);
        System.out.println("N = " + n1 + ":\n" + result1);

        int n2 = 1;
        List<List<String>> result2 = solveNQueens(n2);
        System.out.println("N = " + n2 + ":\n" + result2);
    }
}

This Java code uses backtracking to explore all possible configurations of placing queens on the chessboard and checks for validity at each step. The solveNQueens method returns a list of distinct solutions for the N-Queens puzzle. The isValid method checks whether placing a queen at a specific position is valid or not. The constructSolution method is used to convert the chessboard configuration to the required format for the result.

Python Solution

def solveNQueens(n):
    def is_valid(board, row, col):
        # Check if there is a queen in the same column
        for i in range(row):
            if board[i][col] == 'Q':
                return False

        # Check if there is a queen in the left diagonal
        for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
            if board[i][j] == 'Q':
                return False

        # Check if there is a queen in the right diagonal
        for i, j in zip(range(row - 1, -1, -1), range(col + 1, len(board))):
            if board[i][j] == 'Q':
                return False

        return True

    def construct_solution(board):
        return [''.join(row) for row in board]

    def solve_nqueens_helper(board, row, result):
        if row == len(board):
            result.append(construct_solution(board))
            return

        for col in range(len(board)):
            if is_valid(board, row, col):
                board[row][col] = 'Q'
                solve_nqueens_helper(board, row + 1, result)
                board[row][col] = '.'

    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    solve_nqueens_helper(board, 0, result)
    return result

# Test cases
n1 = 4
result1 = solveNQueens(n1)
print(f"N = {n1}:\n{result1}")

n2 = 1
result2 = solveNQueens(n2)
print(f"N = {n2}:\n{result2}")

This Python code follows the same backtracking approach as the Java solution. The solveNQueens function returns a list of distinct solutions for the N-Queens puzzle. The is_valid function checks whether placing a queen at a specific position is valid or not, and the construct_solution function converts the chessboard configuration to the required format for the result.