テトロミノ敷き詰めパズルを量子コンピュータ（シミュレータ）で解いてみる

#はじめに
テトロミノ敷き詰め問題を量子コンピュータ（シミュレータ）で解いてみます。前回３つの正方形でできたピースの問題を解いてみましたが、今回は４つです。ちなみに、３つのはトロミノと言うそうです。
「ペントミノ「のような」タイル敷き詰め問題を量子コンピュータで解いてみる」
https://qiita.com/drafts/5ddb63f74193babf9b7e/edit

#問題
テトロミノとは、４つの正方形を組み合わせた形状のことで、下図の５つのピースがあります。テトリスと同じです。ピースは、回転したり、裏返したりすることができます。
![p1.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/df715555-8891-12a0-5ec7-b18308225442.png)
このピース２つずつを、下図のようにボートに敷き詰めていきます。
![p3.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/440dd328-3955-d7ad-0bab-f49af0016687.png)

#考え方

3つの時と同じように、まずは、ピースp0の盤面への置き方を考えてみます。下図のように41通りあるようです。この置き方を、それぞれ「q0, q1, q2, q3, q4, q5・・・」とします。
![p4.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/f0967b71-7395-3ba6-68c9-dc2f2b66ad9c.png)
![p5.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/4666ddb1-030b-a962-4d19-a9ef88620a75.png)

他のピースについても置き方をすべて考えて、それぞれq41, q42・・・と割り当てます。ピースによっては下図のように回転・反転で８通りありますので、８通り×それぞれの置き方を考えます。
![p6.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/881f5911-aeaf-5002-5578-047c0e3ea2b4.png)

今回は３つ（トロミノ）の時と違って、人力ですべて書き出すことはできないので、この書き出しもPythonでやります。例えば、私はそれぞれのピースを以下のような行列で定義して、numpyの回転と反転と掛け算を使って作りました。

```
p = [[[1,1,1,1]],
      [[1,1],[1,1]],
      [[1,1,1],[1,0,0]],
      [[1,1,1],[0,1,0]],
      [[1,1,0],[0,1,1]]]
```

本当は、対称性や置いちゃダメな置き方（端が1つだけ空いてしまうなど）もあるのですが、とりあえず全部列挙してしまいます。すべてのピースのすべての置き方を列挙すると429個ありました。

#立式
立式も3つの時とほぼ同じです。イジングモデルやQAOAで解けるように立式してみます。

##量子ビットが表すものを決める
ピースp0は、q0～q40のどれかの置き方になるはずですので、置き方q0になるときに、q0=1 、q0にならない時 q0=0 とします。同様にして、q1になるとき、q1=1, ならないときq1=0・・・、ピースp1についても、置き方q41になるときq41=1, ならないときq41=0・・・とします。

##各ピースについて、置き方の中から２つだけ選ばれるようにする・・・①
まずは、p0の置き方は「q0, q1, q2, ・・・, q40」の41個がありますが、その中から同じ形のピース２つ分が選ばれるようにします。
41個の量子ビットの中から２つだけが選ばれる、という条件を最小値問題の式にしてみます。以下のようになります。

```math
\{2-(q0+q2+q3....+q40)\}^2
```

これで、q0～q41の中で、２個だけ１のとき最小値の０、それ以外は１以上の値になります。
同様にして、ピースp1, p2・・・についても立式していきます。

## 盤面の各位置（1, 2, 3・・・）に置くピースが重ならないようにする・・・②
次に、盤面に注目します。
盤面の「1」の位置に置かれる可能性のあるピースは１つだけ選ばれるようにします。ピースは重なってもだめだし、どれか１つは配置されていないとダメなので、盤面の「1」上に来る可能性のあるピースの中から、１つだけを選ぶ必要があります。先ほどと同様に立式すると、

```math
\{1-(q0+q25+q41+q69+...)\}^2
```
とすれば、盤面の位置1に置かれるピースの配置が１つのみに絞られます。q0, q25はピースp0の置き方の中に含まれています。q41, q69・・・はp1, p2・・・の置き方です。
盤面の他の位置2, 3, 4, 5・・・についても同様に立式します。

# QUBO作成
イジングモデルやQAOAで解けるようにQUBOの形にします。
式が長くて展開に時間がかかるので、今回はQUBOに直接値を入れて作成しました。条件①のQUBOは以下のような感じです。

```
[[-3.  2.  2. ...  0.  0.  0.]
 [ 0. -3.  2. ...  0.  0.  0.]
 [ 0.  0. -3. ...  0.  0.  0.]
 ...
 [ 0.  0.  0. ... -3.  2.  2.]
 [ 0.  0.  0. ...  0. -3.  2.]
 [ 0.  0.  0. ...  0.  0. -3.]]
```

条件②の方のQUBOは以下のような感じです。

```
[[-4.  6.  4. ...  0.  0.  0.]
 [ 0. -4.  6. ...  0.  0.  0.]
 [ 0.  0. -4. ...  0.  0.  0.]
 ...
 [ 0.  0.  0. ... -4.  2.  0.]
 [ 0.  0.  0. ...  0. -4.  2.]
 [ 0.  0.  0. ...  0.  0. -4.]]
```

さらに、条件①と条件②のバランスを考えて足し合わせたものを、QUBOにします。量子ビット数は、配置の総数と同じで429個ですので、QUBOマトリクスのサイズは429×429でした。

# シミュレータで解いてみる
今回はオープンソースのシミュレータblueqatと、D-waveのqbsolvで解いてみました。
３個のタイルの時と違って、一発では良い解が得られないので、何回もループして良い解を探します。
良い解では、例として以下のような結果が得られました！
[13, 33, 66, 68, 144, 223, 251, 298, 339, 352]
![p7.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/defb1407-0c90-4951-4b1a-d85880a629ec.png)

いくつか解はあるようです。
![p8.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/a46f3dd5-6328-c4bd-7167-97d851a71803.png)

下図のような外れの解も結構でてきます。赤い部分は重なってしまったところです。
![p9.PNG](https://qiita-image-store.s3.amazonaws.com/0/298382/3c313dbc-19a5-a1f4-12f2-ac4e03739a37.png)

# まとめ
テトロミノは何とか解けました。次はペントミノ（５つの正方形）に挑戦してみたいと思います！

実はペントミノもコードは書いてみたのですが、量子ビット数が多くて、工夫しないと解けないようです。解は得られますが、３か所位重なってしまう解がほとんどで、最良でも1か所間違いまでしか得られていません。対称性や、ダメな置き方を省いたりして量子ビット削減しても1870になってしまい、難しいです。他の方法を含め、考えてみます！