Unravelling the N-Queens Puzzle!

In the realm of chess, the n-queens puzzle presents a captivating challenge that has intrigued minds for centuries. This puzzle involves placing n queens on an n x n chessboard in such a way that no two queens threaten each other. The beauty of this challenge lies not only in its simplicity but also in the depth of strategic planning it requires. Each queen must be placed so that it does not share the same row, column, or diagonal with another queen — a true test of one’s ability to foresee and plan around potential threats.

Imagine a kingdom where each queen commands her territory on the chessboard. The task is akin to arranging a council where no two queens can challenge each other, maintaining harmony across the board. Solving this puzzle is like orchestrating a dance of diplomacy among queens, each needing her space, yet positioned in a way that contributes to the collective peace of the chessboard kingdom.

This mathematical problem isn’t just a test of logic and spatial reasoning; it’s a metaphor for problem-solving and harmony in complexity. As we delve into this ancient puzzle, let’s unravel the mysteries of queenly strategy and boardroom tactics, discovering unique solutions to maintain peace in the realm of the n-queens.

To solve the n-queens puzzle, where you place n queens on an n x n chessboard such that no two queens threaten each other, you can follow a clear and systematic approach known as backtracking. Here’s a simplified version of the algorithm:

Algorithm Steps:

Initialize the Board:

• Start with an empty n x n chessboard. Each cell is initially marked as empty, represented by ‘.’.

Define Helper Functions:

• is_safe(row, col): Check if it’s safe to place a queen at the specified row and col. Ensure no other queens are placed in the same row, column, or diagonals.
• place_queen(row, col): Place a queen on the board at the specified row and col.
• remove_queen(row, col): Remove a queen from the board at the specified row and col.
• add_solution(): Convert the current board configuration into the required output format and add it to the result list.

Backtracking Function — solve(row=0):

• If the row equals n, it means all queens are placed correctly. Call add_solution() to save the board configuration.
• For each column in the current row:
• Use is_safe() to check if placing a queen at row, col is safe.
• If safe, call place_queen(row, col) and then recursively call solve(row + 1).
• After the recursive call, use remove_queen(row, col) to backtrack and try the next column.

Start the Solver:

• Begin the solver function from the first row of the board.

Collect and Return Results:

• Keep a list of all valid board configurations that fulfil the n-queens criteria.
• Return this list as the output.

Pseudocode:

function solveNQueens(n):
    Initialize board[n][n] to all '.'
    result = []

    function is_safe(row, col):
        Check the same column, row, and both diagonals
        return True if safe, False otherwise

    function place_queen(row, col):
        board[row][col] = 'Q'

    function remove_queen(row, col):
        board[row][col] = '.'

    function add_solution():
        Convert board to list of strings
        Add to result

    function solve(row = 0):
        if row == n:
            add_solution()
            return
        for col from 0 to n-1:
            if is_safe(row, col):
                place_queen(row, col)
                solve(row + 1)
                remove_queen(row, col)

    solve(0)
    return result

Python Code:

class Solution:
    def solveNQueens(self, n):
        def is_not_under_attack(row, col):
            for prev_row in range(row):
                if board[prev_row] == col or \
                   (prev_row - board[prev_row]) == (row - col) or \
                   (prev_row + board[prev_row]) == (row + col):
                    return False
            return True

        def place_queen(row, col):
            board[row] = col

        def remove_queen(row, col):
            board[row] = -1

        def add_solution():
            solution = []
            for i in range(n):
                row = ['.'] * n
                row[board[i]] = 'Q'
                solution.append(''.join(row))
            output.append(solution)

        def backtrack(row = 0):
            for col in range(n):
                if is_not_under_attack(row, col):
                    place_queen(row, col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    remove_queen(row, col)

        board = [-1] * n
        output = []
        backtrack()
        return output

# Example usage
sol = Solution()
print(sol.solveNQueens(4))  # Output: [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]
print(sol.solveNQueens(1))  # Output: [["Q"]]

Explanation:

• Board Representation: The board list stores the column index of the queen in each row.
• Backtrack Function: Recursively tries to place a queen in each column of the current row and moves to the next row if the placement doesn’t lead to a conflict.
• Conflict Checking: is_not_under_attack checks columns and diagonals for potential threats using differences and sums of indices, which uniquely identify diagonals.
• Adding Solutions: Converts the internal board representation into the required list of strings format once a valid arrangement is found.

Complexity:

• Time Complexity: O(n!), since each row reduces the possibilities for the next row exponentially.
• Space Complexity: O(n) for the recursion stack and board storage.

This backtracking approach efficiently explores all configurations and ensures that all solutions meet the problem’s constraints without any two queens threatening each other.