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.
1 | Example: |
Solution
Analysis
8皇后问题. 各个皇后不能在同一行,不能在同一列,同时也不能在同一条对角线(正or斜).
对角线可以通过集合方法判断. x+y=a, 或者 x-y=a. 也就是说点a和点b,对应坐标差的绝对值不能相等.
这里的一个问题是,原始排版是空的,需要将最终内容拼接出来,而不是在原始内容上修改个别位置. 另外,位置有效性判断条件,我们可以稍作修改,筛选掉一部分:去掉行. 因为每次放完一个皇后之后,下一个位置一定是下一行, 跳过本行.
回溯,或者说递归,最终要的是终止条件.这里的终止条件是行号i==n,表示最后一行已经排完了,终止END.
遍历时,在当前行所有列位置进行尝试.
Codes
1 | class Solution { |