ABC Puzzle-约束满足问题

Question

ABC 是一个 5x5 棋盘上的逻辑谜题。在每一行和每一列中，必须恰好有 3 个字母（A、B、C）和 2 个空单元格。此外，对于每一行和每一列，还有关于哪个是 row/column 中第一个字母的信息。这并不意味着它是第一个单元格中的字母，而是该行中的第一个字母（第一个字母前可以有空 spaces）。 This 是板及其信息。

我需要帮助找出每行和每列中第一个字母的约束。

我已经为每行和每列设置了约束条件，但就是不知道如何找到行或列中第一个字母的确切位置。这是我目前所拥有的。

*请注意，我对 A、B、C 使用了 1、2、3，对空单元格使用了“_”（单 space）和“__”（双 space） , 为了仍然留在 'AllDifferentConstraint'.

from constraint import *

if __name__ == "__main__":

problem = Problem(BacktrackingSolver())

variables = []
for i in range(0, 25):
    variables.append(i)
domain= []
for i in range(1,4):
    domain.append(i)

domain.append("_")
domain.append("__")

problem.addVariables(variables, domain)

for row in range(5):
    problem.addConstraint(AllDifferentConstraint(), [row * 5 + i for i in range(5)])

for col in range(5):
    problem.addConstraint(AllDifferentConstraint(), [col * 5 + i for i in range(5)])


solution = problem.getSolution()
print(solution)

Answer 1

免责声明：

我的代码可能看起来有点过度设计
对于最近做了很多 CP 事情的人来说，这个库的可用约束集看起来很奇怪 and/or 不完整（与工业强度相比 Gecode）
- 我认为这个解决方案是 hack（但对于这个玩具问题来说已经足够了）
我保留了您的大部分代码，但将空格更改为数字 (8, 9) 以便更好地可视化

基本思路 假设尺寸是先验固定的，当从切片的 前面看时，正好有 5 个有效的约束条件 :

0: _  __ TARGET ...dontcare
1: __ _  TARGET ...dontcare
2: _  TARGET    ...dontcare
3: __ TARGET    ...dontcare
4: TARGET       ...dontcare

作为一个来自 SAT 解决（在 CP 之前）的人，我觉得用从句推理很自然。以上很容易用布尔逻辑表示（与上面的顺序不同）：

   (  pos0 = F                  )
OR ( (pos0 = _ )  and (pos1 = F) )
OR ( (pos0 = __)  and (pos1 = F) )
OR ( (pos0 = __) and (pos1 = _  ) and (pos2 = F)
OR ( (pos0 = _ )  and (pos1 = __ ) and (pos2 = F)

通常人们会使用一个很好实现的约束/传播器（使用 SAT 技术），但是这个库缺少通常的东西。

但对我们的拯救：FunctionConstraint 允许我们构建一个简单的传播器。这实际上是一个很好的设计（对于小而相对容易的问题）！

一些备注：

clause 构建我们基于布尔逻辑的传播器（以非高效方式）
row 和 clause returns 基于我们想要的一维索引
reverse 让我们在约束需要从末端（而不是在前端）起作用时重用逻辑
我们使用部分函数应用程序使调用紧凑
numpy 仅用作快速可视化工具（没有什么比从 dict 推理矩阵解决方案更糟糕的了）

代码

""" ORIGINAL CODE """

from constraint import *

problem = Problem(BacktrackingSolver())

variables = []
for i in range(0, 25):
    variables.append(i)
domain= []
for i in range(1,4):
    domain.append(i)

domain.append(8)
domain.append(9)

problem.addVariables(variables, domain)

for row in range(5):
    problem.addConstraint(AllDifferentConstraint(), [row * 5 + i for i in range(5)])

for col in range(5):
    problem.addConstraint(AllDifferentConstraint(), [col * 5 + i for i in range(5)])

""" ADDITIONS """

from functools import partial  

def clause(target, p0, p1, p2, p3, p4):
  wildcards = [8, 9]
  return (p0 == target) or                                              \
        ( (p0 in wildcards) and (p1 == target) ) or                    \
        ( (p0 in wildcards) and (p1 in wildcards) and p2 == target ) 


row = lambda x: [x * 5 + i for i in range(5)]
col = lambda x: [x + i * 5 for i in range(5)]
reverse = lambda x: list(reversed(x))

problem.addConstraint(partial(clause, 3), reverse(row(0))) # C
problem.addConstraint(partial(clause, 2), reverse(row(1))) # B
problem.addConstraint(partial(clause, 3), reverse(row(2))) # C
problem.addConstraint(partial(clause, 1), row(2))          # A
problem.addConstraint(partial(clause, 2), row(3))          # B
problem.addConstraint(partial(clause, 1), col(0))          # A
problem.addConstraint(partial(clause, 2), col(1))          # B
problem.addConstraint(partial(clause, 1), col(3))          # A
problem.addConstraint(partial(clause, 3), reverse(col(0))) # C
problem.addConstraint(partial(clause, 3), reverse(col(2))) # C
problem.addConstraint(partial(clause, 3), reverse(col(3))) # C

""" SOLVE """

solution = problem.getSolution()
print(solution)

""" VISUALIZE """

import numpy as np
matrix = np.zeros((5, 5), dtype=int)
matrix[np.unravel_index(range(5*5), (5,5))] = [solution[i] for i in range(5*5)]
print(matrix)

输出

λ python C:\Tmp\constr.py
{10: 9, 13: 3, 11: 1, 12: 2, 0: 9, 3: 1, 5: 1, 8: 2, 15: 9, 18: 8, 14: 8, 20: 3, 23: 9, 1: 2, 2: 8, 6: 9, 7: 3, 16: 2, 17: 3, 4: 3, 9: 8, 19: 1, 22: 8, 21: 2, 24: 1}

[[9 2 8 1 3]
 [1 9 3 2 8]
 [9 1 2 3 8]
 [9 2 3 8 1]
 [3 2 8 9 1]]

结果令人惊讶地看起来是正确的 ;-)，与您的原始任务相比：

ABC Puzzle-约束满足问题

ABC Puzzle- Constraint Satisfaction Problem

python

artificial-intelligence

constraints

constraint-programming

discrete-optimization