java - Java中的N-Queens使用Stacks，回溯后继续走同一条路线

Question

标题几乎说明了一切。我一直在研究这个问题，但无法找到一种方法来防止它发生。也许有某种方法可以存储无效的展示位置？或者我将如何实现一种方法，让它从上次位于该行的时间开始“恢复”，这样它就不会再次选择相同的值？

忽略 while i，它只是为了调试。与打印品相同。

import java.util.Stack;

public class NQueens {

//***** fill in your code here *****
//feel free to add additional methods as necessary

//finds and prints out all solutions to the n-queens problem
public static int solve(int n) {
    //***** fill in your code here *****
    //Scaffolding code from Stacks.pdf
    //------------------------------------------------------------------------------------------------------------------
    //  Create empty stack and set current position to 0
    Stack<Integer> s = new Stack<Integer>();

    int column = 0;
    int row = 0;

    int solutionsCount = 0;
    int i = 0;
    //Repeat {
    //loop from current position to the last position until a valid position is found //current row
    while (i < 5){

        for(column = 0; column < n ;column++) {
            //if there is a valid position
            System.out.println("Top of for loop");
            System.out.println("Column/index for = " + column + "; Row is: " + row);
            System.out.println("Stack size = " + s.size());
            System.out.println();
            if (isValid(s, column, row)) {
                s.push(column);
                //push the position to stack, set current position to 0 // move to next ro
                row++;
                column = 0;
            }//if
        }//for

        //if there is no valid position
        if(!isValid(s, column, row) || column >= n){
            //if stack is empty, break // stop search
            if(s.size() == 0){
                break; //stop search
            }//if
            //else pop from stack, set current position to next position // backtracking to previous row
            else{
                s.pop();
                column++;
                row--;
            }//else
        }//if

        //if stack has size N { // a solution is found
        if (s.size() == n){
            solutionsCount++;
            printSolution(s);
            //pop from stack, set current position to next position // backtracking to find next solution
            s.pop();
            row--;
            column++;
        }//if

        else {
        }//else
    i++;
    // Make sure to change this when not bug testing for 4x4
    }//end for loop
//update the following statement to return the number of solutions found
return solutionsCount;

}//solve()

Answer 1

这看起来像是家庭作业，所以这里有一些提示:

1. 您正在 for 循环之后修改 column 变量。显然，您希望将其值保留到 while 的下一次迭代中。但是，当 while 再次启动时，您要做的第一件事就是使用 for (column = 0; ....) 将 column 设置为 0，这会覆盖其值。 column 应该从 while 的一次迭代到下一次迭代携带哪些信息？
2. 您在 for 循环中将 column 设置为 0，但在下一次 for 迭代之前，它会通过 column++ 递增到 1。
3. 您在循环之后的 if 语句中使用了 column。 for 循环完成后，您期望该变量的值是多少？
4. 在 for 循环之后，有两个 if 语句，它们试图检查相同的条件 - for 循环是否找到了解决方案。只有第二个 if 更清楚。您甚至需要两个 if 吗？
5. 您将列值放入堆栈中，但是当您将它们从堆栈中弹出时，您只需丢弃它们即可。这些值对您没有用处吗？