ペントミノをExact cover問題として解く（その１）

有名なパズルの[ペントミノ (Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%B3%E3%83%88%E3%83%9F%E3%83%8E)を解くコードを紹介します。なるべく分かりやすく、以下のステップでコードを作っていきます。

1. ペントミノのピースのデータ構造
1. ボードのデータ構造
1. まず回転・鏡映はしないで10x6の長方形を作るコードを総当りで作る
1. [Exact cover (Wikipedia)](https://en.wikipedia.org/wiki/Exact_cover#Pentomino_tiling)の考え方
1. Exact cover問題を解く[dancing links](https://en.wikipedia.org/wiki/Dancing_Links)のpackage、[PyPIのDLX](https://pypi.org/project/dlx/)の説明
1. 回転・鏡映をしたピースのデータを作る
1. ペントミノをExact Cover問題として考える
1. DLXを用いて回転・鏡映ありで10x6の長方形を解く

### 1. ペントミノのピースのデータ構造

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/a0846f55-e61e-4c86-944a-f2cd9bae7c6a.png)

このペントミノの12個のピースを構成する5個の正方形のセルの相対座標を$(x,y)$のリストで定義します。どこを原点にするかで変わってきますがそれは気にしなくても大丈夫です。まずは回転等しなくても答えが出るように上の図形と同じ向きしました。

```python
pentomino = [
    [(2,0),(0,1),(1,1),(2,1),(1,2)], # F/0
    [(0,0),(0,1),(0,2),(0,3),(0,4)], # I/1
    [(0,1),(1,1),(2,1),(3,1),(3,0)], # L/2
    [(1,0),(2,0),(3,0),(0,1),(1,1)], # N/3
    [(0,0),(0,1),(0,2),(1,1),(1,2)], # P/4
    [(0,0),(1,0),(2,0),(1,1),(1,2)], # T/5
    [(0,0),(1,0),(1,1),(0,2),(1,2)], # U/6
    [(2,0),(2,1),(0,2),(1,2),(2,2)], # V/7
    [(1,0),(2,0),(0,1),(1,1),(0,2)], # W/8
    [(1,0),(0,1),(1,1),(2,1),(1,2)], # X/9
    [(1,0),(0,1),(1,1),(2,1),(3,1)], # Y10
    [(1,0),(2,0),(1,1),(0,2),(1,2)]] # Z/11
```
### 2. ボードのデータ構造

10x6の長方形を(x,y)の1次元リストで表します。
```python
X, Y = 10, 6
board = [(x,y) for y in range(Y) for x in range(X)]
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/b63ecc93-4d70-4605-9118-b05bb399ccea.png)

### 3. 回転・鏡映はしないで10x6の長方形を作るコードを総当りで作る
この準備として以下の2点を行います。
#### ピース上の最初のセルを原点に変換する

これによってピースの原点をボードの空きセルに合わせれば移動したピースの位置の候補が列挙できるようになります。

```python 
def addxy(xy1, xy2, s=1):
  (x1, y1), (x2, y2)  = xy1, xy2
  return (x1+s*x2, y1+s*y2)
# Normalize (no rotate/reflect)
pieces = []
for pn, pc in enumerate(pentomino):
  pc1 = [(pn,0), [addxy(c,pc[0],-1) for c in pc]]
  print(pc1)
  pieces += [pc1]
#  [(0, 0), [(0, 0), (-2, 1), (-1, 1), (0, 1), (-1, 2)]]
#  [(1, 0), [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)]]
#  [(2, 0), [(0, 0), (1, 0), (2, 0), (3, 0), (3, -1)]]
#  [(3, 0), [(0, 0), (1, 0), (2, 0), (-1, 1), (0, 1)]]
#  [(4, 0), [(0, 0), (0, 1), (0, 2), (1, 1), (1, 2)]]
#  [(5, 0), [(0, 0), (1, 0), (2, 0), (1, 1), (1, 2)]]
#  [(6, 0), [(0, 0), (1, 0), (1, 1), (0, 2), (1, 2)]]
#  [(7, 0), [(0, 0), (0, 1), (-2, 2), (-1, 2), (0, 2)]]
#  [(8, 0), [(0, 0), (1, 0), (-1, 1), (0, 1), (-1, 2)]]
#  [(9, 0), [(0, 0), (-1, 1), (0, 1), (1, 1), (0, 2)]]
#  [(10, 0), [(0, 0), (-1, 1), (0, 1), (1, 1), (2, 1)]]
#  [(11, 0), [(0, 0), (1, 0), (0, 1), (-1, 2), (0, 2)]] 
```
#### ボードの空きエリアをsetで表す

こうすることによってピースが空きエリアに収まるかどうかを簡単に表現できます。

```python 
freearea = set(board)
```
### 総当たりのコード
stackには(ピース番号、置いた座標のリスト、空きエリア)が入ります。次のピース入るかをチェックして入れば、その分空きエリアを狭めて行き、空きエリアが０になればゴールです。

```python
stack = [(0, [], freearea)] # piece number, position list, free area
while stack:
  pn, st, freearea = stack.pop()
  if len(freearea) == 0: break  # Answer found
  for fcell in freearea:
    cells = {addxy(fcell,p) for p in pieces[pn][1]} # move pieces all over the free area
    if cells <= freearea:                           # if cells fits in free area
      stack += [(pn+1, st+[fcell], freearea - cells)] # decrease free area

print("***** Goal : ", st, freearea)
# ***** Goal :  [(6, 1), (0, 1), (5, 4), (5, 0), (1, 3), (0, 0), (8, 0), (9, 3), (3, 0), (3, 2), (4, 4), (7, 1)] set()

```
このコードでピースが入るかどうかの判定はこの1行で書けることに注目して下さい。
```python 
if cells <= free: # if cells fits in free area
```
出た答えはピース０の原点が$(6,1)$, ピース1の原点が$(0,1)$, ...となることを示しています。この回答を図示して最初の図形と一致しているのを確認しました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1922159/f7c6f462-20f3-4c85-bd16-4358255b0e85.png)

ただこの全探索だと回転・鏡映なしでも約４分かかるので、画期的な高速化が必要をなります。そのためにこの問題をExact cover問題に置き換えて考える方法を[次回のその２](https://qiita.com/masa0599/items/0f1078305cf6a2fc32f8)で説明したいと思います。

（開発環境：Google Colab）