LeetCode 51. NQueens
撰写于 20171107 修改于 20171107 分类 LeetCode
Question
The nqueens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the nqueens puzzle.
Each solution contains a distinct board configuration of the nqueens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],
[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
Solution
It is a classical algorithm problem but it is not easy for newbies. To tackle this problem, we can go row by row, and in each position on each row, we can check if the current position is safe to place. So the rules are
 if there are no Queens in vertical and horizontal direction, it is safe
 if there are no Queens in 45 diagonal direction, it is safe
 if there are no Queens in 135 diagonal direction, it is safe
And if there are no positions safe to place a Queen, return to the previous row and move onward to choose a new position in that row.
And you can watch this videoN Queen Problem Using Backtracking Algorithm on YouTube to know more about NQueen problems.
Accepted Code


Note that in Python, if you want to deep copy a list, try my_list[:]
by slicing it.