如何用 C++ 在 10 行內寫出八皇后？

from itertools import *
cols = range(8)
for vec in permutations(cols):
if (8 == len(set(vec[i]+i for i in cols))
== len(set(vec[i]-i for i in cols))):
print vec


#include&
using namespace std;int position[8];bool isSafe(int queen_number, int row_position) {for (int i = 0; i &< queen_number; i++) {int other_row_pos = position[i];if (other_row_pos == row_position ||other_row_pos == row_position - (queen_number - i) ||other_row_pos == row_position + (queen_number - i))return false;}return true;}void solve(int k){if (k == 8){for (int i = 0; i &< 8; i++)cout &<&< position[i] &<&< " ";cout &<&< endl;}else{for (int i = 0; i &< 8; i++){if (isSafe(k, i)){position[k] = i;solve(k + 1);}}}}int main(){ solve(0);return 0;}

n皇后（1&<=n&<=10）問題的通用行數，9行解決。

//////////////////////////////////////////////////////////////////////////////////////////////

n皇后問題

Count=QUEENNUM*QUEENNUM-1；

*/

#define QUEENNUM 2

int NQueen( int Count,int Num,__int64 Attack )

{

__int64 ONE=1;

if( (Num==0) || ( Count==-1) ) return (Num==0)?1:0;

__int64 CulAttack= (ONE&<&<(Count/QUEENNUM) ) | ((ONE&<&<((Count%QUEENNUM))+QUEENNUM)) | (ONE&<&<(QUEENNUM*2+(QUEENNUM+Count%QUEENNUM-Count/QUEENNUM))) | (ONE&<&<(QUEENNUM*4+(Count/QUEENNUM+Count%QUEENNUM)));

if( ((CulAttackAttack)!=0) ) return NQueen(Count-1,Num,Attack);

return NQueen(Count-1,Num,Attack)+NQueen(Count-1,Num-1,Attack|CulAttack);

}

//////////////////////////////////////////////////////////////////////////////////////////////

如果僅需解決8皇后問題，那就更簡單了

//////////////////////////////////////////////////////////////////////////////////////////////

程序說明

對n皇后問題

定理1： 每個皇后對壁節點攻擊8次，每一種攻擊各兩次。

推論：

情況1： 任意兩個皇后之間不能相互攻擊

結論：

優化：

有維他命水還有什麼不滿足，google都是叫人6點起床大老遠跑google去，拖到中午才給你面試，還沒水的。顯然沒有把自己當google。

google是我人生中見到的唯一一個，會把一整天要面試的人，都讓你早上到公司然後慢慢等的，簡直不把來面試的當人看。

隨便寫了一個，不保證對，剛好8行。被人提醒了好像沒考慮斜線，反正原理差不多，不想寫了……

int 八皇后(uint64_t current = 0, uint64_t remains = 8, uint64_t rows = 0, uint64_t columns = 0) {
if (remains == 0) if (rows == 0x0101010101010101UL columns == 0x0101010101010101UL)
return 1;
if (current == 64) return 0;
uint64_t newRows = rows | 1 &<&< (current % 8 * 8); uint64_t newColumns = columns | 1 &<&< (current / 8 * 8); return 八皇后(current+1, remains-1, newRows, newColumns) + 八皇后(current+1, remains, rows, columns); }

昨晚有朋友把這個問題在微信上直接發給我，說知乎上在吐槽你公司的面試，我趕忙註冊來回答。其實任何面試都不能完全考察一個人的能力。如果面試沒表現好，不要為你自己擔心，因為你總會找到更好的地方展示自己。

我在美國UT-Austin念研究生的時候，暑假要找實習工作，去西雅圖微軟面試，被問到過八皇后問題。記得是2007年，面試官很nice。屋子裡面有一個小黑板，很快黑板就被我寫滿了，但是代碼還沒寫完。我猶豫是否要把代碼擦掉重新寫。面試官說，就這樣結束吧，你知道用遞歸就很好了。顯然，我沒拿到offer。我後來反思了很久，修正了自我，終於搞定了5-6個offer，最後去了Google。

八皇后是上編程第一堂課就接觸的，為啥搞不定呢？我反思後的自我修正是：代碼一定要夠簡練，否則很難把它在短時間內清晰地呈現給別人。我後來發現大多數演算法題目，核心代碼都不超過20行。

如果你能用簡練的代碼解決問題，你的面試官一般都是被你秒殺的。簡潔的代碼，意味著很多。有次我去Goldman Sachs，面試官給我了兩個演算法題目二選一。他出去沖咖啡，回來時我把兩個題目都寫完了。當然，我據掉了GS，因為我後來決定回國創業了。

對於面試問題「用c++在10行內寫出八皇后」，我期待是這樣的：

第一，這個問題有很多細節沒有說，所以要clarify問題。那麼就是向面試官發問，比如：8皇后的解怎麼輸出？我會告訴你，我們只要求輸出解的個數，其實，我們想要的是n皇后，對於任意一個n的值，我們要求輸出解的個數。n=1,輸出1; n=2, 輸出0; ...; n=8，輸出92; ...

其次，確定什麼樣的代碼算一行？為什麼要規定10行？我會說10行只是一個指導性的目標，真實的目的是希望代碼簡單明了。我們希望花更少的時間讀懂你的代碼。在工作中也是如此，你的隊員希望你的代碼簡練明了，一看就懂，最好沒有坑。如果非要算行數，那麼單獨的「｛」是不用計算的，因為信息量很小。

當然了，能不能做出來不是最重要的。面試者如何approach這個問題很重要。

import base64
exec(base64.b64decode("ZnJvbSBpdGVydG9vbHMgaW1wb3J0ICoKY29scyA9IHJhbmdlKDgpCmZvciB2ZWMgaW4gcGVybXV0YXRpb25zKGNvbHMpOgogICAgaWYgKDggPT0gbGVuKHNldCh2ZWNbaV0raSBmb3IgaSBpbiBjb2xzKSkKICAgICAgICAgID09IGxlbihzZXQodmVjW2ldLWkgZm9yIGkgaW4gY29scykpKToKICAgICAgICBwcmludCB2ZWM="))


感謝 @藍色的代碼

int col[15], sum[15], _diff[15], *diff = _diff + 8, ans[15];

void dfs(int r) {
if (r == 9) {
for (int i = 1; i &<= 8; ++i) { cout &<&< ans[i] &<&< " "; } cout &<&< endl; } for (int c = 1; c &<= 8; ++c) { if (col[c] == 0 sum[r + c] == 0 diff[r - c] == 0) { col[c] = sum[r + c] = diff[r - c] = 1; ans[r] = c; dfs(r + 1); col[c] = sum[r + c] = diff[r - c] = 0; } } }

int totalNQueens(int n) {
int upperlim = (1 &<&< n) - 1, sum = 0; std::function& dfs = [](int row, int l, int r) {
if (row == upperlim) { ++sum; return; }
for (int cur = upperlim (~(row|l|r)), pos = 0; cur; dfs(row+pos, (l+pos)&<&<1, (r+pos)&>&>1)) {
pos = cur (-cur);
cur -= pos;
}
};
dfs(0, 0, 0);
return sum;
}


(defun queens (n optional (m n))
(if (zerop n)
(list nil)
(loop for solution in (queens (1- n) m)
nconc (loop for new-col from 1 to m
when (loop for row from 1 to n
for col in solution
always (/= new-col col (+ col row) (- col row)))
collect (cons new-col solution)))))


#include &

return 0;
}


#include &
int main(){
printf("...o....
......o.
..o.....
.......o
.o......
....o...
o.......
.....o..
");
}


int n=0;

void NQ(int l, int d, int r)

{

for (int v = ~(l|d|r); int c = v-v; v-=c)

{

if (~(d|c) == 0)

n++;

else

NQ((l|c)&<&<1, d|c, (r|c)&>&>1);

}

}

int main()

{

NQ(0,-1&<&<8,0);

printf("%d", n);

}

這是我根據Matrix大神的程序,改寫成C語言的版本,N皇后(N&<=32)問題的通解.

如果只算有內容的行,正好10行.

解釋一下:

所有的變數(n除外)都表示棋盤上的一行.變數中的一位表示棋盤上的一格.

l是上面幾行的皇后向左下發出的射線佔據的位置.

d是上面幾行的皇后向下發出的射線佔據的位置.

r是上面幾行的皇后向右下發出的射線佔據的位置.

l|d|r是被上面的皇后威脅的位置.

v = ~(l|d|r)是這行可放皇后的位置

c = v-v從可以放皇后的位置中取出最右邊一位

v-=c去除遍歷過的位

~(d|c) == 0表示每一列都有皇后了,那就是找到一個解.

NQ((l|c)&<&<1, d|c, (r|c)&>&>1);表示把向左下,下,右下的射線延伸一格,加上本行的皇后發出的射線.

NQ(0,-1&<&<8,0);表示一開始就標記了只有右邊8列是可用的.要求解N皇后問題,只需把8換成N.

#include &
int queen(int l, int r, int m, int k){
int ans = 0;
for (int i = (~(l | r | m)) 0xff; i; i -= i -i)
ans += queen((l | (i -i)) &<&< 1, (r | (i -i)) &>&> 1 , m | (i -i), k + 1);
return k == 8 ? 1 : ans;
}
int main(){
printf("%d
", queen(0, 0, 0, 0));
}


姿勢水平不夠啊，33行才寫完