Difference between revisions of "CodeArchive NQueen"
From Ubcacm
(→N Queen Problem) |
|||
Line 21: | Line 21: | ||
} | } | ||
</pre> | </pre> | ||
− | + | check | |
-- Main.MatthewChan - 25 Nov 2005 | -- Main.MatthewChan - 25 Nov 2005 |
Latest revision as of 00:28, 7 February 2007
N Queen Problem
O(n) formula-style solution. Algorithm/Formulae from wiki N-queens problem, code from Main.YuryKholondyrev
vector < int > get_queens(int n){ // WARNING: there is no solution for n = 2, 3 if(n == 1) return vector < int > (1, 1); int r = n%12; vector < int > out; for(int i = 2; i <= n; i += 2) out.push_back(i); if(r == 3 || r == 9) for(int i = 0; i + 1 < (int)out.size(); i++) swap(out[i], out[i + 1]); int s = out.size(); for(int i = 1; i <= n; i += 2) out.push_back(i); if(r == 8) for(int i = s; i + 1 < n; i += 2) swap(out[i], out[i + 1]); if(r == 2){ swap(out[s], out[s + 1]); // 1 <-> 3 for(int i = s + 2; i + 1 < n; i++) swap(out[i], out[i + 1]); } if(r == 3 || r == 9) for(int k = 0; k < 2; k++) for(int i = s; i + 1 < n; i++) swap(out[i], out[i + 1]); return out; }
check -- Main.MatthewChan - 25 Nov 2005