修改后的皇后区问题的布尔表达式 [英] Boolean expression for modified Queens problem

问题描述

我从这里.

我修改的N个皇后规则比较简单:

My modified N queens rules are simpler:

对于p * p棋盘，我想以这样的方式放置N个皇后区，

For a p*p chessboard I want to place N queens in such a way so that

1. 皇后将相邻放置，行将首先填充.
2. p * p棋盘的大小将进行调整，直到可以容纳N个皇后为止.

例如，假设N = 17，那么我们需要一个5 * 5的棋盘，放置位置将是:

For example, say N = 17, then we need a 5*5 chessboard and the placement will be:

Q_Q_Q_Q_Q
Q_Q_Q_Q_Q
Q_Q_Q_Q_Q
Q_Q_*_*_*
*_*_*_*_*

问题是我试图为这个问题提供一个布尔表达式.

The question is I am trying to come up with a boolean expression for this problem.

推荐答案

可以使用Python包 humanize 和 omega .

This problem can be solved using the Python packages humanize and 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)

用二进制决策图表示乘法(以及整数除法和模)在变量数量上具有复杂度指数，如下所示:

Representing multiplication (and integer division and modulo) with binary decision diagrams has complexity exponential in the number of variables, as proved in: https://doi.org/10.1109/12.73590

这篇关于修改后的皇后区问题的布尔表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！