java - 使用堆栈在 Java 中进行 Queens 练习

Question

我是编程新手，我的任务是解决 N Queens 问题。我不知道我的代码有什么问题，我花了很多时间。任何人都可以引导我走向正确的方向来帮助我吗？

public static boolean isSafe(int[] col, int size, stack s)
{       
    int x;

    for(int i = 1; i<=size; i++)
    {
        if(s.get(i)==i || ((s.get(i-1) - s.get(i)) == (col[i-1] - col[i])))
            return false;
    }

    return true;
}

public static void solve(int size, stack s)
{
    int[] column = new int[size];
    int x = 0;

    s.push(0);
    column[0] = 0;

    for(int i = 0; i<size; i++)
    {
        for(int j = 0; j<size;j++)
        {
            if(isSafe(column,size) == true)
            {
                s.push(i);
                column[i] = j;
            }
            else
            {
                x = s.pop();
                if(x+1<size)
                {
                    column[i] = x+1;
                    s.push(x+1);
                }
                else
                {   
                    j=0;
                    column[i] = j;
                    s.push(i+1);
                }
            }
        }
    }

    if(s.size() == size)
        printBoard(column, size);
}

栈类，有push、pop、size、get函数(返回int，push函数的参数是int)

我只需要使用回溯和堆栈来解决它，不需要递归。

编辑:顺便说一句，如果我改变了

if(s.size() == size)
  printBoard(column, size);

将大小变量替换为 1，我打印了电路板，否则我什么也得不到。

编辑:问题在于推送和弹出，算法不太正确，因为我最终在堆栈中只有 1 个元素。

Answer 1

为了让任何有兴趣的人澄清一下，“N Queens”问题让人想起“8 Queens”问题，在该问题中，必须将 8 个皇后放在棋盘上，这样任何一个皇后都无法捕获另一个。这可以扩展到任意数量的皇后(只要棋盘具有适当的尺寸)。这个谜题很适合递归，并且经常在有关递归的章节中讲授。这是一个 link拼图。

您说您可以使用堆栈，但不能使用递归。递归实际上是通过使用堆栈(您从未明确与之交互)来工作的。这意味着可以通过使用堆栈来编写任何递归函数。在这种情况下，堆栈用于跟踪函数参数和其他相关变量。更具体地说，当调用一个新的递归函数时，函数中所有当前的本地数据都会被压入堆栈。当退出递归调用后需要取回数据时，栈顶的数据被弹出，然后再次使用。

首先编写一个递归函数来解决问题，然后弄清楚如何将递归解决方案“转换”为具有堆栈的迭代解决方案，这可能更容易。尝试迭代编写解决方案也是一个好主意，然后找出需要跟踪哪些信息才能使回溯起作用。我注意到您还使用一维数组来存储皇后的位置，但首先使用二维数组可能有助于更好地可视化拼图。这也使您的编程更加直接。