当我检查行/列中的重复哈希映射时，程序无限期地运行

Question

我正在编写一个数独板生成器。我想到使用哈希映射来确保数字不会在同一行/列中重复。键是一个字符串（“行”/“列”+行/列数）。填充/检查几行后，程序停止放置数字并无限期运行。我不确定我错过了什么。

如果我在 checkMap 方法中检查 list.size() (== 9)，程序会正常完成，但有些数字是错误的。

班级板{

ArrayList<Integer> list;
Map<String, ArrayList<Integer>> map = new HashMap<>();
String key;
int value;
int[][] board = new int[9][9];

public Board() {
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            do {
                value = (int) Math.floor(Math.random() * 9 + 1); 
            } while (!checkValue(row, col, value));
                            //board[row][col] = value;
        }
    }
}

boolean checkValue(int row, int col, int value) {
    key = "row" + row;
    if (!checkMap(key, value)) {
        return false;
    }
    key = "col" + col;
    if (!checkMap(key, value)) {
        return false:
    }
    return true;
}

boolean checkMap(String key, int value) {
    list = new ArrayList<>();
    if (map.containsKey(key) {
        list = map.get(key);
        if (list.contains(value)) {
            return false;
        }
    }
    list.add(value);
    map.put(key, list);
    return true;
}

}

Answer 1

代码中的一个具体问题是，在

checkValue

方法（应用于特定单元格和值）中，它首先检查该行（调用

checkMap

），然后如果可能，则存储该行的值，然后 then 检查该列，并可能发现该单元格不可用。然后它返回 false，并且 for 循环将使用不同的值再次尝试。但随后它已经存储了该行中使用的第一个值。

更大的问题是这种生成棋盘的方法行不通，除非你在选择随机数时非常幸运。基本上，您需要一种用于“求解”数独板的算法，并使用该算法来检查生成的板是否至少有一个解决方案（理想情况下，您可能希望它“仅”有一个解决方案）。如需一些指导，请查看问题如何使用独特的解决方案生成数独板。