N-Queens

Problem

The n-queens 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 n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

---

Idea

合法的queue放置

当前放置位置的同一行、同一列、两条对角线上都不存在皇后

数组state[i]记录第i行皇后在哪一列

判断列是否冲突，只需要看state数组中state[0…k-1] 是否有和state[k]相等；

判断对角线是否冲突：如果两个皇后在同一对角线，那么|row1-row2| = |column1 - column2|，（row1，column1），（row2，column2）分别为冲突的两个皇后的位置

---

Solution

---