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

nqueens.cpp 2.8KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string.h>
  5. #define NQUEENS 8
  6. using namespace std;
  7. // class with minimal object abstraction
  8. class Board
  9. {
  10. public:
  11. // make these public so we don't clutter this with accessors.
  12. // verbs, not nouns. simplicity.
  13. int size;
  14. int* queens;
  15. int* occupiedrows;
  16. Board(int board_size)
  17. {
  18. // populate stuff
  19. this->size = board_size;
  20. queens = new int[board_size];
  21. occupiedrows = new int[board_size];
  22. for(int i=0;i<board_size;i++){
  23. queens[i]=0;
  24. occupiedrows[i]=0;
  25. }
  26. };
  27. ~Board()
  28. {
  29. delete [] queens;
  30. delete [] occupiedrows;
  31. }
  32. string toString()
  33. {
  34. string s = "";
  35. s += to_string(this->queens[0]);
  36. for(int i=1; i<this->size; i++) {
  37. s += " " + to_string(this->queens[i]);
  38. }
  39. return s;
  40. }
  41. void choose(int row, int col)
  42. {
  43. if(col < this->size && row < this->size) {
  44. this->queens[col] = row;
  45. this->occupiedrows[row] = 1;
  46. }
  47. }
  48. void unchoose(int row, int col)
  49. {
  50. if(col < this->size && row < this->size) {
  51. this->queens[col] = 0;
  52. this->occupiedrows[row] = 0;
  53. }
  54. }
  55. };
  56. // class that performs minimal amount of wrapping around built-in types
  57. // SolutionSaver is a static class
  58. class SolutionSaver
  59. {
  60. private:
  61. vector<string> solutions;
  62. int nsolutions;
  63. public:
  64. static SolutionSaver& getInstance()
  65. {
  66. static SolutionSaver instance;
  67. return instance;
  68. }
  69. void saveSolution(string serialized){
  70. solutions.push_back(serialized);
  71. nsolutions++;
  72. }
  73. void printNumSolutions() {
  74. cout << nsolutions << endl;
  75. }
  76. void printSolutions() {
  77. for(vector<string>::iterator it = solutions.begin(); it != solutions.end(); it++) {
  78. cout << "Solution: " << (*it) << endl;
  79. }
  80. cout << endl;
  81. }
  82. private:
  83. SolutionSaver(){
  84. nsolutions = 0;
  85. };
  86. SolutionSaver(SolutionSaver const&);
  87. };
  88. void explore(Board* b, int col)
  89. {
  90. if(col>=b->size)
  91. {
  92. // Base case
  93. SolutionSaver * s = &SolutionSaver::getInstance();
  94. s->saveSolution(b->toString());
  95. } // Done with base case
  96. else
  97. {
  98. // Recursive case
  99. int size = b->size;
  100. int* attacked = new int[size];
  101. int* occupied = b->occupiedrows;
  102. for(int k=0; k<=(col-1); k++) {
  103. // attacked on lower right diag
  104. int ix1 = b->queens[k] + col - k;
  105. if(ix1 >= 0 && ix1 < b->size) {
  106. attacked[ix1] = 1;
  107. }
  108. // attacked on upper right diag
  109. int ix2 = b->queens[k] - col + k;
  110. if(ix2 >= 0 && ix2 < b->size) {
  111. attacked[ix2] = 1;
  112. }
  113. }
  114. for(int row=0; row<b->size; row++ ) {
  115. if(occupied[row]!=1 && attacked[row]!=1) {
  116. b->choose(row,col);
  117. explore(b,col+1);
  118. b->unchoose(row,col);
  119. }
  120. }
  121. }// Done with recursive case
  122. };
  123. int main(void)
  124. {
  125. Board b(NQUEENS);
  126. explore(&b,0);
  127. SolutionSaver * s = &SolutionSaver::getInstance();
  128. s->printNumSolutions();
  129. }