นิพจน์บูลีนสำหรับปัญหา Queens ที่แก้ไข
Aug 20 2020
ผมเห็นการแสดงออกบูลสำหรับปัญหา N ควีนส์จากที่นี่
กฎ N ควีนส์ที่แก้ไขของฉันง่ายกว่า:
สำหรับกระดานหมากรุก ap * p ฉันต้องการวาง N ราชินีในลักษณะนั้น
- ควีนส์จะถูกวางไว้ใกล้ ๆ แถวจะเต็มก่อน
- p * p ขนาดกระดานหมากรุกจะถูกปรับจนกว่าจะสามารถบรรจุราชินีได้ N
ตัวอย่างเช่นพูดว่า N = 17 จากนั้นเราต้องการกระดานหมากรุก 5 * 5 และตำแหน่งจะเป็น:
Q_Q_Q_Q_Q
Q_Q_Q_Q_Q
Q_Q_Q_Q_Q
Q_Q_*_*_*
*_*_*_*_*
คำถามคือฉันพยายามหานิพจน์บูลีนสำหรับปัญหานี้
คำตอบ
1 IoannisFilippidis Sep 10 2020 at 01:02
ปัญหานี้สามารถแก้ไขได้โดยใช้แพ็คเกจ Python humanizeและomega.
"""Solve variable size square fitting."""
import humanize
from omega.symbolic.fol import Context
def pick_chessboard(q):
ctx = Context()
# compute size of chessboard
#
# picking a domain for `p`
# requires partially solving the
# problem of computing `p`
ctx.declare(p=(0, q))
s = '''
(p * p >= {q}) # chessboard fits the queens, and
/\ ((p - 1) * (p - 1) < {q}) # is the smallest such board
'''.format(q=q)
u = ctx.add_expr(s)
d, = list(ctx.pick_iter(u)) # assert unique solution
p = d['p']
print('chessboard size: {p}'.format(p=p))
# compute number of full rows
ctx.declare(x=(0, p))
s = 'x = {q} / {p}'.format(q=q, p=p) # integer division
u = ctx.add_expr(s)
d, = list(ctx.pick_iter(u))
r = d['x']
print('{r} rows are full'.format(r=r))
# compute number of queens on the last row
s = 'x = {q} % {p}'.format(q=q, p=p) # modulo
u = ctx.add_expr(s)
d, = list(ctx.pick_iter(u))
n = d['x']
k = r + 1
kword = humanize.ordinal(k)
print('{n} queens on the {kword} row'.format(
n=n, kword=kword))
if __name__ == '__main__':
q = 10 # number of queens
pick_chessboard(q)
การแทนการคูณ (และการหารจำนวนเต็มและโมดูโล) ด้วยแผนภาพการตัดสินใจแบบไบนารีมีเลขชี้กำลังที่ซับซ้อนในจำนวนตัวแปรตามที่พิสูจน์แล้วใน: https://doi.org/10.1109/12.73590