Solve, time, and profile programs solving the N queens problem in various languages. Solution relies on built-in integer array types.

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145 ``````#include #include #include #include #define NQUEENS 8 using namespace std; // class with minimal object abstraction class Board { public: // make these public so we don't clutter this with accessors. // verbs, not nouns. simplicity. int size; int* queens; int* occupiedrows; Board(int board_size) { // populate stuff this->size = board_size; queens = new int[board_size]; occupiedrows = new int[board_size]; for(int i=0;iqueens[0]); for(int i=1; isize; i++) { s += " " + to_string(this->queens[i]); } return s; } void choose(int row, int col) { if(col < this->size && row < this->size) { this->queens[col] = row; this->occupiedrows[row] = 1; } } void unchoose(int row, int col) { if(col < this->size && row < this->size) { this->queens[col] = 0; this->occupiedrows[row] = 0; } } }; // class that performs minimal amount of wrapping around built-in types // SolutionSaver is a static class class SolutionSaver { private: vector solutions; int nsolutions; public: static SolutionSaver& getInstance() { static SolutionSaver instance; return instance; } void saveSolution(string serialized){ solutions.push_back(serialized); nsolutions++; } void printNumSolutions() { cout << nsolutions << endl; } void printSolutions() { for(vector::iterator it = solutions.begin(); it != solutions.end(); it++) { cout << "Solution: " << (*it) << endl; } cout << endl; } private: SolutionSaver(){ nsolutions = 0; }; SolutionSaver(SolutionSaver const&); }; void explore(Board* b, int col) { if(col>=b->size) { // Base case SolutionSaver * s = &SolutionSaver::getInstance(); s->saveSolution(b->toString()); } // Done with base case else { // Recursive case int size = b->size; int* attacked = new int[size]; int* occupied = b->occupiedrows; for(int k=0; k<=(col-1); k++) { // attacked on lower right diag int ix1 = b->queens[k] + col - k; if(ix1 >= 0 && ix1 < b->size) { attacked[ix1] = 1; } // attacked on upper right diag int ix2 = b->queens[k] - col + k; if(ix2 >= 0 && ix2 < b->size) { attacked[ix2] = 1; } } for(int row=0; rowsize; row++ ) { if(occupied[row]!=1 && attacked[row]!=1) { b->choose(row,col); explore(b,col+1); b->unchoose(row,col); } } }// Done with recursive case }; int main(void) { Board b(NQUEENS); explore(&b,0); SolutionSaver * s = &SolutionSaver::getInstance(); s->printNumSolutions(); }``````