N Queens Puzzle #2554
Description
Is your feature request related to a problem? Please describe.
Given a N x N chess board. Return all arrangements in which N queens can be placed on the board such no two queens attack each other.
Ex. N = 6
Solution= There are 4 possible ways
Arrangement: 1
".Q....",
"...Q..",
".....Q",
"Q.....",
"..Q...",
"....Q."
Arrangement: 2
"..Q...",
".....Q",
".Q....",
"....Q.",
"Q.....",
"...Q.."
Arrangement: 3
"...Q..",
"Q.....",
"....Q.",
".Q....",
".....Q",
"..Q..."
Arrangement: 4
"....Q.",
"..Q...",
"Q.....",
".....Q",
"...Q..",
".Q...."
Describe the solution you'd like
This can be solved using backtracking in below steps
- Start with first column and place queen on first row
- Try placing queen in a row on second column
- If placing second queen in second column attacks any of the previous queens, change the row in second column
- otherwise move to next column and try to place next queen
- In case if there is no rows where a queen can be placed such that it doesn't attack previous queens, then go back to previous column and change row of previous queen.
- Keep doing this until last queen is not placed safely.
- If there is no such way then return an empty list as solution
Describe alternatives you've considered
Brute Force approach:
- Generate all possible arrangement to place N queens on N*N board.
- Check each board if queens are placed safely.
- If it is safe, include arrangement in solution set. Otherwise ignore it
Problem with this approach
- But this will lead to an exponential number of arrangement. Which will be too slow to run.
Additional context
No