N-Queens - Python Solution

1. Introduction

The "N-Queens" puzzle is a well-known problem in computer science and combinatorics. It involves placing n queens on an n x n chessboard so that no two queens threaten each other. The challenge lies in the queens' unique movement, as they can move any number of squares vertically, horizontally, or diagonally. This problem is a classic example of backtracking and is often used to teach algorithm design and problem-solving techniques.

Problem

Given an integer n, the task is to return all distinct solutions to the n-queens puzzle. Each solution should contain a distinct board configuration of the queens' placement, where 'Q' represents a queen and '.' represents an empty space. No two queens should attack each other.

2. Solution Steps

1. Understand the rules of queen movement and the requirements for a valid solution.

2. Use backtracking to systematically explore all potential board configurations.

3. Implement checks to ensure that no two queens threaten each other.

4. Convert each valid configuration into the required output format.

5. Return all the distinct solutions.

3. Code Program

def solveNQueens(n):
    def isSafe(row, col):
        # Check if a queen can be placed at (row, col)
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def solve(row):
        # Base case: all queens are placed
        if row == n:
            solution = []
            for i in board:
                solution.append('.' * i + 'Q' + '.' * (n - i - 1))
            solutions.append(solution)
            return
        # Try placing a queen in each column
        for col in range(n):
            if isSafe(row, col):
                board[row] = col
                solve(row + 1)

    solutions = []
    board = [-1] * n
    solve(0)
    return solutions

# Testing the function with an example
print(solveNQueens(4))

Output:

[
 ['.Q..',
  '...Q',
  'Q...',
  '..Q.'],
 ['..Q.',
  'Q...',
  '...Q',
  '.Q..']
]

Explanation:

1. Safety Check: The isSafe function checks if a queen can be placed at a given row and column without being attacked.

2. Recursive Solving: The solve function uses recursion to place a queen in each row.

3. Base Case: When all queens are placed, the solution is converted into the required format and added to the list of solutions.

4. Backtracking: For each row, the function iterates over columns and uses backtracking to explore all possible placements.

5. Board Representation: The board is represented as a list of integers, where each integer represents the column index of the queen in that row.

6. Final Output: The function returns a list of solutions, each representing a distinct configuration of the n-queens' placement.