fork(2) download
copy 
  1. #include <iostream>
  2. #include <array>
  3.  
  4. template<constexpr int N = 8>
  5. class QueenProblemSolver {
  6. public:
  7. 	QueenProblemSolver() {
  8. 		for (auto& i : is_occupied_column) {
  9. 			i = false;
  10. 		}
  11.  
  12. 		for (auto& i : is_occupied_right_diagonal) {
  13. 			i = false;
  14. 		}
  15.  
  16. 		for (auto& i : is_occupied_left_diagonal) {
  17. 			i = false;
  18. 		}
  19.  
  20. 		placeQueen(0);
  21. 	}
  22.  
  23. private:	
  24. 	void placeQueen(int row) {
  25. 		for (auto col = 0; col < N; ++col) { // Iteratively try placing the row'th queen in every column
  26. 			auto right_diagonal = get_right_diagonal(row, col);
  27. 			auto left_diagonal = get_left_diagonal(row, col);
  28. 			if (!is_occupied_column[col]	// Column is not occupied by any other queen
  29. 				&& !is_occupied_right_diagonal[right_diagonal]	// Right diagonal is not occupied
  30. 				&& !is_occupied_left_diagonal[left_diagonal]	// Left diagonal is not occupied
  31. 			) {
  32. 				// row'th queen can be placed here
  33. 				placed_column_num[row] = col;
  34. 				is_occupied_column[col] = true;
  35. 				is_occupied_right_diagonal[right_diagonal] = true;
  36. 				is_occupied_left_diagonal[left_diagonal] = true;
  37.  
  38. 				if ((row + 1) < N) {	// Recursively place the (row + 1)'th queen
  39. 					placeQueen(row + 1);
  40. 				} else {	// N queens have been placed, so we have found a solution
  41. 					printSolution();
  42. 				}
  43.  
  44. 				// Clear the occupied flags since we have finished placing the queen at this position
  45. 				is_occupied_column[col] = false;
  46. 				is_occupied_right_diagonal[right_diagonal] = false;
  47. 				is_occupied_left_diagonal[left_diagonal] = false;
  48. 			}
  49. 		}
  50. 	}
  51.  
  52. 	void printSolution() {
  53. 		++count;
  54. 		std::cout << count << ": ";
  55.  
  56. 		// Print the occupied column in each row
  57. 		for (auto row = 0; row < N; ++row) {
  58. 			std::cout << placed_column_num[row] << " ";
  59. 		}
  60. 		std::cout << std::endl;
  61. 	}
  62.  
  63. 	inline static constexpr auto get_num_diagonals() {
  64. 		return (1 << N) - 1;
  65. 	}
  66.  
  67. 	inline int get_right_diagonal(int row, int col) const {
  68. 		return row + col;
  69. 	}
  70.  
  71. 	inline int get_left_diagonal(int row, int col) const {
  72. 		return get_left_diagonal_offset() + (row - col);
  73. 	}
  74.  
  75. 	inline constexpr auto get_left_diagonal_offset() const {
  76. 		return (1 << (N - 1)) - 2;
  77. 	}
  78.  
  79. 	std::array<int, N> placed_column_num;
  80. 	std::array<bool, N> is_occupied_column;
  81. 	std::array<bool, get_num_diagonals()> is_occupied_right_diagonal;
  82. 	std::array<bool, get_num_diagonals()> is_occupied_left_diagonal;
  83. 	int count{0};
  84. };
  85.  
  86. int main() {
  87. 	QueenProblemSolver<10> qp8;
  88. }
Compilation error #stdin compilation error #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:4:10: error: invalid declaration specifier in template non-type parameter
template<constexpr int N = 8>
         ^~~~~~~~~~
1 error generated.
stdout
copy 
Standard output is empty
https://ideone.com/YU11ym
N Queen Problem
language:
C++14 (clang 8.0)
created:
77 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!