文字拾い謎solver

目的

こういう謎を解きたい

謎検練習謎(https://www.nazoken.com/exercise-n/question04/index.html)より引用

制約

要素のオーダーや定義

• 単語リストの大きさ : $${A\sim3e4}$$ or $${2e5}$$

• 単語の長さの見積もり$${L\leq15}$$

• 文字の数 : $${B=75\sim1e2}$$

• 問題に含まれるブロック数 $${N}$$ (例では4)

• 問題に含まれる数字の数 $${M}$$ (例では3)

方法1 : 数字に当てはめる文字全探査

$${O(B^M)}$$

一般の場合

$${N}$$個の単語すべてに該当する単語リストの単語が存在するかを判定。

$$
O(AB^M)
$$

数字に当てはまる文字を先に選別する場合

前計算$${O(A)}$$で文字を選別できる
数字$${i}$$に使用できる文字の種類数を$${B'_i}$$とし
$${B'=\max_{i}B'_i}$$とすると

$$
O(AB'^M)
$$

数字の組に対する解を持ち、併合する方法

追記予定

方法2 : ブロックに当てはめる単語全探査

$${O(A^N)}$$

単語に単語を当てはめる（一般）

各ブロックにどの単語を当てはめるかを全探査$${O(A^N)}$$し、
$${N}$$単語の任意の組に矛盾がないかを判定$${O(N^2)}$$

$$
O(A^N)
$$

単語に単語を当てはめる（全ての数字を含む枠がある場合）

全ての数字を含む枠を便宜上金枠と呼ぶことにする
金枠にどの単語を当てはめるかを全探査$${O(A)}$$し、
他の枠にどの単語を当てはめればよいかを考える$${O(NA)}$$

$$
O(A^2)
$$

コードサンプル