N-Queens Solutions C ++

Question

So I need help with the classic N-Queens issue.

The program launch command: nqueens N k - where N is the size of the table (N x N), and k is the number of solutions

So, for example, if I were to run the program by typing nqueens 4 1 , the following would print.

_ Q _ _

_ _ _ Q

Q _ _ _

_ _ Q _

However, I cannot figure out how to handle more than one solution? How to identify more than one solution to this problem?

What I'm still below:

#include <cstdlib> #include <iomanip> #include <cmath> #include <vector> using namespace std; class Board { private: bool** spaces; int size; public: Board(int size) { this->size = size; spaces = new bool*[size]; for (int i = 0; i < size; ++i) { spaces[i] = new bool[size]; } } bool isSafe(int row, int column, vector<int>& state) { //check row conflict //no need to check for column conflicts //because the board is beimg filled column //by column for(int i = 0; i < column; ++i) { if(state[i] == row) return false; } //check for diagonal conflicts int columnDiff = 0; int rowDiff = 0; for(int i = 0; i < column; ++i) { columnDiff = abs(column - i); rowDiff = abs(row - state[i]); if(columnDiff == rowDiff) return false; } return true; } int getSize() { return size; } bool getSpace(int x, int y) { return spaces[y][x]; } void setSpace(int x, int y, bool value) { spaces[y][x] = value; } Board(Board& other) { this->size = other.getSize(); spaces = new bool*[size]; for (int i = 0; i < size; ++i) { spaces[i] = new bool[size]; for (int j = 0; j < size; ++j) { spaces[i][j] = other.getSpace(j, i); } } } void backtrack(vector<int>& state, int board_size) { int row = 0; int column = 0; bool backtrack = false; while(column < board_size) { while(row < board_size) { if(backtrack) { row = state[column] + 1; if(row == board_size) { column--; //backtrack more backtrack = true; row = 0; break; } backtrack = false; } if(isSafe(row, column, state)) { state[column] = row; row = 0; column++; //advance backtrack = false; break; } else { if(row == (board_size - 1)) { column--; //backtrack backtrack = true; row = 0; } else { row++; } } } } } }; int print_solutions(Board *board, vector<int>& state, int board_size) { for(int i=0; i < board_size; ++i) { for(int j=0; j < board_size; ++j) { if(state[i] == j) cout << 'Q' << " "; else cout << '_' << " "; } cout << endl; } } int main(int argc, char* argv[]) { if (argc < 2) { cout << "Usage: nqueens [Board Size] [Number of Solutions]" << endl; return 1; } int board_size = atoi(argv[1]); //int solution_count = atoi(argv[2]); vector<int> state; state.resize(board_size); Board *my_board = new Board(board_size); my_board->backtrack(state, board_size); print_solutions(my_board, state, board_size); return 0; } 

Answer 1

In this solution, I almost completely used the original approach and code:

 #include <cstdlib> #include <iomanip> #include <cmath> #include <vector> #include <iostream> using namespace std; class Board { private: bool** spaces; int size; public: Board(int size) { this->size = size; spaces = new bool*[size]; for (int i = 0; i < size; ++i) { spaces[i] = new bool[size]; } } bool isSafe(int row, int column, vector<int>& state) { //check row conflict //no need to check for column conflicts //because the board is beimg filled column //by column for(int i = 0; i < column; ++i) { if(state[i] == row) return false; } //check for diagonal conflicts int columnDiff = 0; int rowDiff = 0; for(int i = 0; i < column; ++i) { columnDiff = abs(column - i); rowDiff = abs(row - state[i]); if(columnDiff == rowDiff) return false; } return true; } int getSize() { return size; } bool getSpace(int x, int y) { return spaces[y][x]; } void setSpace(int x, int y, bool value) { spaces[y][x] = value; } Board(Board& other) { this->size = other.getSize(); spaces = new bool*[size]; for (int i = 0; i < size; ++i) { spaces[i] = new bool[size]; for (int j = 0; j < size; ++j) { spaces[i][j] = other.getSpace(j, i); } } } bool backtrack(vector<int>& state, int& column, int board_size) { int row = 0; bool backtrack = column == board_size; while(column < board_size || backtrack) { { if(backtrack) { if (column == 0) return false; column--; row = state[column] + 1; if(row == board_size) { backtrack = true; continue; } backtrack = false; } if(isSafe(row, column, state)) { state[column] = row; row = 0; column++; //advance backtrack = false; continue; } else { if(row == (board_size - 1)) { backtrack = true; } else { row++; } } } } return true; } }; void print_solutions(Board *board, vector<int>& state, int board_size) { for(int i=0; i < board_size; ++i) { for(int j=0; j < board_size; ++j) { if(state[i] == j) cout << 'Q' << " "; else cout << '_' << " "; } cout << endl; } cout << endl; } int main(int argc, char* argv[]) { if (argc < 3) { cout << "Usage: nqueens [Board Size] [Number of Solutions]" << endl; return 1; } int board_size = atoi(argv[1]); int solution_count = atoi(argv[2]); vector<int> state; state.resize(board_size); Board *my_board = new Board(board_size); int column = 0; while (solution_count-- > 0 && my_board->backtrack(state, column, board_size)) print_solutions(my_board, state, board_size); return 0; } 

• fixed: compilation error: cout unknown → #include iostream
• Added extra line in print_solutions to separate multiple solutions.
• fixed: print_solutions printed transposed table
• fixed: compilation error: print_solutions does not return value → void
• fixed: argc check
• added: solution_count support by moving column to call the site
• fixed: duplication of return code ( column-- , row = 0 )
• fixed: unnecessary inner loop ( row < board_size )
• not fixed: my_board leaked
• not fixed: the entire Board class and its instance are not needed

Answer 2

You can use a recursive approach to solve it. I wrote an article about this: Recursion Tutorial: N-queens in C. To get all the solutions, just run the recursion without stopping at the first solution found.

There is also a heuristic solution: Eight Queen Puzzles .

Answer 3

Mark the gist . This is a simple recursive function that returns all solutions. It works by putting the next line every time the queen. The is_safe method checks if the queen can be placed in the col column in the next row. The solution is a vector, where index i is a row, and the value at that index is a column. Each time the queen is placed successfully, the vector grows by one element and is added to the set of candidates who return to the recursive call stack.