n 皇后问题矩阵具有解决方案的垃圾值 [关闭]

Question

我正在解决 nqueen 问题，其中你有 nxn 的棋盘，你必须放置 n 个皇后，这样没有皇后互相攻击。除了矩阵中的垃圾值外，一切都对我有用，我不知道原因，因为我是新手c++ 有人能告诉我如何解决这个问题以及我在代码中哪里出错了所以我以后可以避免这个问题

include <iostream>
using namespace std;
bool issafe(int **arr, int x, int y, int n)
{

    for (int i = 0; i < x; i++)
    {
        if (arr[i][y] == 1)
        {
            return false;
        }
    }
    int row = x;
    int col = y;

    while (row >= 0 && col >= 0)
    {
        if (arr[row][col] == 1)
        {
            return false;
        }
        row--;
        col--;
    }
    while (row >= 0 && col < n)
    {
        if (arr[row][col] == 1)
        {
            return false;
        }
        row--;
        col++;
    }
    return true;
}
bool nqueense(int **arr, int x, int n)
{

    if (x >= n)
    {
        return true;
    }
    for (int i = 0; i < n; i++)
    {

        if (issafe(arr, x, i, n))
        {
            arr[x][i] = 1;
            if (nqueense(arr, x + 1, n))
            {
                return true;
            }
            else
            {
                arr[x][i] = 0;
            }
        }
    }

    return false;
}
void printarr(int **arr, int n)
{

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}
int main()
{

    int n;
    n = 4;
    int **arr = new int *[n];
    for (int i = 0; i < n; i++)
    {
        arr[i] = new int[n];
    }
    if (nqueense(arr, 0, n))
    {
        printarr(arr, n);
    }
    else
    {
        cout << "false dream";
    }
    return 0;
}

期待这是我的结果

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0 

但实际输出为

0 1 0 0 
0 17825984 0 1 
1 0 0 0 
17855864 17825984 1 0 

Answer 1

你没有初始化数组，它包含未确定的值。

快速而肮脏的修复：在

main

中添加它，就在

if (nqueense(arr, 0, n))

之前

  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y ++)
      arr[x][y] = 0;

这会将您的

a

“数组”的所有元素初始化为0.

虽然可能还有更多错误，我没有检查。特别是检查你的数组索引是否超出范围。 C++ 不会为你检查这个。

---

一个正确的解决方案是使用

std::vector<<std::vector<int> a;

而不是你的

new int*

疯狂。我把细节留给你做练习。

Answer 2

你的'issafe'函数有问题。 对于垃圾值，条件有问题。

if (arr[row][col] == 1)
{
    return false;
}

并为设置值的条件添加其他内容，我认为这将解决您的问题

if (issafe(arr, x, i, n))
{
    arr[x][i] = 1;
    if (nqueense(arr, x + 1, n))
    {
        return true;
    }
    else
    {
        arr[x][i] = 0;
    }
}
else
{
    //add code!
}

Answer 3

您忘记在函数内将 row, col 重置为 x, y

issafe

我修改了代码，让我们更容易追踪问题。 我把修改后的版本放在这里。

#include <iostream>
#include <array>

#include <cassert>

const int N = 4;

template <int W> class Grid
{
public:
    Grid()
    {
        m_data.fill(0);
    }

    void set(int x, int y, int val)
    {
        m_data[get_idx(x, y)] = val;
    }

    int get(int x, int y) const
    {
        return m_data[get_idx(x, y)];
    }

private:
    int get_idx(int x, int y) const
    {
        assert(x >= 0 && x < W && y >= 0 && y < W);
        return y * W + x;
    }

private:
    std::array<int, W * W> m_data;
};

using Arr = Grid<N>;

bool issafe(Arr& arr, int x, int y, int n)
{

    for (int i = 0; i < x; i++) {
        if (arr.get(i, y) == 1) {
            return false;
        }
    }

    int row = x;
    int col = y;
    while (row >= 0 && col >= 0) {
        if (arr.get(row, col) == 1) {
            return false;
        }
        row--;
        col--;
    }

    row = x;
    col = y;
    while (row >= 0 && col < n) {
        if (arr.get(row, col) == 1) {
            return false;
        }
        row--;
        col++;
    }
    return true;
}
bool nqueense(Arr& arr, int x, int n)
{
    if (x >= n) {
        return true;
    }

    for (int i = 0; i < n; i++) {

        if (issafe(arr, x, i, n)) {
            arr.set(x, i, 1);
            if (nqueense(arr, x + 1, n)) {
                return true;
            } else {
                arr.set(x, i, 0);
            }
        }
    }

    return false;
}
void printarr(Arr const& arr, int n)
{

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cout << arr.get(i, j) << " ";
        }
        std::cout << std::endl;
    }
}

int main()
{

    Arr arr;
    if (nqueense(arr, 0, N)) {
        printarr(arr, N);
    } else {
        std::cout << "false dream";
    }
    return 0;
}