如何使用 z3 Solver 解决 Kirkman 的女学生问题？

Question

我是 SMT 问题的新手，并尝试使用 Dennis Yurichev 编写的示例在 SAT/SMT 中复制如何使用 z3/MK85 解决柯克曼女学生问题。但是当我尝试获取模型时（我使用的是Z3）：

m["%d_%d" % (person , day)]

Python 有一些错误：

Traceback (most recent call last):

File "", line 1, in

File "D:\Z3\z3-master\z3-master\build\python\z3\z3.py", line 6138, in __getitem___z3_assert(False, "Integer, Z3 declaration, or Z3 constant expected")

File "D:\Z3\z3-master\z3-master\build\python\z3\z3.py", line 92, in _z3_assert raise Z3Exception(msg) z3.z3types.Z3Exception: Integer, Z3 declaration, or Z3 constant expected

不知道我是不是看错了模特的表情？ .我很想调试它。另外不知道z3有没有别的办法解决，z3和mk85的表达差异

from z3 import *
import itertools
PERSONS , DAYS , GROUPS = 15, 7, 5
s=Solver()
tbl=[[BitVec("%d_%d"%(person , day), 16) for day in range(DAYS)] for person in range(PERSONS)]
for person in range(PERSONS):
   for day in range(DAYS):
      s.add(And(tbl[person][day]>=0, tbl[person][day] < GROUPS))
def only_one_in_pair_can_be_equal(l1, l2):
   assert len(l1)==len(l2)
   expr=[]
   for pair_eq in range(len(l1)):
             tmp=[]
             for i in range(len(l1)):
                     if pair_eq==i:
                             tmp.append(l1[i]==l2[i])
                     else:
                             tmp.append(l1[i]!=l2[i])
             expr.append(And(*tmp))
   s.add(Or(*expr))
for pair in itertools.combinations(range(PERSONS), r=2):
   only_one_in_pair_can_be_equal (tbl[pair[0]], tbl[pair[1]])
assert s.check()
m=s.model()
print("group for each person:")
print("person:"+"".join([chr(ord('A')+i)+" " for i in range(PERSONS)]))
for day in range(DAYS):
   print("day=%d:" % day)
   for person in range(PERSONS):
      print(m["%d_%d" % (person , day)])  #error
   print("")

def persons_in_group(day, group):
     rt=""
     for person in range(PERSONS):
             if m["%d_%d" % (person , day)]==group:#error
                     rt=rt+chr(ord('A')+person)
     return rt
for day in range(DAYS):
     print( "day=%d:" % day)
     for group in range(GROUPS):
             print(persons_in_group(day, group)+" ")
     print(" ")

我希望调试它或以其他方式解决这个问题。

Answer 1

这里的问题是您正在使用不正确的索引访问模型。而不是：

m["%d_%d" % (person , day)]

使用：

m[tbl[person][day]]

（你有两个这样的实例，你需要在两个实例中都这样做。）

如何使用 z3 Solver 解决 Kirkman 的女学生问题？

How to use z3 Solver to solve Kirkman’s Schoolgirl Problem?

python

smt

z3