如何利用backTracking获取二维列表中的案例数

Question

我想知道如何解决维度列表中的案例数。

arr = [[0] * 2 for _ in range(2)]
count = 0

def BackTracking(index):
    global count
    if index == 4:
        print(arr)
        return

    for i in range(2):
        for j in range(2):
            if arr[i][j] == 0:
                for k in range(3):
                    arr[i][j] = k
                    BackTracking(index+1)
                    arr[i][j] = 0

BackTracking(0)
print(count)

我的代码在结果中有很多重复。如何通过回溯获得二维列表中的病例数？

Answer 1

我想，即使你没有这么说，你也在试着把数字0、1和2排列在4个方框中。在这种情况下，您不希望函数中有这两个外部循环。每个对BackTracking的调用都负责准确地填写一个框--由“索引”指定的框。你不填充其他的--你打电话给BackTracking(1)来填充第二个框，它调用BackTracking(2)来填充下一个框。这意味着您必须能够从index中提取x和y坐标，幸运的是，这并不难。

我想这就是你的本意：

arr = [[0] * 2 for _ in range(2)]
count = 0

def BackTracking(index):
    global count
    if index == 4:
        count += 1
        print(arr)
        return

    i = index % 2
    j = index // 2

    for k in range(3):
        arr[i][j] = k
        BackTracking(index+1)
        arr[i][j] = 0

BackTracking(0)
print(count)