华容道程序代码Java

下面是一个华容道程序的 Java 实现代码：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class HuaRongDao {
    // 棋盘类
    static class Board {
        int[][] board;
        int height, width;

        Board(int[][] board) {
            this.board = board;
            this.height = board.length;
            this.width = board[0].length;
        }

        // 返回空格坐标
        int[] getBlank() {
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (board[i][j] == 0) {
                        return new int[]{i, j};
                    }
                }
            }
            return null;
        }

        // 移动棋子
        void move(int[] direction) {
            int[] blank = getBlank();
            int i = blank[0], j = blank[1];
            if (direction[0] == -1 && i > 0) {
                board[i][j] = board[i-1][j];
                board[i-1][j] = 0;
            } else if (direction[0] == 1 && i < height-1) {
                board[i][j] = board[i+1][j];
                board[i+1][j] = 0;
            } else if (direction[1] == -1 && j > 0) {
                board[i][j] = board[i][j-1];
                board[i][j-1] = 0;
            } else if (direction[1] == 1 && j < width-1) {
                board[i][j] = board[i][j+1];
                board[i][j+1] = 0;
            }
        }

        // 判断是否完成
        boolean isSolved() {
            int num = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (board[i][j] != num) {
                        return false;
                    }
                    num++;
                }
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 0;
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    hash = hash * 10 + board[i][j];
                }
            }
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (!(obj instanceof Board)) {
                return false;
            }
            Board other = (Board) obj;
            if (height != other.height || width != other.width) {
                return false;
            }
            for (int i = 0; i < height; i++) {
                for (int j = 0; j < width; j++) {
                    if (board[i][j] != other.board[i][j]) {
                        return false;
                    }
                }
            }
            return true;
        }
    }

    // 搜索类
    static class Search {
        Board board;
        ArrayList<int[]> path;

        Search(Board board) {
            this.board = board;
            this.path = new ArrayList<>();
        }

        // 广度优先搜索
        boolean bfs() {
            Queue<Board> queue = new LinkedList<>();
            HashSet<Board> visited = new HashSet<>();
            queue.offer(board);
            visited.add(board);
            while (!queue.isEmpty()) {
                Board curBoard = queue.poll();
                int[] blank = curBoard.getBlank();
                int i = blank[0], j = blank[1];
                for (int[] direction : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                    Board newBoard = new Board(copy(curBoard.board));
                    newBoard.move(direction);
                    if (!visited.contains(newBoard)) {
                        visited.add(newBoard);
                        path.add(direction);
                        if (newBoard.isSolved()) {
                            return true;
                        }
                        queue.offer(newBoard);
                    }
                }
            }
            return false;
        }

        // 深度优先搜索
        boolean dfs(int depth) {
            if (depth == 0) {
                return board.isSolved();
            }
            for (int[] direction : new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                Board newBoard = new Board(copy(board.board));
                newBoard.move(direction);
                if (!path.isEmpty() && reverse(direction).equals(path.get(path.size()-1))) {
                    continue;  // 不走回头路
                }
                path.add(direction);
                if (dfs(depth-1)) {
                    return true;
                }
                path.remove(path.size()-1);
            }
            return false;
        }

        // 迭代加深搜索
        boolean ids() {
            for (int depth = 1; depth < 100; depth++) {
                path.clear();
                if (dfs(depth)) {
                    return true;
                }
            }
            return false;
        }

        // 复制二维数组
        int[][] copy(int[][] board) {
            int[][] newBoard = new int[board.length][];
            for (int i = 0; i < board.length; i++) {
                newBoard[i] = board[i].clone();
            }
            return newBoard;
        }

        // 反方向
        int[] reverse(int[] direction) {
            return new int[]{-direction[0], -direction[1]};
        }
    }

    // 测试
    public static void main(String[] args) {
        int[][] board = {{1, 2, 3}, {4, 0, 5}, {6, 7, 8}};
        Search search = new Search(new Board(board));
        if (search.ids()) {
            for (int[] direction : search.path) {
                System.out.println(direction[0] + ", " + direction[1]);
            }
        } else {
            System.out.println("No solution");
        }
    }
}

这个程序实现了一个完整的华容道游戏盘面求解，可以通过广度优先搜索和迭代加深搜索实现。