https://www.topcoder.com/challenges/30081256
$9\times9$の数独が与えられるので、デジタルアニーラを利用して解け。
この問題はデジタルアニーラのLarning Challengeですので、解法の概要およびコードはTutorialに記載されています(コンテスト期間中は、build_row_ruleの実装だけは公開されていませんでした。)。この記事では、Tutorialの内容について行間を埋める形で解説することを目指します。
デジタルアニーラはQUBO(Quadratic Unconstrained Binary Optimization)と呼ばれる形式の問題を解くことに特化したハードウェアであり、最適化問題を解くためには問題を定式化してQUBOへと変換するステップが必要になります。
QUBOとは、$X_i\in \{0,1\}$であるような$N$個の変数$\{X_1, X_2, ..., X_N\}$について、二次多項式(quadratic polynomial) $$E(X_1, X_2, ..., X_N)=\sum_{i=1}^N c_iX_i+\sum_{i=1}^{N-1}\sum_{j=1}^{i} Q_{ij}X_iX_j$$ の値を最小化する問題のことをいいます。
ここで、値を最小化することで数独の解となるようなquadratic polynomialを構成することができればデジタルアニーラで数独を解くことができます。
QUBOでは各変数$X_i$は0もしくは1の値しか取ることができないため、数独をそのままの形($9\times9$個の1~9の数字)で扱うことはできません。そこで、盤面を$9\times9\times9$の3次元bool配列$X$として読み替えることで、数独をQUBOに落とし込むことができます。ここで、$X_{ijk}=1$であることは、盤面の$i$行目$j$列目に数字$k$が入っていることを意味します。
数独の制約としては、以下の5つが挙げられます。
マス$(i,j)$に$n$個の数字が入っている状態は、$\{X_{ij1}, X_{ij2}, ...,X_{ij9}\}$のなかに1であるようなものが$n$個ある状態を指します。よって、すべてのマスに数字が1つだけ入っている状態は $$\sum_{k=1}^9 X_{ijk}=1,\;\forall_{ij}\in cell$$ と表せます。
この制約と制約1をあわせると、「任意の列$j$と数字$k$の組み合わせについて、$j$列目に$k$が入っているような行$i$が1つだけ存在する」と言い換えることができて、このことは $$s.t.\;\sum_i X_{ijk}=1,\;\forall j\in column,\;\forall k\in K(K=\{1..9\})$$ と表せます。
この制約と制約1をあわせると、「任意の行$i$と数字$k$の組み合わせについて、$i$行目に$k$が入っているような列$j$が1つだけ存在する」と言い換えることができて、このことは $$s.t.\;\sum_j X_{ijk}=1,\;\forall i\in row,\;\forall k\in K(K=\{1..9\})$$ と表せます。
この制約と制約1をあわせると、「任意のサブグリッドについて、数字$k$が入っているようなマス$(i,j)$が1つだけ存在する」と言い換えることができて、このことは $$s.t.\;\sum_j^2\sum_i^2 X_{(i+u)(j+v)k}=1,\;\forall\in K(K=\{1..9\})\;u,v\in\{0,3,6\}$$ と表せます。
数独でははじめから与えられている数字が存在して、そこは変更できません。 $$s.t.\;\sum_{hint}X_{ijk}=1$$
数独をデジタルアニーラで解くために、以上の5つの制約をQUBOに変換します。今回の場合、それぞれの制約について、満たされている場合に値が0になるような関数を作り、それらをすべて足し合わせたものが解きたいQUBOになります。
以下では、Tutorialに記載されているソースコードに対応した形(二次多項式の一次の項を持たず、二次の項と定数項のみの形)への式変形まで行ってみました。
制約1が満たされている場合に値が0となる関数として \begin{align*} \alpha\sum_{ij}\left( \sum_{k=1}^9 X_{ijk}-1 \right)^2 &=\alpha\sum_{ij}\left( \sum_{k_1}\sum_{k_2} X_{ijk_1}X_{ijk_2} -2\sum_k X_{ijk} +1 \right) \\ &=\alpha\sum_{ij}\left( \sum_{k_1}\sum_{k_2} X_{ijk_1}X_{ijk_2} -2\sum_k X_{ijk}^2 +1 \right) \end{align*} が作れます。式変形について、$X_{ijk}\in\{0,1\}$より$X_{ijk}^2=X_{ijk}$であることに注意してください。
制約2が満たされている場合に値が0となる関数として \begin{align*} \alpha\sum_{k=1}^9\sum_{j}\left( \sum_{i} X_{ijk}-1 \right)^2 &=\alpha\sum_{k=1}^9\sum_{j}\left( \sum_{i_1}\sum_{i_2} X_{ijk_1}X_{ijk_2} -2\sum_i X_{ijk} +1 \right) \\ &=\alpha\sum_{k=1}^9\sum_{j}\left( \sum_{i_1}\sum_{i_2} X_{ijk_1}X_{ijk_2} -2\sum_i X_{ijk}^2 +1 \right) \end{align*} が作れます。
制約3が満たされている場合に値が0となる関数として \begin{align*} \alpha\sum_{k=1}^9\sum_{i}\left( \sum_{j} X_{ijk}-1 \right)^2 &=\alpha\sum_{k=1}^9\sum_{i}\left( \sum_{j_1}\sum_{j_2} X_{ijk_1}X_{ijk_2} -2\sum_j X_{ijk} +1 \right) \\ &=\alpha\sum_{k=1}^9\sum_{j}\left( \sum_{j_1}\sum_{j_2} X_{ijk_1}X_{ijk_2} -2\sum_j X_{ijk}^2 +1 \right) \end{align*} が作れます。
制約4が満たされている場合に値が0となる関数として、各$u,v$について \begin{align*} \alpha \sum_{k=1}^9 \left( \sum_j^2\sum_i^2 X_{(i+u)(j+v)k}-1 \right)^2 &=\alpha \sum_{k=1}^9 \left( \sum_{j_1}^2\sum_{i_1}^2 \sum_{j_2}^2\sum_{i_2}^2 X_{(i_1+u)(j_1+v)k} X_{(i_2+u)(j_2+v)k} -2\sum_{j}^2\sum_{i}^2 X_{(i+u)(j+v)k} -1 \right)\\ &=\alpha \sum_{k=1}^9 \left( \sum_{j_1}^2\sum_{i_1}^2 \sum_{j_2}^2\sum_{i_2}^2 X_{(i_1+u)(j_1+v)k} X_{(i_2+u)(j_2+v)k} -2\sum_{j}^2\sum_{i}^2 X_{(i+u)(j+v)k}^2 -1 \right) \end{align*} が作れます。ここで $u,v\in \{0,3,6\}$ であって、和を取ると $$\alpha \sum_u\sum_v \sum_{k=1}^9 \left( \sum_{j_1}^2\sum_{i_1}^2 \sum_{j_2}^2\sum_{i_2}^2 X_{(i_1+u)(j_1+v)k} X_{(i_2+u)(j_2+v)k} -2\sum_{j}^2\sum_{i}^2 X_{(i+u)(j+v)k}^2 -1 \right)$$ となります。
制約5が満たされている場合に値が0となる関数として \begin{align*} 2\alpha\sum_{hint} \left( 1-X_{ijk} \right)&=2\alpha\sum_{hint} \left( 1-X_{ijk}^2 \right) \end{align*} が作れます。(他の制約よりも強い制約なので重みをつけるために2をかけていると思っているんですが、どうなんですかね)
以上で、数独のルールをすべてQUBOに変換することができました。よって、これらをすべて足し合わせた関数 $$H=\alpha\sum_{ij}\left( \sum_{k_1}\sum_{k_2} X_{ijk_1}X_{ijk_2} -2\sum_k X_{ijk}^2 +1 \right)+\alpha\sum_{k=1}^9\sum_{j}\left( \sum_{i_1}\sum_{i_2} X_{ijk_1}X_{ijk_2} -2\sum_i X_{ijk}^2 +1 \right)+\alpha\sum_{k=1}^9\sum_{j}\left( \sum_{j_1}\sum_{j_2} X_{ijk_1}X_{ijk_2} -2\sum_j X_{ijk}^2 +1 \right)+\alpha \sum_u\sum_v \sum_{k=1}^9 \left( \sum_{j_1}^2\sum_{i_1}^2 \sum_{j_2}^2\sum_{i_2}^2 X_{(i_1+u)(j_1+v)k} X_{(i_2+u)(j_2+v)k} -2\sum_{j}^2\sum_{i}^2 X_{(i+u)(j+v)k}^2 -1 \right)+2\alpha\sum_{hint} \left( 1-X_{ijk}^2 \right)$$ が0になるような$X_{ijk}$を見つけることで、数独を解くことができます。これで、数独をデジタルアニーラで解ける形に変換することができました。
Tutorialに載っているので、割愛。