Так что мне нужна помощь с классической проблемой N-Queens.
Команда для запуска программы будет следующей: nqueens N k — где N — размер таблицы (N x N), а k — количество решений.
Так, например, если бы я запустил программу, набрав nqueens 4 1, было бы напечатано следующее.
_ Q _ _
_ _ _ Q
Q _ _ _
_ _ Q _
Однако я не могу понять, как обрабатывать более 1 решения? Как определить более одного решения этой проблемы?
То, что у меня есть до сих пор, ниже:
#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;
}
argc < 2, вероятно, должно бытьargc < 3, поскольку вы ожидаете два параметра, тогда вы, вероятно, захотите каким-то образом использовать параметр количества решений. - person Retired Ninja schedule 17.11.2013