Reputation:
N-Queens Solutions C++
So I need help with the classic N-Queens problem.
The command to run the program will be: 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 be printed out.
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
However, I cannot figure out how to handle more than 1 solution? How can I determine more than just one solution for this problem?
What I have so far is 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;
}
Upvotes: 6
Views: 22026
Answers (4)
Reputation: 1973
Here is my brute force recursive solution. It is not optimal one (without backtracking), but works reasonable good for chess boards up to 14 x 14.
In the recursive method queensSolution the first argument is the size of chess board. The second argument encodes actual position of the queens.
For example, vector describing the position on the picture would be {1, 3, 0, 2}. This means: in the first row (count starts with 0, so it is first element of the vector) a queen is on position 1 (second quadrat from left), in the second row (second element in the vector) a queen is placed on position 3 (the last quadrat of the row) etc.
The third argument contains vector that will contain all solution positions (encoded as vector as described above).
The help method intersect checks whether there is a collision between a new queen that will be placed on position {queens.size(), x}. Collisions occur when the new queen is on the same 'column' (x position) as any of existing queens or whether the distances between x positions and y positions of the new queen with any of existing queens are equal (diagonal position). We do not have to check whether the new queen will be placed in a row (y) where some other queen is already placed, because every time we add an element to the queens vector we put it in new row.
#include<vector>
using namespace std;
bool intersect(const vector<int> &queens, int x) {
int y = queens.size();
for (int i = 0; i < y; i++) {
if ((abs(queens[i] - x) == 0) || (abs(queens[i] - x) == y - i))
return true;
}
return false;
}
void queensSolution(const int dim, vector<int> queens, vector<vector<int>> &res) {
if (queens.size() >= dim) {
res.push_back(queens);
queens.clear();
return;
}
for (int i = 0; i < dim; i++) {
if (!intersect(queens, i)) {
queens.push_back(i);
queensSolution(dim, queens, res);
queens.pop_back();
}
}
}
For example, to find all solutions for 4 x 4 chessboard, do following:
int main(){
int dim = 4;
vector<int>queens;
vector<vector<int>> result;
queensSolution(dim, queens, result);
}
After queensSolution returns, vector result contains two vectors: {1, 3, 0, 2} and {2, 0, 3, 1}.
Upvotes: 2
Reputation: 366
Check this gist. It's a simple recursive function that returns all the solutions.
It works by placing each time a queen a the next row. The method is_safechecks if it is safe to place a queen at column col in the next row. The solution are vector where the index i is the row and the value at that index is the column. Each time a queen is placed successfully, the vector grows by one element and is added to the set of candidate solutions which are returned back up in the recursive calls stack.
Upvotes: 0
Reputation: 5525
You can use a recursive approach for solving it. I have written an article about this: Recursion tutorial: N-queens in C. To obtain all the solutions, simply run the recursion without terminating for the first solution found.
There is also a heuristic solution available here: Eight queen puzzle.
Upvotes: 1
Reputation: 2089
In this solution I kept pretty much of the original approach and the 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: compile error: cout is unknown ->
#includeiostream - added: extra newline in
print_solutionsto separate multiple solutions - fixed:
print_solutionsprinted the transposed table - fixed: compile error:
print_solutionsdoes not return a value ->void - fixed:
argccheck - added:
solution_countsupport by movingcolumnto call site - fixed: backtrack code duplication (
column--,row = 0) - fixed: unnecessary inner loop (
row < board_size) - not fixed:
my_boardis leaked - not fixed: the whole
Boardclass and its instance is unnecessary
Upvotes: 2
Related Questions
- N Queens problem solution from Cracking the Coding Interview. What would be the Time Complexity?
- N queens solution is incorrect and im not sure why
- N-Queens problem. Returning array from functions c++
- 8 queens problem
- Modified N-Queens in C
- 8 queens puzzle conflict checking
- N queens using backtracking
- How to solve 8 queens 1D array with brute force?
- N Queens in C++ using vectors
- Query about N- Queen solving?