Peg 纸牌解决方案更改目的地

Peg solitaire solution change destination

我在 java.

中写了一个解决挂钩纸牌的程序

我的程序得到一个起始板和一个目标板并尝试完成游戏。

我有一种计数器可以计算我的轮次,因为我有一个目的地有更多的 1 个钉子休息,假设如果我只需要移除 2 个钉子,那么我可以只用 2 个动作解决它。

我创建了一个看板 class:

public class Board {
    private int board[][] = new int[7][7];
    public Board(String place)
    {
        board[0][0]=2;
        board[1][0]=2;
        board[5][0]=2;
        board[6][0]=2;
        board[0][1]=2;
        board[1][1]=2;
        board[5][1]=2;
        board[6][1]=2;
        board[0][5]=2;
        board[1][5]=2;
        board[5][5]=2;
        board[6][5]=2;
        board[0][6]=2;
        board[1][6]=2;
        board[5][6]=2;
        board[6][6]=2;
        int loca=0;//location on the string of place
        for(int i=0;i<7;i++){
            for(int j=0;j<7;j++){
                if(board[i][j]!=2) {
                    if (place.charAt(loca) == 'O') {
                        loca++;
                        board[i][j] = 1;
                    } else if (place.charAt(loca) == '.') {
                        loca++;
                        board[i][j] = 0;
                    }
                }
                System.out.print(board[i][j]);//print for test
            }
            System.out.println();//print for test
        }
        System.out.println();

    }
    public Board(Board copy){
        for(int i=0;i<7;i++)
        {
            for(int j=0;j<7;j++)
            {
                board[i][j]=copy.getValue(i,j);
            }
        }
    }
    public int getValue(int x, int y)
    {
        return board[x][y];
    }
    public boolean isFinished(Board destination)
    {
        for(int i=0;i<7;i++)
        {
            for(int j=0;j<7;j++)
            {
                if(this.getValue(i,j)!=destination.getValue(i,j))
                {
                    return false;
                }
            }
        }
        return true;
    }
    public Board turn(Board board,String direction,int x,int y)
    {
        if(direction.equals("right"))
        {
            board.setValue(x,y,0);
            board.setValue(x+1,y,0);
            board.setValue(x+2,y,1);
            return board;
        }
        else if(direction.equals("left"))
        {
            board.setValue(x,y,0);
            board.setValue(x-1,y,0);
            board.setValue(x-2,y,1);
            return board;
        }
        else if(direction.equals("up"))
        {
            board.setValue(x,y,0);
            board.setValue(x,y-1,0);
            board.setValue(x,y-2,1);
            return board;
        }
        else if(direction.equals("down"))
        {
            board.setValue(x,y,0);
            board.setValue(x,y+1,0);
            board.setValue(x,y+2,1);
            return board;
        }
        else{
            System.out.println("there is not such direction, method turn on board class");
            return null;//just for caution
        }
    }
    public boolean isLegal(int x, int y){
        if(board[x][y]==2)
        {
            return false;
        }
        else{
            return true;
        }
    }
    public boolean canTurn(String direction,int x,int y){
        if(direction.equals("right"))
        {
            if(x<5) {
                if (board[x][y] == 1 && board[x + 1][y] == 1 && board[x + 2][y] == 0) {
                    return true;
                }
            }
        }
        else if(direction.equals("left"))
        {
            if(x>1) {
                if (board[x][y] == 1 && board[x - 1][y] == 1 && board[x - 2][y] == 0) {
                    return true;
                }
            }
        }
        else if(direction.equals("up"))
        {
            if(y>1) {
                if (board[x][y] == 1 && board[x][y - 1] == 1 && board[x][y - 2] == 0) {
                    return true;
                }
            }
        }
        else if(direction.equals("down"))
        {
            if(y<5) {
                if (board[x][y] == 1 && board[x][y + 1] == 1 && board[x][y + 2] == 0) {
                    return true;
                }
            }
        }
        else{
            System.out.println("there is not such direction, method canTurn on board class");
            return false;//just for caution
        }
        return false;
    }
    public void setValue(int x, int y, int value)
    {
        board[x][y]=value;
    }
}

然后我写了我的“求解器”class。

public class PegSolver {
    public int peg =1;
    Board destinationBoard = new Board("OOOOOOOOOOOOOOOOO..OOOOOOOOOOOOOO");
    Board board = new Board("OOOOOOOOOOOOOOOO.OOOOOOOOOOOOOOOO");

    public void start(){

        solve(0,board);
    }
    public boolean solve(int turn, Board board){
        Board temp = new Board(board);
        if(turn>peg)
        {
            return false;
        }
        else if(turn==peg){
            //todo:check if solve
            if(temp.isFinished(destinationBoard))
            {
                System.out.println("solution");
                return true;
            }
            else
            {
                return false;
            }
        }
        else//lower then 8
        {
            for(int i=0;i<7;i++){
                for (int j=0;j<7;j++)
                {
                    if(board.isLegal(i,j)) {
                        if(board.canTurn("right",i,j) && solve(turn++, temp.turn(temp, "right", i, j)))
                        {
                            return true;
                        }
                        else if(board.canTurn("left",i,j) && solve(turn++, temp.turn(temp, "left", i, j)))
                        {
                            return true;
                        }
                        else if(board.canTurn("up",i,j) && solve(turn++, temp.turn(temp, "up", i, j)))
                        {
                            return true;
                        }
                        else if(board.canTurn("down",i,j) && solve(turn++, temp.turn(temp, "down", i, j)))
                        {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}

当程序找到解决方案时,它需要打印“解决方案”,但由于某种原因,我的程序无法找到解决方案,即使它是一步到位的基本目的地。

有人可以帮我吗?

请查看修改后的代码。 许多更改与代码中的索引和方向不一致有关:其中 x 表示水平索引,y 表示垂直索引:数组索引应为 board[y][x](而不是 board[x][y])。
为了代码的可读性更好,许多“幻数”被更改为常量。 toString 方法添加到 Boardclass 以打印出板状态。它使用特殊字符制作漂亮的打印输出:

这在调试时很有用。

public class PegSolver {

    private final Board startBoard, destinationBoard;

    public PegSolver(Board startBoard, Board destinationBoard) {
        super();
        this.startBoard = startBoard;
        this.destinationBoard = destinationBoard;
    }

    public void start(){
        solve(0,startBoard);
    }
    private boolean solve(int turn, Board board){

        //check if solve
        if(board.isFinished(destinationBoard))
        {
            System.out.println("solved after "+ turn +" turns");
            return true;
        }

        for(int x=0;x<board.boardSize();x++){
            for (int y=0;y<board.boardSize();y++)
            {
                if(board.isLegal(x,y)) {
                    if(board.canTurn("right",x,y)
                            //turn++ changed to turn+1 so turn is incremented before invoking next solve
                            //and avoid changing the value of turn
                            && solve(turn+1, board.turn(new Board(board), "right", x, y)))
                        return true;
                    else if(board.canTurn("left",x,y)
                            && solve(turn+1, board.turn(new Board(board), "left", x, y)))
                        return true;
                    else if(board.canTurn("up",x,y)
                            && solve(turn+1, board.turn(new Board(board), "up", x, y)))
                        return true;
                    else if(board.canTurn("down",x,y)
                            && solve(turn+1, board.turn(new Board(board), "down", x, y)))
                        return true;
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {

        Board[] destinationBoards = {
                //by order of number of turns
                new Board("OOOOOOOOOOOOOO..OOOOOOOOOOOOOOOOO"),  //one right turn
                new Board("OOO.OOOO.OOOOO.OOOOOOOOOOOOOOOOOO"),  //right, down
                new Board("OOO.OO..OOOOOO.OOOOOOOOOOOOOOOOOO"),  //right, down,right
                new Board("OOO.OOO.OOOOO..OOOOO.OOOOOOOOOOOO"),  //right, down,right,up
                new Board("OOOOOOO..OOOO...OOOO.OOOOOOOOOOOO"),  //right, down,right,up,up
                new Board(".OO.OOO.OOOOO...OOOO.OOOOOOOOOOOO"),  //right, down,right,up,up,down
                new Board(".OO.OOO.OOOOO...OOOOO..OOOOOOOOOO"),  //right, down,right,up,up,down, left
                new Board(".OO.OOO.OOOOO...OOOOO.OOOOO.OO.OO"),  //right, down,right,up,up,down,left,up
                new Board(".OO.OO..O.OOO...OOOOO.OOOOO.OO.OO"),  //10 turns
                new Board("..O..O.O..OOO...OOOO..OOOOO..O..O"),  //15 turns
                new Board(".........O................O......"),  //30 turns
                new Board("...................O............."),  //31 turns
        };

        Board startBoard = new Board("OOOOOOOOOOOOOOOO.OOOOOOOOOOOOOOOO");

        for(Board destinationBoard : destinationBoards ){
            new PegSolver(startBoard, destinationBoard).start();
        }
    }
}

class Board {

    //int representation of the three states of a board cell
    private final static int  EMPTY = 0, PEG = 1, BORDER = 2;
    /*cahr representation of the three states of a board cell
      special chars are used to get nice printout
      todo: change board to char[][] to avoid the need for two
      representations (int and char)
     */
    private final static char[] CHAR_REPRESENTATION = {9898,9899,10062};
    private final static char ERROR = '?';
    private final int BOARD_SIZE=7, CORNER_SIZE=2;
    private final int board[][] = new int[BOARD_SIZE][BOARD_SIZE];

    public Board(String place)  {

        int loca=0;
        for(int y=0;y<BOARD_SIZE;y++){
            for(int x=0;x<BOARD_SIZE;x++){
                if(isWithinBoard(x,y)) {
                    if (place.charAt(loca) == 'O') {
                        loca++;
                        board[y][x] = PEG;
                    } else if (place.charAt(loca) == '.') {
                        loca++;
                        board[y][x] = EMPTY;
                    }
                }else{
                    board[y][x] = BORDER;
                }
            }
        }
        //for testing
        //System.out.println(this);
    }

    //copy constructor
    public Board(Board copy){
        for(int x=0;x<BOARD_SIZE;x++)
        {
            for(int y=0;y<BOARD_SIZE;y++)
            {
                board[y][x]=copy.getValue(x,y);
            }
        }
    }

    public int getValue(int x, int y)
    {
        return board[y][x];  //and not return board[x][y];
    }

    public boolean isFinished(Board destination)
    {
        for(int i=0;i<BOARD_SIZE;i++)
        {
            for(int j=0;j<BOARD_SIZE;j++)
            {
                if(this.getValue(i,j)!=destination.getValue(i,j))
                    return false;
            }
        }
        return true;
    }

    public Board turn(Board board,String direction,int x,int y)
    {
        if(direction.equals("right"))
        {
            board.setValue(x,y,EMPTY);
            board.setValue(x+1,y,EMPTY);
            board.setValue(x+2,y,PEG);
            return board;
        }
        else if(direction.equals("left"))
        {
            board.setValue(x,y,EMPTY);
            board.setValue(x-1,y,EMPTY);
            board.setValue(x-2,y,PEG);
            return board;
        }
        else if(direction.equals("up"))
        {
            board.setValue(x,y,EMPTY);
            board.setValue(x,y-1,EMPTY);
            board.setValue(x,y-2,PEG);
            return board;
        }
        else if(direction.equals("down"))
        {
            board.setValue(x,y,EMPTY);
            board.setValue(x,y+1,EMPTY);
            board.setValue(x,y+2,PEG);
            return board;
        }

        System.out.println("there is not such direction, method turn on startBoard class");
        return null;
    }

    public boolean isLegal(int x, int y){
        if(board[y][x]==BORDER)   //and not if(board[x][y]==BORDER)
            return false;

        return true;
    }

    public boolean canTurn(String direction,int x,int y){
        if(direction.equals("right") && x < BOARD_SIZE - 2)
        {
            if (board[y][x] == PEG && board[y][x + 1] == PEG && board[y][x + 2] == EMPTY)
                return true;
        }
        else if(direction.equals("left") && x > 1)
        {
            if (board[y][x] == PEG && board[y][x - 1] == PEG && board[y][x - 2] == EMPTY)
                return true;

        }
        else if(direction.equals("up") && y > 1)
        {
            if (board[y][x] == PEG && board[y - 1][x] == PEG && board[y - 2][x] == EMPTY)
                return true;

        }
        else if(direction.equals("down") && y < BOARD_SIZE - 2)
        {
            if (board[y][x] == PEG && board[y + 1][x] == PEG && board[y + 2][x] == EMPTY)
                return true;
        }

        return false;
    }

    public void setValue(int x, int y, int value)
    {
        board[y][x]=value;  //and not board[x][y]=value;
    }

    //for square nxn board
    public int boardSize(){
        return board.length;
    }

    public boolean isWithinBoard(int x, int y){

        //check bounds
        if (x < 0 || y < 0 || x >= BOARD_SIZE || y >= BOARD_SIZE) return false;
        //left top corner
        if (x < CORNER_SIZE && y < CORNER_SIZE) return false;
        //right top corner
        if(x >= BOARD_SIZE - CORNER_SIZE && y < CORNER_SIZE) return false;
        //left bottom corner
        if(x < CORNER_SIZE && y >= BOARD_SIZE - CORNER_SIZE) return false;
        //right bottom corner
        if(x >= BOARD_SIZE - CORNER_SIZE && y >= BOARD_SIZE - CORNER_SIZE) return false;

        return true;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int[] row : board) {
            for(int cell : row){
                if(cell<CHAR_REPRESENTATION.length && cell >= 0) {
                    sb.append(CHAR_REPRESENTATION[cell]);
                }else{
                    sb.append(ERROR);
                }
            }
            sb.append("\n"); //new line
        }
        return sb.toString();
    }
}

待办事项:
代码可以运行,但需要进一步深入测试和调试。

有什么不明白的地方,尽管问。