PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[心得] 8 queens 之 92種位置 - 7, 8, 9奧義

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間16年前 (2008/10/10 23:52)推噓1(1推 0噓 1→)

留言2則, 1人參與討論串1/1

今天寫ACM Q167時, 看到測資是從1排到64, 突然想到的求92種位置的方法也許很多人以前就有用了, 也許很多人有更快的做法不過因為是自己想到的心得 - 7, 8 ,9 奧義, 分享給大家 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 48 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 如果在4擺放queen 同一列就不用說了別列來說, 18, 20, 22都會被吃掉 (18 - 4) % 7 = 0 (18 - 4) / 7 = 3 - 1 兩條件同時成立來判斷不合法的擺放奧義 8, 9 是同樣道理所以92種位置的做法就可以用以下2函式來達成 inline bool isSet(const int &p, const int &size, const vector<int> &index) { bool isLegal = true; for(int i = size - 1; i >= 0; --i) { int result = (size * 8 + p) - index[i]; if(result % 7 == 0) { if(result / 7 == size - i) { isLegal = false; break; } } if(result % 8 == 0) { if(result / 8 == size - i) { isLegal = false; break; } } if(result % 9 == 0) { if(result / 9 == size - i) { isLegal = false; break; } } } return isLegal; } inline void EightQueensPositions(vector<vector<int> > &p) { p.clear(); vector<int> index(8, 0); //eight queens simulate... vector<int> q_index(8, 0); int now_line = 0; while(true) { while(q_index[now_line] == 8) { --now_line; if(now_line < 0) break; ++q_index[now_line]; } if(now_line < 0) break; if(isSet(q_index[now_line], now_line, index) == true) { index[now_line] = now_line * 8 + q_index[now_line]; ++now_line; if(now_line != 8) q_index[now_line] = 0; } else ++q_index[now_line]; if(now_line == 8) { p.push_back(index); --now_line; ++q_index[now_line]; } } } 有了這92種擺法的所有位置, 解Q167就可以AC 0.000 Bleed -- ACM's PARADISE http://bleed1979.myweb.hinet.net/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.16.70