[1]位运算处理八皇后问题LeetCode
总体思路具体实现
题目链接：https://leetcode-cn.com/problems/n-queens/
总体思路
首先用到了一个int（姑且称之为伪数组）来存储可放置的位置，自然有其好处，省去了繁杂的创建数组的过程，并且便于用位运算进行顺次约束。分为三个约束条件，姑且用line，knife以及fork代替，分别用于，列约束，左斜约束，右斜约束（擅自命名，顺便帮自己记下“左手拿叉，右手拿刀”。 八皇后离不开深度优先搜索，为了思路更加清晰，将生成输出部分抽象为一个generateBoard函数，将生成可行解的部分抽象为一个solve函数，并且用solveNQueen连接两者。 每次深度搜索时，先判断是否为零，若为零，则意味着此时可以终止深度搜索。若不为零，则取得位数最低的一个零1进行下一步的深度搜索，回溯时将其置1，避免死循环。 生成部分，首先全部置’.’,然后根据solutions将放置皇后处置’Q’。 用到了高效率位运算： •int __builtin_ctz (unsigned int x) 返回x的二进制下末尾的0的个数
具体实现
class Solution {
public:
vector
<vector
<string
>> solveNQueens(int n
) {
auto solutions
= vector
<vector
<string
>>();
auto queens
= vector
<int
>(n
, -1);
solve(solutions
, queens
, n
, 0, 0, 0, 0);
return solutions
;
}
void solve(vector
<vector
<string
>> &solutions
, vector
<int
> &queens
, int n
, int row
, int line
, int knife
, int fork
) {
if (row
== n
) {
auto board
= generateBoard(queens
, n
);
solutions
.push_back(board
);
} else {
int availablePositions
= ((1 << n
) - 1) & (~(line
| knife
| fork
));
int
& ap
=availablePositions
;
while (ap
!= 0) {
int position
= ap
& (-ap
);
ap
= ap
& (ap
- 1);
int column
= __builtin_ctz(position
);
queens
[row
] = column
;
solve(solutions
, queens
, n
, row
+ 1, line
| position
, (knife
| position
) >> 1, (fork
| position
) << 1);
queens
[row
] = -1;
}
}
}
vector
<string
> generateBoard(vector
<int
> &queens
, int n
) {
auto board
= vector
<string
>();
for (int i
= 0; i
< n
; i
++) {
string row
= string(n
, '.');
row
[queens
[i
]] = 'Q';
board
.push_back(row
);
}
return board
;
}
};
