回溯时While循环未满足条件提前终止——四皇后迭代求解问题

问题概述 #

尝试编写迭代程序解决4x4棋盘的4皇后问题（放置4个互不攻击的皇后），但程序在回溯后，主while循环提前终止，得到错误解，实际row仍小于4却退出循环。

现有代码 #

static int[] solve(char[][] board){
    int[] position = new int[4];
    int row = 0;
    int column = 0;

    while(row < 4){
        for(boolean check; column < board.length; column++){
            System.out.println("["+row+","+column+"]");
            check = true;
            for(int queen= 0; queen < row; queen++){
                if (position[queen] == column || queen - position[queen] == row - column || queen + position[queen] == row + column) {
                    check = false;
                    break;
                }
            }
            if(check){
                position[row] = column;
                column = 0;
                row++;
            }
            if(column > 2){
                column = position[--row];
            }
        }
    }
    return position;
}

当前输出与期望输出 #

当前错误输出 #

| Q | X | X | X |
| X | X | X | Q |
| X | Q | X | X |
| Q | X | X | X |

期望正确输出 #

| X | Q | X | X |
| X | X | X | Q |
| Q | X | X | X |
| X | X | Q | X |

逻辑错误分析 #

1. 回溯位置错误：当当前行所有列遍历完毕（column > 2）时，代码将column设为position[--row]，这会导致回溯后回到上一行皇后的原列，而非从原列的下一列开始尝试。这种情况下，会重复遍历已经验证过的无效位置，最终导致for循环提前结束，触发while循环退出。
2. for循环流程混乱：找到当前行的合法列后，仅设置column=0并row++，但for循环会继续执行column++，导致下一行的列遍历从1开始，同时未跳出当前for循环，引发后续不必要的迭代干扰流程。
3. 回溯时机错误：在for循环的每次迭代中都判断column > 2，而非在for循环结束后判断是否找到合法列，导致回溯逻辑被提前触发，打乱了遍历顺序。

修正后的代码 #

static int[] solve(char[][] board) {
    int[] position = new int[4];
    int row = 0;
    int column = 0;

    while (row < 4) {
        boolean found = false;
        // 遍历当前行的所有列
        for (; column < board.length; column++) {
            System.out.println("[" + row + "," + column + "]");
            boolean check = true;
            // 检查与已放置皇后是否冲突
            for (int queen = 0; queen < row; queen++) {
                if (position[queen] == column 
                    || queen - position[queen] == row - column 
                    || queen + position[queen] == row + column) {
                    check = false;
                    break;
                }
            }
            if (check) {
                position[row] = column;
                row++;
                column = 0; // 下一行从第0列开始遍历
                found = true;
                break; // 找到合法位置，跳出当前行的循环
            }
        }
        // 当前行未找到合法位置，回溯
        if (!found) {
            if (row == 0) {
                break; // 极端情况：第一行无合法位置（4皇后不会触发）
            }
            row--;
            column = position[row] + 1; // 从上一行皇后的下一列开始尝试
        }
    }
    return position;
}

修正说明 #

• 添加found标记，明确当前行是否找到合法列，避免在迭代中提前触发回溯。
• 回溯时将column设置为position[row] + 1，确保从上一行皇后的下一列开始重新尝试，避免重复无效遍历。
• 找到合法列后立即跳出当前行的for循环，保证流程清晰，避免后续迭代干扰。
• 增加边界判断，防止row减到负数导致数组越界。

验证结果 #

修正后程序会输出正确的位置序列，对应的棋盘与期望输出一致，while循环会在row达到4时正常终止。

内容的提问来源于stack exchange，提问作者Joy