수정 된 Queens 문제에 대한 부울 표현식

Aug 20 2020

여기 에서 N Queens 문제에 대한 부울 표현식을 보았습니다 .

수정 된 N 퀸즈 규칙은 더 간단합니다.

ap * p 체스 판의 경우 N 개의 퀸을 배치하고 싶습니다.

  1. 퀸즈가 인접하게 배치되고 행이 먼저 채워집니다.
  2. 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