【第三轮】8.3-8.9 CareerCup 9.9

9.9 Write an algorithm to prim all ways of arranging eight queens on an 8x8 chess board so that none of them share the same row, column or diagonal. In this case,
"diagonal" means all diagonals, not just the two that bisect the board.


回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
传说中的八皇后，递归实现。
【时间复杂度】
O(N!)
【空间复杂度】
O(N!)
【gist link】
https://gist.github.com/dc77131096d73914c4e4

【解题思路】
for each row, traverse every column to see whether it meets the requirements.

【时间复杂度】
O(n^2)

【空间复杂度】
O(n)


【gist link】
https://gist.github.com/happyWinner/55b8bd163c266b16c4f8

【解题思路】
Recursion. Easy to generalize it to be N queens problem

【时间复杂度】
O(1) for eight queen
O(n^2) for n queen

【空间复杂度】
O(1) for eight queen
O(n) for n queen

【gist link】
https://gist.github.com/chrislukkk/1a06f5d153c8b2cf3d7e

【解题思路】Eight Queens, Fix one column, then search the next one, till find an valid combination
【时间复杂度】
O(N!)
【空间复杂度】
O(N!)
【gist link】
https://gist.github.com/bitcpf/ae50050120459bf50228