php - 哈希游戏中一个岛屿的所有可能组合

Question

这是游戏:Hashiwokakero .

为了解决这个问题，我需要找到所有可能的链接 + 每个岛屿周围岛屿的组合。

约束是 1 或 2 个链接，一个组合足以为目标岛屿创建链接。

例如，我有一个岛['A' => 3]，这意味着它需要解决3个链接，并且它有3个邻居['B', ' C', 'D'].

我想找到一个可以产生这样一个数组的算法:

[
    ['B' => 1, 'C' => 1, 'D' => 1],
    ['B' => 1, 'C' => 2],
    ['B' => 1, 'D' => 2],
    ['B' => 2, 'C' => 1],
    ['B' => 2, 'D' => 1],
    ['C' => 1, 'D' => 2],
    ['C' => 2, 'D' => 1]
];

谢谢。

Answer 1

如果您想找到每个邻居的所有链接组合(0、1 或 2)，链接总数是固定的，那么您可以使用以下递归函数:

function getPossibleLinks($value, $neighbors) { 
    if ($value == 0) return [[]];
    $max = min(2, $value);
    $min = 2 - min(count($neighbors) * 2 - $value, 2);
    if ($min > 2) {
        throw new Exception('Not possible to assign that many links');
    }
    $results = [];
    for ($count = $min; $count <= $max; $count++) {
        $nextResults = getPossibleLinks($value - $count, array_slice($neighbors, 0, -1));
        foreach($nextResults as $result) {
            if ($count) $result[end($neighbors)] = $count;
            $results[] = $result; 
        }
    }
    return $results;
}

您需要将链接数作为第一个参数 ($value) 传递给它，并将邻居数组作为字符串数组传递给它。

调用示例:

$results = getPossibleLinks(3, ["B", "C", "D"]);

此调用后，$results 将具有以下内容:

[
    ['B' => 2, 'C' => 1],
    ['B' => 1, 'C' => 2],
    ['B' => 2, 'D' => 1],
    ['B' => 1, 'C' => 1, 'D' => 1],
    ['C' => 2, 'D' => 1],
    ['B' => 1, 'D' => 2],
    ['C' => 1, 'D' => 2]
]

查看它在 eval.in 上运行.