Главная » C++ » Переполнение стека решений N-Queens

Переполнение стека решений N-Queens

Поэтому мне нужна помощь с классической проблемой 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;
}

6

Решение

В этом решении я сохранил в значительной степени оригинальный подход и код:

#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;
}
  • исправлено: ошибка компиляции: cout неизвестен -> #include iostream
  • добавлено: дополнительная новая строка в print_solutions разделить несколько решений
  • фиксированный: print_solutions распечатал транспонированную таблицу
  • исправлено: ошибка компиляции: print_solutions не возвращает значение -> void
  • фиксированный: argc проверять
  • добавлено: solution_count поддержка движением column позвонить на сайт
  • исправлено: дублирование кода возврата (column--, row = 0)
  • исправлено: ненужный внутренний цикл (row < board_size)
  • не фиксируется: my_board утечка
  • не исправлено: весь Board класс и его экземпляр не нужны
2

Другие решения

Вот мое рекурсивное решение для грубой силы. Он не является оптимальным (без возврата), но достаточно хорошо работает для шахматных досок размером до 14 х 14.
В рекурсивном методе queensSolution Первый аргумент — размер шахматной доски. Второй аргумент кодирует фактическое положение королев.

Например, вектор, описывающий положение на картинке, будет {1, 3, 0, 2}. Это означает: в первой строке (отсчет начинается с 0, то есть это первый элемент вектора) ферзь находится на позиции 1 (второй квадрат слева), во второй строке (второй элемент в векторе) ставится ферзь на позиции 3 (последний квадрат ряда) и т. д.

введите описание изображения здесь

Третий аргумент содержит вектор, который будет содержать все позиции решения (закодированный как вектор, как описано выше).
Метод справки intersect проверяет, нет ли столкновения между новой королевой, которая будет размещена в позиции {queens.size (), x}. Столкновения происходят, когда новая королева находится в том же «столбце» (позиция x), что и любая из существующих королев, или если расстояния между позициями x и позициями y новой королевы с любой из существующих королев равны (диагональная позиция). Нам не нужно проверять, будет ли новая королева помещена в строку (y), где уже размещена какая-то другая королева, потому что каждый раз, когда мы добавляем элемент в queens вектор мы поместили в новую строку.

#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();
}
}
}

Например, чтобы найти все решения для шахматной доски 4х4, сделайте следующее:

int main(){
int dim = 4;
vector<int>queens;
vector<vector<int>> result;
queensSolution(dim, queens, result);
}

После queensSolution возвращает, вектор результата содержит два вектора: {1, 3, 0, 2} а также {2, 0, 3, 1},

2

Вы можете использовать рекурсивный подход для ее решения. Я написал статью об этом: Учебное пособие по рекурсии: N-королев в C. Чтобы получить все решения, просто запустите рекурсию без прерывания для первого найденного решения.

Здесь также доступно эвристическое решение: Пазл Восемь королев.

1

Проверь это суть. Это простая рекурсивная функция, которая возвращает все решения.
Это работает, помещая каждый раз ферзя в следующий ряд. Метод is_safeпроверяет, безопасно ли размещать ферзь в столбце col в следующей строке. Решением является вектор, где индекс i является строкой, а значение этого индекса является столбцом. Каждый раз, когда ферзь размещается успешно, вектор увеличивается на один элемент и добавляется в набор возможных решений, которые возвращаются обратно в стек рекурсивных вызовов.

0
Источник
По вопросам рекламы [email protected]
Web-Answers © 2024 Наверх