Guest User

Untitled

a guest
Oct 16th, 2017
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. bool is_valid(vector<int> candidate_solutions) {
  7. for (int i = 0; i < candidate_solutions.size(); i++) {
  8. for (int j = 0; j < i; j++) {
  9. if (candidate_solutions[i] == candidate_solutions[j]) {
  10. return false;
  11. }
  12. if (candidate_solutions[i - (j + 1)] == candidate_solutions[i] - (j + 1)) {
  13. return false;
  14. }
  15. if (candidate_solutions[i - (j + 1)] == candidate_solutions[i] + (j + 1)) {
  16. return false;
  17. }
  18. }
  19. }
  20. return true;
  21. }
  22.  
  23. bool is_complete(vector<int> candidate_solutions, int current_row) {
  24. if (is_valid(candidate_solutions) && (candidate_solutions.size() - 1 == current_row)) {
  25. return true;
  26. }
  27. return false;
  28. }
  29.  
  30. void print(vector<int> candidate_solutions) {
  31. for (int x : candidate_solutions) {
  32. cout << x << " ";
  33. }
  34. }
  35.  
  36. bool pick_next_column(int& col, int grid_size) {
  37. if ((col + 1) < grid_size) {
  38. col++;
  39. return true;
  40. }
  41. return false;
  42. }
  43.  
  44. int main() {
  45. int grid_size;
  46. cin >> grid_size;
  47. vector<int> candidate_solutions(grid_size);
  48. int k = 0;
  49. candidate_solutions[k] = -1;
  50. while (k >= 0) {
  51. if (pick_next_column(candidate_solutions[k], grid_size)) {
  52. if (is_complete(candidate_solutions, k)) {
  53. print(candidate_solutions);
  54. }
  55. else {
  56. if (is_valid(candidate_solutions)) {
  57. candidate_solutions[++k] = 0;
  58. }
  59. }
  60. }
  61. else {
  62. k--;
  63. }
  64. }
  65. return 0;
  66. }
Add Comment
Please, Sign In to add comment