python - 在网格中回溯

Question

假设有一个由 1 和 0 组成的二维网格，例如 -

0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

网格被“折叠”以形成一个少 1 行和 1 列的较小网格，因此上面的示例将“折叠”以形成 3 行 3 列的网格。

新值由以下规则确定 -

new_grid[i][j] is dependent on 
  i) old_grid[i][j], 
 ii) old_grid[i][j+1], 
iii) old_grid[i+1][j] 
 iv) old_grid[i+1][j+1]

If exactly one of the above values are 1, then new_grid[i][j] will be 1, else 0.

因此对于示例网格，在 [0][0]、[0][1]、[1][0] 和 [1][1] 中，只有 [0][1] 为 1，因此新网格中的 [0][0] 将为 1。同样，[ 0][1]、[0][2]、[1][1] 和 [1][2]，[0][1] 和 [1][2] code> 为 1，因此 new_grid 中的 [0][1] 将为 0。

输入以 new_grid 值的形式给出。我必须找出 old_grid 的可能配置数量，以便通过提供的折叠规则可以实现 new_grid。

---

我的方法

我目前想到的回溯方案是这样的——

1. 为旧网格中的每个 1 值单元格确定假想的 2X2 框，这些框将对应于新网格中的适当单元格。

2. 所有这些框都只包含一个值为 1 的单元格，因此将 1 放入每个框中的随机单元格中。

3. 递归检查在随机单元格中放入 1 是否确保每个框仍然恰好保留一个值为 1 的单元格。

4. 如果最终获得了一个网格配置，其中每个框只包含一个值为 1 的单元格，请检查配置是否可以“折叠”以获得新网格。

5. 如果不是，则使用值为 1 的不同单元格重复该过程。

如果旧网格中有一些单元格不属于任何“框”，那么它们就是我所说的“无关紧要”的单元格。

---

例如-

1 1 
0 0

对于上面的new_grid，old_grid可以是-

1 0 1
0 0 0 
0 0 0           

或

1 0 1
0 0 0
1 1 1

最后一行的单元格是“无关紧要”的单元格，因为它们不在任何 2X2 框下并且它们都可以是 1 或 0成为有效的配置(我认为这是我们可以灵活操作它们的程度，尽管我不确定)。

我的问题是 - 该算法很可能呈指数增长，并且它会花费很多时间来处理比方说 50X10 的网格。

请问还有其他方法可以解决这个问题吗？或者是否有任何聪明的算法可以不遍历所有可能的配置来计算它们？

Answer 1

嗯，所以我想到了一个像这样的 2x3 newGrid:

newGrid: 0 1 0
         0 0 0

需要由这些 3x4 oldGrids 中的任何一个生成:
每个_可以是1或0

oldGrid 1: _ 0 1 _
           _ 0 0 _
           _ _ _ _

oldGrid 2: _ 1 0 _
           _ 0 0 _
           _ _ _ _

oldGrid 3: _ 0 0 _
           _ 1 0 _
           _ _ _ _

oldGrid 4: _ 0 0 _
           _ 0 1 _
           _ _ _ _

剩下的所有 8 个点都可以用 2^8 种方式填充。所以答案是 4 * 2^8

但是，想象一下如果 newGrid 有多个 1:

newGrid: 1 1 0
         0 0 0

其中将有这 8 个 oldGrids:

oldGrid 1: 1 0 _ _
           0 0 _ _
           _ _ _ _

oldGrid 2: 0 1 _ _
           0 0 _ _
           _ _ _ _

oldGrid 3: 0 0 _ _
           1 0 _ _
           _ _ _ _

oldGrid 4: 0 0 _ _
           0 1 _ _
           _ _ _ _

oldGrid 5: _ 1 0 _
           _ 0 0 _
           _ _ _ _

oldGrid 6: _ 0 1 _
           _ 0 0 _
           _ _ _ _

oldGrid 7: _ 0 0 _
           _ 1 0 _
           _ _ _ _

oldGrid 8: _ 0 0 _
           _ 0 1 _
           _ _ _ _

从 oldGrid 1 我会产生 2^8 种组合。但请注意，其中一些与 oldGrid 6 生成的解决方案相同。是那些看起来像这样的:

oldGrid 1.1: 1 0 1 _
             0 0 0 _
             _ _ _ _

它有 2^6 个解决方案。

因此 oldGrid 1 有 2^8 - 2^6 种解决方案与 oldGrid 6 不冲突。
oldGrid 6 有 2^6 个解决方案，与 oldGrid 1 不冲突。
他们一起有 (2^8 - 2^6) + (2^8 - 2^6) + 2^6 解决方案。

1 和 6、1 和 8、2 和 5、3 和 6、3 和 8、4 和 7 有冲突的解空间，每个都有 2^6。

我认为这意味着解决方案的数量是 8 * 2^8 - 6 * 2^6。
那就是:

numberOfSolutions = numberOf1s * 4 * 2^(oldGridSize-4) - overlappingSolutionsCount
overlappingSolutionsCount = numberOfOverlappingPairs * 2^(oldGridSize-4-overlapAreaSize)  

如何计算重叠度

function countOverlappingSolutions(newGrid: an MxN matrix) {
    result = 0
    oldGridSize = (M+1) * (N+1)
    for each pair of 1s in the newGrid:
        let manhattanDistance = manhattan distance between the 1s in the pair
        let overlapAreaSize = 0

        if the 1s are in the same row or column
            if manhattanDistance == 1:
                overlapSize = 2
        else if manhattanDistance == 2
            overlapAreaSize = 1

        result += 2^(oldGridSize -4 -overlapAreaSize)

    return result
}

最终算法:

let newGrid be a MxN matrix
let numberOf1s = number of 1s in newGrid
let oldGridSize = (M+1) * (N+1)

result = numberOf1s * 4 * 2^(oldGridSize - 4) - countOverlappingSolutions(newGrid)

我无法努力编写 python 代码，但我希望解决方案是正确的和/或指明了方向