bhuztez?，正在找工作 ... 韋易笑、?RednaxelaFX、?小白菜、?鋼盅郭子?等?517?人贊同 既然有人邀請我了，我就來了，解法參考?如何簡化求解八妃問題的代碼？ - 知乎用戶的回答

#include <iostream> #include <algorithm> #include <bitset> #include <numeric> #include <utility> int main() {for (int queens[] = {0,1,2,3,4,5,6,7}; ::std::next_permutation(queens,queens+8); )if ((::std::bitset<15>(::std::accumulate(queens,queens+8, ::std::make_pair(0, 0), [](::std::pair<int, int> a, int b){return ::std::make_pair((1<<(b+a.second))|a.first,a.second+1);}).first).count() == 8) && (::std::bitset<15>(::std::accumulate(queens, queens+8, ::std::make_pair(0, 0), [](::std::pair<int, int> a, int b){return ::std::make_pair((1<<(7+b-a.second))|a.first, a.second+1);}).first).count() == 8))::std::cout << queens[0] << queens[1] << queens[2] << queens[3] << queens[4] << queens[5] << queens[6] << queens[7] << ::std::endl; }
算上include，剛好十行，充分運(yùn)用了C++標(biāo)準(zhǔn)庫

你們這些連include都沒的，也好意思貼上來么？

現(xiàn)在問題來了，15K 的工作在哪里？

----------------------------------------------------------------------------
更新

J語言 49字符 (i.(([:*./"1[:(#=+/@:~:)"1(+,:-)"1)#])i.@:!A.i.)8 編輯于 2015-03-06?62 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 10贊同 反對，不會顯示你的姓名 朱沖喵?，{ 數(shù)學(xué)喵 | 計(jì)算機(jī)喵 } 10?人贊同 謝喵~
#include <iostream> int sum,ans[8]; int solve(int n, long long mark, int *ans){for (int i=n>8?++sum&0:0; n>8&&i<8; i!=7?std::cout << ans[i++] << " " : std::cout << ans[i++] << std::endl);for (int i=0; i<8; !(mark>>i&1)&&!(mark>>(n+i+7)&1)&&!(mark>>(n-i+30)&1)?solve(n+(ans[n-1]=i+1)-i, mark|1ll<<i|1ll<<(n+i+7)|1ll<<(n-i+30), ans):0,i++);return sum; } int main(){std::cout << solve(1, 0, ans) << std::endl; } 正好10行呢
輸出八皇后的所有方案和方案總數(shù),這樣就完整了,直接輸出92是不是在抖機(jī)靈呢?
使用位運(yùn)算來簡化行列攻擊判斷,mark的1-8位為列判斷,9-23與24-38位為對角線判斷.

//另:沒有main的,沒有include的,不能直接運(yùn)行的應(yīng)該不是嚴(yán)格符合題意吧.那這么說我solve函數(shù)也只有5行呢... (逃 編輯于 2015-03-21?1 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 104贊同 反對，不會顯示你的姓名 方志文 104?人贊同 這是要輸出一個可行解還是所有解的個數(shù)？如果是個數(shù)的話，之前在quora上看到大神解答。
#include <iostream>
int main() {?
std::cout << 92 << std::endl ;
return 0;
} 編輯于 2015-03-05?29 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 90贊同 反對，不會顯示你的姓名 藍(lán)色?，主業(yè)三流青春校園小說作家兼反差萌段子手… 90?人贊同 比行數(shù)有意思？
Python大法好
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
C++的話，隨隨便便就超過了，不過如果可以，呵呵... #include<iostream> 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;}
使用了心形在線生成網(wǎng)站:ImageChef - Visual Poetry for Facebook or Email Greetings

（娛樂貼） 編輯于 2015-03-05?13 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 199贊同 反對，不會顯示你的姓名 子飛?，上海己美網(wǎng)絡(luò)CEO 微信號: zifeizhong 199?人贊同 昨晚有朋友把這個問題在微信上直接發(fā)給我，說知乎上在吐槽你公司的面試，我趕忙注冊來回答。其實(shí)任何面試都不能完全考察一個人的能力。如果面試沒表現(xiàn)好，不要為你自己擔(dān)心，因?yàn)槟憧倳业礁玫牡胤秸故咀约骸?br />
我在美國UT-Austin念研究生的時(shí)候，暑假要找實(shí)習(xí)工作，去西雅圖微軟面試，被問到過八皇后問題。記得是2007年，面試官很nice。屋子里面有一個小黑板，很快黑板就被我寫滿了，但是代碼還沒寫完。我猶豫是否要把代碼擦掉重新寫。面試官說，就這樣結(jié)束吧，你知道用遞歸就很好了。顯然，我沒拿到offer。我后來反思了很久，修正了自我，終于搞定了5-6個offer，最后去了Google。

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

如果你能用簡練的代碼解決問題，你的面試官一般都是被你秒殺的。簡潔的代碼，意味著很多。有次我去Goldman Sachs，面試官給我了兩個算法題目二選一。他出去沖咖啡，回來時(shí)我把兩個題目都寫完了。當(dāng)然，我據(jù)掉了GS，因?yàn)槲液髞頉Q定回國創(chuàng)業(yè)了。

對于面試問題“用c++在10行內(nèi)寫出八皇后”，我期待是這樣的：

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

其次，確定什么樣的代碼算一行？為什么要規(guī)定10行？我會說10行只是一個指導(dǎo)性的目標(biāo)，真實(shí)的目的是希望代碼簡單明了。我們希望花更少的時(shí)間讀懂你的代碼。在工作中也是如此，你的隊(duì)員希望你的代碼簡練明了，一看就懂，最好沒有坑。如果非要算行數(shù)，那么單獨(dú)的“｛”是不用計(jì)算的，因?yàn)樾畔⒘亢苄　?br />
當(dāng)然了，能不能做出來不是最重要的。面試者如何approach這個問題很重要。
這個帖子里面的很多回復(fù)都很牛x，拜讀了之后感覺我大中華人才濟(jì)濟(jì)。希望大家不介意我打個小廣告：本公司含我在內(nèi)目前只有2名程序猿，需要大量的人才加入。公司的千萬級投資已在年前全部到位，歡迎大家來公司面試順帶拿維他命水喝。

最后，有人說不貼代碼都是耍流氓，所以也貼出我以前寫的代碼，還請大家輕點(diǎn)拍磚（得到n皇后的解及其個數(shù)，分別是iterative和recursive兩種方法）： 發(fā)布于 2015-03-06?36 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 98贊同 反對，不會顯示你的姓名 vczh?，專業(yè)造輪子，前排已拉黑。… 鋼盅郭子?等?98?人贊同

有維他命水還有什么不滿足，google都是叫人6點(diǎn)起床大老遠(yuǎn)跑google去，拖到中午才給你面試，還沒水的。顯然沒有把自己當(dāng)google。

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

隨便寫了一個，不保證對，剛好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); } 編輯于 2015-03-05?32 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 22贊同 反對，不會顯示你的姓名 Comzyh?，計(jì)算機(jī)專業(yè)在讀 22?人贊同 記得大一的時(shí)候匯編老師給我們吹牛，說他曾經(jīng)有個學(xué)生能一行寫出八皇后，之后再也沒人能寫出，我不服，然后寫了個給他，不過實(shí)在是搞不到一行去。
下面程序能夠編譯運(yùn)行，輸出8皇后解的數(shù)量。正好10行，沒有return 0；
#include <cstdio> 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\n", queen(0, 0, 0, 0)); } 編輯于 2015-03-06?13 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 11贊同 反對，不會顯示你的姓名 Yangff?，不要說你沒有女裝過，光著身子洗澡也是女… 11?人贊同 #include <cstdio> int main(){printf("...o....\n......o.\n..o.....\n.......o\n.o......\n....o...\no.......\n.....o..\n"); } 發(fā)布于 2015-03-05?4 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 9贊同 反對，不會顯示你的姓名 壯壯?，啊! 9?人贊同 位運(yùn)算簡介及實(shí)用技巧（三）：進(jìn)階篇(2)
Matrix67大牛寫的 人肉翻譯成C++就好了. 發(fā)布于 2015-03-05?1 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 1贊同 反對，不會顯示你的姓名 鴿子?，The programmer 1?人贊同 lisp的話10行足夠了
(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 mwhen (loop for row from 1 to nfor col in solutionalways (/= new-col col (+ col row) (- col row)))collect (cons new-col solution))))) 編輯于 2016-01-07?添加評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 4贊同 反對，不會顯示你的姓名 Kim Leo?，http://i2p.kimleo.net?微信公眾號：ki2mmy 4?人贊同 我覺的題主是來秀優(yōu)越的！
像?@vczh，面試都沒拿到過維他命水好伐！ 發(fā)布于 2015-03-05?添加評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 66贊同 反對，不會顯示你的姓名 蕭井陌?，微信公眾號：煉瓜研究所 技術(shù)社區(qū) … 66?人贊同 為啥你覺得自己可以10行內(nèi)寫出八皇后。。。
#include <eightqueen>int main(int argc, const char *argvp[]) {::eightQueen();return 0; }
8行寫的八皇后 發(fā)布于 2015-03-05?24 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 32贊同 反對，不會顯示你的姓名 江Bin vczh?等?32?人贊同 n皇后（1<=n<=10）問題的通用行數(shù)，9行解決。

//
/*

n皇后問題
1<=n<=10

Count=QUEENNUM*QUEENNUM-1；
Num=QUEENNUM;
Attack=0;



*/

#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( ((CulAttack&Attack)!=0) ) return NQueen(Count-1,Num,Attack);


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

}

//

如果僅需解決8皇后問題，那就更簡單了
int EightQueen()
{
return 92;
}


//
程序說明
-- 如果糾結(jié)于皇后之間不能互相攻擊，10行內(nèi)是搞不定的，必須轉(zhuǎn)換問題

對n皇后問題
定義1： 建立(n+2)*(n+2)的棋盤，其中最外圍成為壁，共有4*（n+1）個節(jié)點(diǎn)，稱為壁節(jié)點(diǎn)
定義2： 每個皇后定義4種攻擊方式：-- | \ / (橫線，豎線，左斜線，右斜線)。

定理1： 每個皇后對壁節(jié)點(diǎn)攻擊8次，每一種攻擊各兩次。

推論：

情況1： 任意兩個皇后之間不能相互攻擊
情況2： 任意一個壁節(jié)點(diǎn)最多承受4次方式不同攻擊
當(dāng)棋盤中存在n個皇后時(shí)，情況1 為 情況2 的充分必要條件。

結(jié)論：
僅需要判斷每個壁節(jié)點(diǎn)的攻擊方式不重復(fù)即可。

優(yōu)化：
由于每個皇后攻擊的壁節(jié)點(diǎn)對稱，因此每種攻擊僅需一半的攻擊節(jié)點(diǎn)。
-- n
| n
\ 2*n
/ 2*n

程序思想：
1. 將n*n的棋盤編號，0 -- n*n-1
2. 判斷，當(dāng)皇后處于位置i時(shí)，其4種攻擊方式所攻擊的壁節(jié)點(diǎn)編號
3. 若某壁節(jié)點(diǎn)已經(jīng)被攻擊，則皇后不得處于該位置
4. 若無壁節(jié)點(diǎn)被重復(fù)攻擊，則皇后可能處于該位置
5. 采用bit位標(biāo)注，最大為64bit，因此該函數(shù)最多能夠解決到10皇后問題
//

感謝：
1. 題主的問題，若不存在這一限制，不會這么想，還是挺有意思的。
2.?@vczh?的代碼提供了靈感。 編輯于 2015-03-07?添加評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 19贊同 反對，不會顯示你的姓名 Kenneth?，精通C艸，不，被C艸 19?人贊同 把換行符替換成空格。 發(fā)布于 2015-03-05?3 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 13贊同 反對，不會顯示你的姓名 沈兄 13?人贊同 e
i
g
h
t
q
u
e
e
n

ps 不要在意單數(shù)啦～ 發(fā)布于 2015-03-05?1 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 21贊同 反對，不會顯示你的姓名 李小明?，喜愛多種運(yùn)動。 21?人贊同 你不會不換行嗎。 發(fā)布于 2015-03-05?5 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 21贊同 反對，不會顯示你的姓名 Adder?，不明白你們?yōu)槭裁聪嘈胚壿?/span> 21?人贊同 本來想說故意不換行算什么本事，結(jié)果寫完發(fā)現(xiàn)已經(jīng)10+了……好憂傷
update：左大括號左邊不換行了哈哈哈……還是多一行啊……
update：我不做人……啊不對不寫return 0了，10行。
#include <cstdio> int dfs(int r, int p1, int p2) {int ret = 0, pos = ((1<<8)-1) & ~(r|p1|p2);for (int k = pos & (-pos); pos; pos -= k, k = pos & (-pos))ret += dfs(r+k, (p1+k)<<1, (p2+k)>>1);return r+1 == (1<<8) ? 1 : ret; } int main() {printf("%d\n", dfs(0,0,0)); } 編輯于 2015-03-05?11 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 2贊同 反對，不會顯示你的姓名 李寒?，Programmer 2?人贊同 #include <stdio.h> #define LOWBIT(x) x&(-x) int solve(int c, int lc, int rc, int sum) {if(c == 0xFF) return sum + 1;for (int pos = ((c | lc | rc)&0xFF)^0xFF; pos; pos&=(~(LOWBIT(pos)))) {sum = solve(c|LOWBIT(pos), (lc|LOWBIT(pos))<<1, (rc|LOWBIT(pos))>>1, sum);}return sum; } int main() { printf("%d\n", solve(0, 0, 0, 0)); }
$ gcc -std=gnu99 -o 8 8.c && ./8 92
可以更短！ 編輯于 2015-03-05?添加評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 13贊同 反對，不會顯示你的姓名 賈川川?，寫過一些帶class的C 13?人贊同 #include<stdio.h> int main() { int i=0, j=0, s=0, v=0, l=0, k=0; int a[100]; for( scanf("%d",&s); *a-s; v=a[j*=v]-a[i],k=i<s,j+=(v=j<s&&(!k&&!!printf(2+"\n\n%c"-(!l<<!j),"**Q"[l^v?(l^j)&1:2])&&++l||a[i]<s&&v&&v-i+j&&v+i-j&&v+i-j))&&!(l%=s),v||(i==j?a[i+=k]=0:++a[i])>=s*k&&++a[--i]); return 0; } 純C--from ioccc
輸入8試試?

-----------------------------------------------------------------------------------------------------------------------------
更新一下好了 反正沒人看見：
知乎真是娛樂至死
最高票說得對 include都沒有你也好意思貼出來？ 編輯于 2016-02-22?11 條評論?感謝? 分享 ?收藏???沒有幫助???舉報(bào)???作者保留權(quán)利 曙方?，東南形勝，止于至善 8?人贊同 如果只寫核心的話10行基本夠了，因?yàn)榭隙ú粫谕恍?#xff0c;同一列，只需要判斷對角線就好。
int queens (){int pos[] = {0,1,2,3,4,5,6,7},ans = 0;while(next_permutation(pos,pos+8)){bool ok = true;for(int* p = pos;p<pos+8;p++)if ( count_if(pos,p,[=](int& j){return p - &j == *p-j || p - &j == j - *p ;}) )ok = false;ans += ok;}return ans; }

一共92個解。
運(yùn)行結(jié)果?http://ideone.com/cjee0Y
from:?https://www.zhihu.com/question/28543312#answer-11874244

總結(jié)

以上是生活随笔為你收集整理的如何用 C++ 在 10 行内写出八皇后？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。