N Queen с использованием C ++ и возврат с помощью динамического 2D-массива
Я пытался решить проблему N королевы с помощью возврата. Большинство подходов, которые я нашел в Интернете, были связаны с векторами, что затрудняло мне визуализацию решений, как это делают некоторые апплеты в Интернете.
Решение, которое я придумал, дает мне много проблем (которые, как я чувствую, связаны с индексацией используемого динамического двумерного массива), и я не могу понять это с помощью отладчика Dev-C ++. Любая помощь и / или конструктивная критика высоко ценится. Спасибо заранее.
Вот решение, которое я придумал:
#include<iostream>
#include<string.h>
#include<conio.h>
using namespace std;
void display(char** b, int len);
void initialize(char** &b, int k);
void consider1strow(char ** b, int len);
void markunsafe(char** board, int rowno, int colno);
void marksafe(char** board, int rowno, int colno);
void considerrow(char** board, int rowno);
void backtrack(char** board, int rowno);
bool checksafety(char** board, int rowno, int colno);
void place(char** board, int rowno, int colno);
void solve(char** board, int len);int state[20] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
int len;
void display(char** board, int len)
{
int i, j;
cout << endl << "The current state of the board:" << endl;
for (i = 0; i < len; i++)
{
for (j = 0; j < len; j++)
{
cout << board[i][j];
}
cout << endl;
}
}
void initialize(char** &b, int k)
{
int i, j;
//create dynamic board
b = new char*[k];
for (i = 0; i < k; i++)
{
b[i] = new char[k];
}
//initialize array
for (i = 0; i < k; i++)
{
for (j = 0; j < k; j++)
{
b[i][j] = '-';
}
}
}
void consider1strow(char ** board, int len)
{
int col;
cout << "Enter the column to try for the first row!";
cin >> col;
board[0][col - 1] = 'Q';
state[0] = col - 1;
markunsafe(board, 0, col - 1);
display(board, len);
}
void markunsafe(char** board, int rowno, int colno)
{
int i, j;
//mark row as unsafe
for (i = 0; i < len; i++)
{
board[rowno][i] = 'x';
}
//mark column as unsafe
for (i = 0; i < len; i++)
{
board[i][colno] = 'x';
}
//mark unsafe diagonals
for (i = 0; i < len; i++)
{
for (j = 0; j < len; j++)
{
if ((rowno + colno) == (i + j))
{
board[i][j] = 'x'; //check if index gives a problem of +/- 1
}
if ((rowno - colno) == (i - j))
{
board[i][j] = 'x'; //check if index gives a problem of +/- 1
}
}
}
board[rowno][colno] = 'Q';
}
void marksafe(char** board, int rowno, int colno)
{
int i, j;
//mark row as safe
for (i = 0; i < len; i++)
{
board[rowno][i] = '-';
}
//mark column as unsafe
for (i = 0; i < len; i++)
{
board[i][colno] = '-';
}
//mark unsafe diagonals
for (i = 0; i < len; i++)
{
for (j = 0; j < len; j++)
{
if ((rowno + colno) == (i + j))
{
board[i][j] = '-'; //check if index gives a problem of +/- 1
}
if ((rowno - colno) == (i - j))
{
board[i][j] = '-'; //check if index gives a problem of +/- 1
}
}
}
}void considerrow(char** board, int rowno)
{
bool safe = 0;
int i;
for (i = 0; i < len; i++)
{
safe = checksafety(board, rowno, i);
if (safe && (i >= state[rowno]))
{
break;
}
}
if (safe && (i >= state[rowno]))
{
place(board, rowno, i);
}
else if (!safe)
{
backtrack(board, rowno);
}
}
void backtrack(char** board, int rowno)
{
marksafe(board, rowno - 2, state[rowno - 2]);
considerrow(board, rowno);
}
bool checksafety(char** board, int rowno, int colno)
{
if (rowno == 0)
{
return 1;
}
else if (board[rowno][colno] == 'x')
{
return 0;
}
else if (board[rowno][colno] == '-')
{
return 1;
}
}void place(char** board, int rowno, int colno)
{
board[rowno][colno] = 'Q';
state[rowno] = colno;
markunsafe(board, rowno, colno);
}
void solve(char** board, int len)
{
int i = 0;
if (i == len)
{
display(board, len);
}
else
{
consider1strow(board, len);
for (i = 1; i < len; i++)
{
considerrow(board, i);
}
}
}
int main()
{
char** board;
cout << "Enter the size of the board!";
cin >> len;
initialize(board, len);
solve(board, len);
getch();
}
Решение
Он запускается после начальной настройки, но вы его не печатаете. Изменить это (внутри решить):
for(i=1;i<len;i++)
{considerrow(board,i);}
за это:
for(i=1; i<len; i++) {
considerrow(board,i);
display(board,len);
}
Кроме того, есть проблема с тем, как вы делаете возврат. Если никакие опции недоступны, вы удаляете ферзя из предыдущего ряда (это нормально), а затем вы помечаете каждую ячейку, на которую она нападала, как безопасную (не хорошо). Проблема в том, что некоторые из этих ячеек могут быть атакованы другой королевой, поэтому вы не можете пометить их как безопасные. Кроме того, вы не помещаете другую королеву в этот ряд. Я предлагаю несколько решений:
Во-первых, сделайте это рекурсивным: considerrow вызовет себя со следующей строкой и вернет true (1), если это удастся, или false (0), если это не удастся. Если это не удастся со следующей строкой, вы можете использовать следующую ферзь в текущей строке и вызвать considerrow снова, пока вы не добьетесь успеха или не исчерпаете столбцы, в этом случае вы возвращаете false.
Чтобы рассмотреть другую королеву в определенном ряду, вы можете сделать две вещи: создать копию доски, которую вы передадите considerrow для следующей строки (и, таким образом, сохраняя копию «до», чтобы попробовать другую королеву), или пометьте каждую ячейку как безопасную, а затем проверьте все существующие королевы, чтобы пометить ячейки как опасные.
Редактировать:
Чтобы сделать это рекурсивным, мы собираемся сделать considerrow называть себя со следующим значением.
bool considerrow(char** board,int rowno) {
//Print the board
display(board,len);
bool safe=0;
int i;
for(i=0; i<len; i++) {
safe=checksafety(board,rowno,i);
if(safe) {
place(board,rowno,i);
//Is this the last row? If so, we suceeded
if (rowno==len-1) return 1;
//Call itself with next row, check if suceeded
if (considerrow(board,rowno+1))
return 1;
else //Failed, try a different row
backtrack(board,rowno);
}
}
return 0; //If we got here, then we ran out of colums. Return failure
}
Функция возврата может быть изменена для возврата текущей строки следующим образом:
void backtrack(char** board, int rowno) {
//Clear the current row
marksafe(board,rowno,state[rowno]);
//Check that every cell attacked by another queen is marked unsafe
for(int i=0; i<rowno; i++) markunsafe(board,i,state[i]);
}
Для этого решения требуется только вызвать первую строку:
void solve(char** board,int len) {
considerrow(board,0);
display(board,len);
}
Другие решения
Других решений пока нет …