Java编写Peg Solitaire（孔明棋）求解器无法找到解问题求助

问题排查与修复方案 #

1. 方向逻辑坐标完全错位（核心bug） #

你在canTurn和turn方法中混淆了行、列坐标的含义：

• 你定义的board[x][y]中x为行索引，y为列索引
• 向右/向左走应该保持行不变，修改列坐标，而你现在的逻辑是修改行坐标x，保持列y不变，和实际方向完全不匹配
• 上下走应该保持列不变，修改行坐标，你现在的逻辑是修改列坐标y，保持行x不变

修复方式：将四个方向的坐标逻辑替换为正确对应关系：

// canTurn方法的方向判断修正
if(direction.equals("right")) {
    if(y <5) { // 列+2不越界
        if (board[x][y] == 1 && board[x][y+1] ==1 && board[x][y+2]==0) {
            return true;
        }
    }
} else if(direction.equals("left")) {
    if(y>1) { // 列-2不越界
        if (board[x][y] ==1 && board[x][y-1]==1 && board[x][y-2]==0) {
            return true;
        }
    }
} else if(direction.equals("up")) {
    if(x>1) { // 行-2不越界
        if (board[x][y] ==1 && board[x-1][y]==1 && board[x-2][y]==0) {
            return true;
        }
    }
} else if(direction.equals("down")) {
    if(x<5) { // 行+2不越界
        if (board[x][y] ==1 && board[x+1][y]==1 && board[x+2][y]==0) {
            return true;
        }
    }
}

// turn方法的坐标逻辑同步修正
if(direction.equals("right")) {
    board.setValue(x,y,0);
    board.setValue(x,y+1,0);
    board.setValue(x,y+2,1);
    return board;
} else if(direction.equals("left")) {
    board.setValue(x,y,0);
    board.setValue(x,y-1,0);
    board.setValue(x,y-2,1);
    return board;
} else if(direction.equals("up")) {
    board.setValue(x,y,0);
    board.setValue(x-1,y,0);
    board.setValue(x-2,y,1);
    return board;
} else if(direction.equals("down")) {
    board.setValue(x,y,0);
    board.setValue(x+1,y,0);
    board.setValue(x+2,y,1);
    return board;
}

2. 递归步数传参错误 #

你在递归调用solve时使用了turn++后置自增，存在两个问题：

• 传参给下一层的是自增前的turn值，导致下一层步数统计错误
• 自增会修改当前层的turn变量，多个方向判断时步数会累计错误，回溯逻辑完全失效

修复方式：直接传turn + 1给下一层递归，不要修改当前层的turn变量：

// 所有递归调用处的turn++改为turn+1
if(board.canTurn("right",i,j) && solve(turn + 1, temp.turn(temp, "right", i, j))) {
    return true;
} else if(board.canTurn("left",i,j) && solve(turn + 1, temp.turn(temp, "left", i, j))) {
    return true;
} else if(board.canTurn("up",i,j) && solve(turn + 1, temp.turn(temp, "up", i, j))) {
    return true;
} else if(board.canTurn("down",i,j) && solve(turn + 1, temp.turn(temp, "down", i, j))) {
    return true;
}

3. 棋盘副本共用导致状态污染 #

你在solve方法开头只创建了一个temp副本，多个方向走棋都会修改同一个temp对象，第一个方向尝试失败后，后续方向的走棋都是基于被修改过的错误棋盘状态。

修复方式：每次尝试一个方向前，重新创建独立的棋盘副本：

// 去掉solve开头的Board temp = new Board(board);
// 每个方向判断前创建新副本
if(board.canTurn("right",i,j)) {
    Board temp = new Board(board);
    if(solve(turn +1, temp.turn(temp, "right", i,j))) {
        return true;
    }
}
// 其余三个方向同理，每个都创建独立temp

4. 步数阈值配置核对 #

如果你需要测试2步的场景，需要把PegSolver中的peg变量改为2，当前设置为1只能搜索1步的解。

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