1

我正在开发一个数独求解程序，我需要一个数组列表来保存 9x9 板上每个方块的数字 1 到 9。这些数组列表中的每一个都对应于可以进入该方格的可能数字，如果一个数字不能进入该方格，则将其从列表中删除。

我希望能够拉出它正在处理的当前正方形的数组列表，例如，如果我想从对应于正方形 (3,5) 的数组列表中删除数字 7

arrayOfLists[3][5].remove(Integer.valueOf(7));

但是我无法弄清楚如何做到这一点。当我尝试创建数组时，我在声明数组列表的行上收到此错误

无法创建 ArrayList 的通用数组

这是我的代码：

    //create arraylist
    ArrayList<Integer> nums = new ArrayList<Integer>();

    //fill arraylist with numbers 1-9
    for (int i = 1; i < 10; i++) {
        nums.add(i);
    }

    //create 9x9 array of arraylists
    ArrayList<Integer>[][] array = new ArrayList<Integer>[9][9];

    //fill each element of array with arraylist of numbers 1-9
    for(int i = 0; i<9; i++){
        for(int j = 0; j<9; j++){
            array[i][j] = nums;
        }       
    }

}

我这样做不正确还是无法创建数组列表数组？如果不可能，那我该怎么做呢？

4

5 回答 5

1

使用位域而不是数组列表。也就是说，使用一个整数，其中 1-9 位表示数字的可能性。测试、添加、删除单个数字是 O(1)，并且它具有固定的内存大小。将整数封装在它自己的知道操作的对象中。

于 2013-08-24T13:25:02.063 回答
1

每当我看到列表列表时，警钟就会开始响起。你真正想要这种东西的情况确实很少见，这不是其中之一。

你有一个固定的棋盘，由 9 个固定的方格、列和行组成，每个位置可能有一个数字 1-9。

对所有这些概念都使用数组，因为它们的大小是固定的，并且您需要直接访问每个元素 - 集合没有任何好处，反而会成为障碍。使用逻辑（可能是集合）确保数字在每个区域中只使用一次。

于 2013-08-24T00:56:51.930 回答
0

您可以完全删除使用 2d 的东西，并通过给每个方块一个 1...81 中的唯一数字来保留一个列表。因此，如果您正在使用 3,5 单元格，这意味着它是列表中的 9*2+5 = 23rd 项目。这将大大简化列表操作。给定 (3,5) 类型的参考，您可以使用一种方法来给出唯一的单元格索引

于 2013-08-24T12:47:24.297 回答
0

一些东西：

1) 在你的 for 循环中， array[i][j] = nums; 这将在数​​组的每个元素中产生相同的对象。如果您在数组的一个元素上调用 remove()，它将影响所有其他元素。您想为每个元素构建一个单独的列表对象。

2）程序到接口；将 nums 声明为 List 而不是 ArrayList。

3) 使用列表列表，而不是任何列表数组。

    List<List<List<Integer>>> list = new ArrayList<List<List<Integer>>>();
    for(int i = 0; i<9; i++){
        List<List<Integer>> row = new ArrayList<List<Integer>>();
        for(int j = 0; j<9; j++){
            List<Integer> nums = new ArrayList<Integer>();
            for (int k = 1; k < 10; k++) {
                nums.add(i);
            }
            row.add(nums);
        }
        list.add(row);
    }

    // You can still get an element by index
    int x = list.get(3).get(1).remove(6);

但这有点笨拙。您可能要考虑编写一个代表板的类。这样你至少会有更好地抽象它的操作。

于 2013-08-24T00:29:00.880 回答
-1

好的，我将把它作为答案发布，因为它似乎对我有用，而且我还没有看到任何陷阱。

private static class IntegerArrayList extends ArrayList<Integer> {
    IntegerArrayList () { super(); }
    IntegerArrayList (Collection<? extends Integer> c) { super(c); }
    IntegerArrayList (int initialCapacity) { super(initialCapacity); }
}

现在你可以说类似 

IntegerArrayList[][] array = new IntegerArrayList[9][9];

并且像 array[1][2] 这样的元素将继承所有 ArrayList 方法（array[1][2].remove(something)工作正常）。我让班级private static认为如果这是你唯一使用它的地方，你可以将它嵌套在其他班级中，但如果你愿意，你可以将其公开。ArrayList另外，我从;复制了所有三个构造函数。您可以消除不需要的，但我认为没有令人信服的理由。

我认为这个问题是new ArrayList<Integer>[9][9]被禁止的，因为它会创建一个不会进行类型检查的数组（因为“类型擦除”）。但我认为添加您自己的继承自的非泛型类型可以ArrayList<Integer>恢复类型安全性。

但我不是一般的专家，如果有人比我更有知识，发现这个解决方案存在问题，我也不会感到惊讶。但它对我来说似乎工作得很好，没有关于未检查类型的东西或任何东西的编译器警告。

（PS 我把这个作为一个可能的通用解决方案来解决一个经常被问到的问题。但实际上，对于这个特定的问题，我可能只使用一个固定大小的布尔数组而不是一个 ArrayList，就像其他人一样，或者如果速度是一个真正的问题，我什至可能会在整数上做一些事情。）

于 2013-08-24T00:59:31.823 回答