Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- bool is_valid(const vector<int>& cols, int row) {
- for (int i=0; i<row; ++i) {
- if (cols[i] == cols[row] || abs(cols[i]-cols[row]) == row-i)
- return false; //clash horizontal or diagonal
- }
- return true;
- }
- vector<vector<string>> solveNQueens(int n) {
- //using backtracking iteratively
- vector<vector<string>> ret;
- vector<int> cols(n, 0);
- int row = 0;
- while (true) {
- if (row == n) { //valid complete board
- //compose string vector for board and add to ret
- vector<string> board;
- string line(n, '.');
- for (int pos : cols) {
- line[pos] = 'Q';
- board.push_back(line);
- line[pos] = '.';
- }
- ret.push_back(board);
- //continue search by going to last row and incrementing last queen
- cols[--row]++;
- }
- else if (cols[row] == n) { //end of row
- cols[row--] = 0; //reset queen position and move back one row
- if (row == -1) break; //finished. let's break out
- cols[row]++; //move queen forward one position.
- }
- else if (!is_valid(cols, row))
- cols[row]++; //not valid, so move queen forward one position
- else
- row++; //valid, so go to next row.
- }
- return ret;
- }
- void print_grids(const vector<vector<string>>& grids) {
- for (const vector<string>& grid : grids) {
- for (const string& line : grid)
- cout << line << "\n";
- cout << "\n";
- }
- }
- int main() {
- auto grids = solveNQueens(5);
- cout << "calculated " << grids.size() << " boards:\n\n";
- print_grids(grids);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement