3

KenKen パズルは、エッジが接続されたドメインに分割されたラテン方陣です。1 つのセル、同じ行または列内の 2 つの隣接するセル、行またはエルに配置された 3 つのセルなどです。各ドメインには、ターゲットを与えるラベルがあります。数値と、ドメインのセル内の数値に適用してターゲット数値を生成する単一の算術演算 (+-*/)。(ドメインにセルが 1 つしかない場合、演算子は指定されず、ターゲットだけが指定されます --- 正方形は自動的に解決されます。演算子が - または / の場合、ドメインにはセルが 2 つしかありません。)パズルは、ドメインの境界とラベルと一致するラテン方陣を (再) 構築することです。(解が一意ではないパズルを一度だけ見たことがあると思います。)

セル内の数値は、1 からパズルの幅 (高さ) までの範囲で指定できます。通常、パズルは 1 辺が 4 または 6 セルですが、任意のサイズのパズルを検討してください。公開されたパズル (4x4 または 6x6) のドメインは、通常 5 つ以下のセルしかありませんが、これも厳しい制限ではないようです。(ただし、パズルのドメインが 1 つだけの場合、その次元のラテン方陣と同じ数の解が存在することになります...)

KenKen ソルバーを作成するための最初のステップは、最初はドメインのジオメトリを無視して、任意のドメインで可能な数値の組み合わせを生成できるルーチンを用意することです。(3 つのセルの行のような線形ドメインは、解決されたパズルで重複した数字を持つことはできませんが、当面はこれを無視します。) ケースバイケースで加算ラベルを処理する Python 関数を作成できました。パズルの幅、ドメイン内のセルの数、およびターゲットの合計であり、ターゲットに加算される有効な数値のタプルのリストを返します。

乗算のケースは私を避けます。与えられたサイズのパズルで与えられたサイズのドメインで達成可能な製品に等しいキーを持つ辞書を取得できます。値は、製品を与える要因を含むタプルのリストです。しかし、ケースを解決することはできません-ケースバイケースのルーチンであり、悪いものでもありません。

与えられた積を素数に因数分解するのは簡単に思えますが、素数のリストを必要な数の因数に分割することは私を困惑させます。(私は Knuth の TAOCP の Volume 4 の Fascicle 3 について熟考しましたが、彼のアルゴリズムの説明を「理解する」方法を学んでいないので、集合分割のための彼のアルゴリズムが出発点になるかどうかはわかりません。Knuth の説明を理解することは、別の質問！）

一般的なドメインとパズルのサイズの「乗算」辞書を事前に計算し、ロード時間をオーバーヘッドまでチョークするだけで十分ですが、そのアプローチは、たとえば、100 個のセルを片側にパズルし、サイズが 2 ～ 50 セルのドメイン。

4

1 に答える 1

5

単純化された目標: 整数の数が固定されている特定の積を形成するために乗算するすべての整数の組み合わせを列挙する必要があります。

これを解決するために必要なのは、ターゲット数の素因数分解であり、組み合わせアプローチを使用して、これらの因数から可能なすべての副積を形成します。(パズルには他にもいくつかの制約があり、可能性のあるすべてのサブプロダクトを取得すると簡単に含めることができます。たとえば、エントリが よりも大きくなることはなくmax_entry、使用する整数の固定数があるなどですn_boxes_in_domain。)

たとえば、 if max_entry=6、n_boxes_in_domain=3、およびtarget_number=20: 20 は (2, 2, 5) を生成します。これは (2, 2, 5) と (1, 4, 5) になります。

これの秘訣は、考えられるすべてのサブプロダクトを形成することであり、以下のコードはこれを行います。可能なすべての単一ペアを形成する要因をループし、これを再帰的に実行して、すべての単一ペアまたは複数ペアのすべての可能なセットを提供します。(非効率ですが、大きな数でも素因数分解は小さくなります):

def xgroup(items):
    L = len(items)
    for i in range(L-1):
        for j in range(1, L):
            temp = list(items)
            a = temp.pop(j)
            b = temp.pop(i)
            temp.insert(0, a*b)
            yield temp
            for x in xgroup(temp):
                yield x

def product_combos(max_entry, n_boxes, items):
    r = set()
    if len(items)<=n_boxes:
        r.add(tuple(items))
    for i in xgroup(items):
        x = i[:]
        x.sort()
        if x[-1]<=max_entry and len(x)<=n_boxes:
            r.add(tuple(x))
    r = [list(i) for i in r]
    r.sort()
    for i in r:
        while len(i)<n_boxes:
            i.insert(0, 1)
    return r

素因数の生成はあなたに任せますが、これはうまくいくようです

max_entry=6, n_boxes=3, items=(2,2,5)
[2, 2, 5]
[1, 4, 5]

そして、より困難なケースでは、target_number=2106 

max_entry=50, n_boxes=6, items=(2,3,3,3,3,13)
[2, 3, 3, 3, 3, 13]
[1, 2, 3, 3, 3, 39]
[1, 2, 3, 3, 9, 13]
[1, 1, 2, 3, 9, 39]
[1, 1, 2, 3, 13, 27]
[1, 1, 2, 9, 9, 13]
[1, 1, 1, 2, 27, 39]
[1, 3, 3, 3, 3, 26]
[1, 3, 3, 3, 6, 13]
[1, 1, 3, 3, 6, 39]
[1, 1, 3, 3, 9, 26]
[1, 1, 3, 3, 13, 18]
[1, 1, 3, 6, 9, 13]
[1, 1, 1, 3, 18, 39]
[1, 1, 1, 3, 26, 27]
[1, 1, 1, 6, 9, 39]
[1, 1, 1, 6, 13, 27]
[1, 1, 1, 9, 9, 26]
[1, 1, 1, 9, 13, 18]
于 2009-06-06T06:35:33.773 に答える