我对编程有点陌生,我的任务是解决 N 皇后问题。 我不知道我的代码有什么问题,我花了很多时间。 谁能帮助我引导我走向正确的方向?
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 个元素。
最佳答案
只是为了向感兴趣的人澄清一下,“N 个皇后”问题让人想起“8 个皇后”问题,其中必须将 8 个皇后放在棋盘上,这样没有一个皇后可以捕获另一个皇后。这可以扩展到任意数量的皇后(只要棋盘具有适当的尺寸)。这个谜题很适合递归,并且经常在递归章节中教授。这是 link到这个谜题。
您说您可以使用堆栈
,但不能使用递归
。递归实际上是通过使用堆栈(您从未显式与之交互)来工作的。这意味着可以使用堆栈来编写任何递归函数。在这种情况下,堆栈用于跟踪函数参数和其他相关变量。更具体地说,当调用新的递归函数时,函数中当前的所有本地数据都被压入堆栈。当退出递归调用后需要检索数据时,将栈顶的数据弹出,然后再次使用。
首先编写一个递归函数来解决问题,然后弄清楚如何将递归解决方案“转换”为带有堆栈的迭代解决方案,这可能会更容易。尝试迭代地编写解决方案,然后找出需要跟踪哪些信息才能使回溯发挥作用也是一个好主意。我注意到您还使用一维数组来存储皇后的位置,但首先使用二维数组可能有助于更好地可视化谜题。这也使您的编程更加简单。
关于java - 使用堆栈在 Java 中进行 Queens 练习,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9999471/