Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- bool is_valid(vector<int> candidate_solutions) {
- for (int i = 0; i < candidate_solutions.size(); i++) {
- for (int j = 0; j < i; j++) {
- if (candidate_solutions[i] == candidate_solutions[j]) {
- return false;
- }
- if (candidate_solutions[i - (j + 1)] == candidate_solutions[i] - (j + 1)) {
- return false;
- }
- if (candidate_solutions[i - (j + 1)] == candidate_solutions[i] + (j + 1)) {
- return false;
- }
- }
- }
- return true;
- }
- bool is_complete(vector<int> candidate_solutions, int current_row) {
- if (is_valid(candidate_solutions) && (candidate_solutions.size() - 1 == current_row)) {
- return true;
- }
- return false;
- }
- void print(vector<int> candidate_solutions) {
- for (int x : candidate_solutions) {
- cout << x << " ";
- }
- }
- bool pick_next_column(int& col, int grid_size) {
- if ((col + 1) < grid_size) {
- col++;
- return true;
- }
- return false;
- }
- int main() {
- int grid_size;
- cin >> grid_size;
- vector<int> candidate_solutions(grid_size);
- int k = 0;
- candidate_solutions[k] = -1;
- while (k >= 0) {
- if (pick_next_column(candidate_solutions[k], grid_size)) {
- if (is_complete(candidate_solutions, k)) {
- print(candidate_solutions);
- }
- else {
- if (is_valid(candidate_solutions)) {
- candidate_solutions[++k] = 0;
- }
- }
- }
- else {
- k--;
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment