Finally, I have some time to revisit the N queens problem using bit operations.
The following functions could solve 11 queens in 1 second:
|
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 49 50 51 52 53 54 55 56 57 58 59 60 |
class Solution { public: vector<vector<string>> solveNQueens(int n) { NQresult.clear(); NQpath.clear(); NQn = n; NQtotal = 0; bitNQueens(0, 0, 0); cout << NQtotal << endl; return NQresult; } private: /** [Q..... row = 101010 ..Q... ld = 100100 ....Q. rd = 000111 ......] or = 101111 pos = 010000 => p = (010000) & (110000) = 010000 => pos = 0; [Q..... row = 111010 ..Q... ld = 011000 ....Q. rd = 000111 .Q....] **/ vector<vector<string>> NQresult; vector<int> NQpath; int NQtotal; int NQn; void addNQueenSolution() { vector<string> v; for (int i = 0; i < NQn; ++i) v.push_back(string(NQn, '.')); for (int i = 0; i < NQn; ++i) { v[i][NQpath[i]] = 'Q'; //cout << v[i] << endl; } //cout << endl; NQresult.push_back(v); } // col: whether this col is occupied // ld: left diagnal for the current row // rd: right diagnal for the current row void bitNQueens(int col, int ld, int rd) { int allOccupied = (1 << NQn) - 1; if (col == allOccupied) { ++NQtotal; addNQueenSolution(); return; } int pos = allOccupied & (~(col | ld | rd)); while (pos != 0) { int p = pos & (-pos); // which way to go pos = pos - p; // get the rightmost 1 of position position NQpath.push_back(p == 1 ? 0 : (int)round(log(p) / log(2))); bitNQueens(col + p, (ld + p) << 1, (rd + p) >> 1); NQpath.pop_back(); } } }; |
So far to me, this is the most efficient algorithm for N queens.
The code is mostly self-explenary. Please comment if anything cannot be understood.
|
1 2 3 |
// col: whether this col is occupied // ld: left diagnal for the current row // rd: right diagnal for the current row |
