N皇后使用c++，回溯使用动态2D阵列

Question

我一直试图用回溯来解决N皇后问题。我在网上发现的大多数方法都涉及向量，这使得我很难像互联网上的一些小程序那样可视化解决方案。

我想出的解决方案是给我很多问题(我觉得这些问题与使用的动态2D数组索引有关)，我无法用Dev-C++ debugger.Any帮助和/或建设性的批评来解决这个问题。在此之前，非常感谢您。

以下是我想出的解决方案：

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

Answer 1

它在初始配置之后运行，但您没有打印它。更改此(内部解决)：

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