在网格中回溯

Question

假设有一个1和0的2D网格,例如 -

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] and [1][1],只有[0][1]就是1,所以[0][0]在新的网格将是1.类似地,出[0][1], [0][2], [1][1] and [1][2],两者[0][1] and [1][2]都1,所以[0][1]在new_grid将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框,它们都可以是1s或0s有效配置(我认为这是我们可以灵活操作它们的程度,虽然我不确定).

我的问题是这个 - 这个算法在增长中可能是指数级的,并且它需要花费大量时间来说明50X10.

有没有其他方法可以解决这个问题？或者是否有任何聪明的算法不能通过每个可能的配置来计算它们？

Answer 1

嗯，所以我想到了一个 2x3 newGrid，如下所示：

newGrid: 0 1 0
         0 0 0

需要由这些 3x4 oldGrid 之一生成：
每个都_可以是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 个 oldGrid：

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 代码，但我希望解决方案是正确的和/或指明方向