求助：基于回溯算法的蜂巢Hidato解谜Java代码实现

问题需求 #

我有一个蜂巢结构的表格，需要编写Java代码读取该表格作为输入，输出解谜后的表格。解谜要求如下：

• 表格中必须存在一条哈密顿路径，从数字1的位置出发，终止于给定的最大值位置。
• 已完成输入部分代码，需要帮忙实现基于回溯算法的解谜功能。

用户现有输入代码 #

public static void main(String[] args) {
    int n;
    List<Integer> w=new ArrayList<>();
    Scanner scan=new Scanner(System.in);
    n=scan.nextInt();
    int [][] s=new int[2*n-1][2*n-1];
    int [][] v=new int[2*n-1][2*n-1];
    for(int i=0;i<n;i++)
    {
        s[i]=new int[i+n];
                for(int j=0;j<i+n;j++)
                {
                    s[i][j]=scan.nextInt();
                    if(s[i][j]>0)
                    {
                        w.add(s[i][j]);
                        v[i][j]=1;
                    }
                    else if(s[i][j]==-1)
                        v[i][j]=1;
                    else if(s[i][j]==0)
                        v[i][j]==0;

                }
    }
    for(int i=n;i<2*n-1;i++)
    {
        s[i]=new int[2*n-2-i%n];
        for(int j=0;j<2*n-i%n-2;j++)
        {
            s[i][j]=scan.nextInt();
            if(s[i][j]>0)
                w.add(s[i][j]);
        }
    }
    w.sort(naturalOrder());
}

完整实现代码 #

先修正输入逻辑的错误，再加入回溯算法核心逻辑：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class HoneycombSolver {
    // 蜂巢格子的6个邻接方向，根据行的上下半区调整
    private static final int[][] TOP_HALF_DIRS = {{-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, 0}, {1, 1}};
    private static final int[][] BOTTOM_HALF_DIRS = {{-1, -1}, {-1, 0}, {0, -1}, {0, 1}, {1, -1}, {1, 0}};

    private static int n;
    private static int[][] grid;
    private static boolean[][] visited;
    private static int maxNum;
    private static int totalCells;
    private static boolean solved = false;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int totalRows = 2 * n - 1;
        grid = new int[totalRows][];
        visited = new boolean[totalRows][];
        List<Integer> givenNums = new ArrayList<>();
        int startRow = -1, startCol = -1;

        // 读取上半区格子（0到n-1行）
        for (int i = 0; i < n; i++) {
            int cols = i + n;
            grid[i] = new int[cols];
            visited[i] = new boolean[cols];
            for (int j = 0; j < cols; j++) {
                grid[i][j] = scan.nextInt();
                if (grid[i][j] > 0) {
                    givenNums.add(grid[i][j]);
                    visited[i][j] = true; // 已填数字的格子标记为已访问
                    if (grid[i][j] == 1) {
                        startRow = i;
                        startCol = j;
                    }
                } else if (grid[i][j] == -1) {
                    visited[i][j] = false; // 空格子待填充
                } else if (grid[i][j] == 0) {
                    visited[i][j] = true; // 无效格子跳过
                }
            }
        }

        // 读取下半区格子（n到2n-2行）
        for (int i = n; i < totalRows; i++) {
            int cols = totalRows - (i - n + 1);
            grid[i] = new int[cols];
            visited[i] = new boolean[cols];
            for (int j = 0; j < cols; j++) {
                grid[i][j] = scan.nextInt();
                if (grid[i][j] > 0) {
                    givenNums.add(grid[i][j]);
                    visited[i][j] = true;
                } else if (grid[i][j] == -1) {
                    visited[i][j] = false;
                } else if (grid[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }

        // 计算最大值和总有效格子数
        if (!givenNums.isEmpty()) {
            maxNum = Collections.max(givenNums);
        }
        totalCells = 0;
        for (int i = 0; i < totalRows; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] != 0) {
                    totalCells++;
                }
            }
        }

        // 启动回溯解谜
        if (startRow != -1 && startCol != -1) {
            backtrack(startRow, startCol, 1);
        }

        // 输出解谜后的蜂巢表格
        printGrid();
        scan.close();
    }

    private static void backtrack(int row, int col, int currentNum) {
        // 终止条件：到达最大值且遍历完所有格子
        if (currentNum == maxNum && currentNum == totalCells) {
            solved = true;
            return;
        }
        // 到达最大值但未遍历完，直接返回
        if (currentNum == maxNum) {
            return;
        }

        // 根据行区选择邻接方向
        int[][] dirs = (row < n) ? TOP_HALF_DIRS : BOTTOM_HALF_DIRS;

        for (int[] dir : dirs) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            // 检查新位置是否合法
            if (isValid(newRow, newCol)) {
                int nextNum = currentNum + 1;
                // 若该位置已有数字，必须等于下一个数才能继续
                if (grid[newRow][newCol] > 0 && grid[newRow][newCol] != nextNum) {
                    continue;
                }

                // 标记状态
                boolean wasGiven = (grid[newRow][newCol] > 0);
                if (!wasGiven) {
                    grid[newRow][newCol] = nextNum;
                }
                visited[newRow][newCol] = true;

                // 递归探索
                backtrack(newRow, newCol, nextNum);

                // 找到解后直接终止所有递归
                if (solved) {
                    return;
                }

                // 回溯恢复状态
                visited[newRow][newCol] = false;
                if (!wasGiven) {
                    grid[newRow][newCol] = -1;
                }
            }
        }
    }

    private static boolean isValid(int row, int col) {
        if (row < 0 || row >= grid.length) return false;
        if (col < 0 || col >= grid[row].length) return false;
        return !visited[row][col] && grid[row][col] != 0;
    }

    private static void printGrid() {
        for (int i = 0; i < grid.length; i++) {
            // 打印前置空格模拟蜂巢缩进
            if (i >= n) {
                for (int k = 0; k < i - n + 1; k++) {
                    System.out.print("  ");
                }
            } else {
                for (int k = 0; k < n - i - 1; k++) {
                    System.out.print("  ");
                }
            }

            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) continue;
                System.out.printf("%2d ", grid[i][j]);
            }
            System.out.println();
        }
    }
}

代码说明 #

1. 输入逻辑修正：

   • 修复原代码中赋值错误（v[i][j]==0改为visited[i][j] = false）
   • 修正下半区格子列数计算错误，确保蜂巢结构正确
   • 区分已填数字、空格子、无效格子的状态标记

2. 回溯算法核心：

   • 针对蜂巢上下半区的不同结构，使用两组邻接方向数组
   • 递归尝试每个合法邻接格子，严格遵循数字递增规则
   • 找到解后立即终止递归，避免冗余计算

3. 输出优化：

   • 添加前置空格模拟蜂巢的缩进布局，输出结果更直观

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