CodeArchive NQueen

From Ubcacm
Jump to: navigation, search

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