Generate all safe queen placements on board

Q: Generate all safe queen placements on board

This question evaluates algorithm design for constraint-satisfaction problems, testing skills in search, recursion, backtracking, combinatorics, and state-space pruning.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an integer n representing the size of a chessboard (n × n). You need to place n queens on the board so that no two queens attack each other.

A queen can attack another piece if they are on the same row, same column, or same diagonal.

Return all distinct valid configurations of the board.

Each configuration should be represented as an array (or list) of n strings.
Each string has length n and represents one row of the board.
Character 'Q' represents a queen, and '.' represents an empty square.

Two configurations are considered different if they differ in at least one row string.

You may assume:

1 ≤ n ≤ 9 .

Example

Input:

n = 4

One valid output (order of configurations and rows does not matter):

[
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],

  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

In each configuration above, there are 4 queens on the board, and no two queens attack each other.

Generate all safe queen placements on board

Overview

Comments (0)