Skip to main content

N-Queens

Question​

Given an integer n, return all distinct solutions to the n-queens puzzle, where each solution consists of a distinct placement of n queens on an n x n chessboard such that no two queens attack each other.

Example 1
None

Solution​

all//N-Queens.py


def n_queens(n):
    board = [[0 for _ in range(n)] for _ in range(n)]
    if solve_n_queens(board, 0):
        return board
    return None

def solve_n_queens(board, col):
    if col == len(board):
        return True
    for row in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 1
            if solve_n_queens(board, col+1):
                return True
            board[row][col] = 0
    return False

def is_safe(board, row, col):
    # check upper left diagonal
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # check upper right diagonal
    for i, j in zip(range(row, -1, -1), range(col, len(board))):
        if board[i][j] == 1:
            return False

    # check same row
    for i in range(col):
        if board[row][i] == 1:
            return False

    return True