KakuroとSubset Sum、スーパーセットには連続する正の整数が含まれ、サブセットは固定サイズのkです

Question

私はKakuro Game in javaで作業しています。カクローは、スドクに似たゲームです。

Kakuroの目的は、各「領域」に重複する番号がないように、1から9までの整数でそれらの空白ブロックを記入し、領域内の空白ブロックのすべての数値が地域の「ヒントブロック」の番号。領域の例は、上記の図では赤色で示されています。

ここで私がやっているのは、与えられたカクロのパズルを自動的に解決できるAIを書くことです。これはまず、K個の要素の可能なすべての組み合わせを整数の範囲集合（1,9）から見つける必要があり、そのK要素の合計がその領域の "hintblock"に示された数と等しくなるようにする必要があります。 （この場合、Kはその領域内の空白ブロックの数です）これは、スーパーセットがはるかに均一で（1から9までの連続する整数）、サブセットが固定サイズであることを除いて、「サブセット問題」のバリエーションですK. さらに良い点は、スーパーセットの範囲を手前に減らすことができることです。たとえば、画像の右側のブロックを参照してください。この場合の合計は24であり、Kは3である。この領域内の任意のブロックを選択し、他のすべてのブロックが可能な限り最大値であると仮定すると、任意のブロックが（24- 9 + 8））= 7となる。 （24-（1 + 2））= 21を計算することによって最大値を得ることもできますが、これは21> 9なので問題はありません。従って、スーパーセットは{7,8,9}になる。

この領域は、K =スーパーセットサイズのため、簡単なケースです。ただし、Kがスーパーセットサイズよりもはるかに小さい場合は、すべての組み合わせをチェックすると（SuperSize-K）が計算されます。時間。これは非効率的です。今私の質問は、このケースに最も適しているサブセットの合計問題の解決策がありますか？私はJavaでコードを作成しますが、SPLやBrainF * ckを含むプログラミング言語は大歓迎です。

Answer 1

2から = 1から9の整数のセットの512個のサブセットがあります（実際には、サイズ0と1のセットが決して発生しないので、これらの502個だけが興味深いです）。これらをあらかじめ計算するのはかなり簡単です合計（3と45の間の値を含む）とサイズで整理します。次に、ターゲットセットを取得するだけの簡単な検索です。

標準9整数かくれの場合、setsize/sumの組み合わせには12以上の解決策がありません。 12個の解を持つ2つの組み合わせは、k = 5/sum = 25であり、k = 4/sum = 20である。 （この二重性は偶然ではなく、その結果、あらかじめ計算されたセットの半分を保存することで逃げることができます）n - この場合は9--の場合、kの合計はsになりますn-kの数値はすべてのサブセットの補数を単純に取ることによってn*(n+1)/2 - sに加算されます）。nが増加すると、サブセットの最大数が指数関数的に増加します。私はこれのpython3「ワンライナー」を使用して、30までの最大値を計算する：

for j in range(9,31): 
    print(j, Counter((len(k),sum(k)) 
        for k in combinations(range(1,j+1), j//2) 
       ).most_common(1)) 

最後の二つの値を計算するのに数秒を要したので、これは間違いの可能性を列挙するための最も効率的な戦略ではありません。私は可読性のために出力を少しきれいにしました。

N  k  sum  count 
--  --  ---  ----- 
9  4  20   12 
10  5  28   20 
11  5  31   32 
12  6  39   58 
13  6  42   94 
14  7  52   169 
15  7  56   289 
16  8  68   526 
17  8  72   910 
18  9  86  1667 
19  9  90  2934 
20  10  105  5448 
21  10  110  9686 
22  11  126  18084 
23  11  132  32540 
24  12  150  61108 
25  12  156  110780 
26  13  175  208960 
27  13  182  381676 
28  14  203  723354 
29  14  210  1328980 
30  15  233  2527074 

非常に多くの可能性があるため、完璧な解決策をもってカクロを生成するのがはるかに難しいようです。もちろん、可能なk/sumの組み合わせのほとんどを避けることができますが、パズルそのものにスケーラビリティが組み込まれているように見えます。

（注：これは、整数列のオンライン百科事典でSequence A277218であり、それはMagic Carpetsに関係していますSequence A055606、に関連している。）

Answer 2

私はサブセットの合計を無視し、代わりにこれを処理することを示唆しています制約充足問題として。そして、私の最初のパスは、次の推測が最小の可能性のある正方形に対して行われるという最適化を伴うバックトラッキングアルゴリズムです。

これはNP困難な問題であることに注意してください。 いいえ解決策はうまくスケールされます。