ペントミノ・ソルバーのアルゴリズム


# はじめに
この記事

https://qiita.com/sense_n_react/items/0875e969626c1892b60a

で紹介したプログラムのアルゴリズムを説明します。
個人的にはいろんな言語の中で *Ruby* が一番シンプルだと感じていてるので、*Ruby* 版のソルバー（[solver.rb](https://github.com/sense-n-react/PentominoSolvers/blob/main/solver.rb)）を例示しながらアルゴリズムを説明して行きます。

# 戦略
0. 全ての可能性を試す
**全てのピース**の**全ての姿勢**の組合せを再帰呼び出しによるバックトラッキングで試して行きます。

0. 左上から敷き詰める
左上を起点として、右方向に空きエリアを探します。空きがなければ１列下の左端から右端に向かって空きを探します。空きが見つかればそこに配置します。

0. 対称性の排除
6x10 のペントミノは2,339通りの解がありますが、盤面を左右反転や上下反転した場合の解を考慮せずに探索すると4倍の 9,356 通りが見つかります。
そこで、対称な解を排除するために '*F*' の配置を制限します。

0. 最適化
コードの簡潔さを優先し、最適化は行いません。
最適化の例は別の投稿で示します。


# 座標の定義

 - 盤面の座標
Ｘ軸、Ｙ軸をそれぞれ水平方向、垂直方向とします。6x10 の場合、左上が(0,0)、右下が(5,9)です。
```text:盤面の座標
     0   1   2   3   4   5 　　X
   +---+---+---+---+---+---+   
0  |0,0|   |   |   |   |   |   
   +---+---+---+---+---+---+
1  |   |   |   |   |   |   |   
   +---+---+---+---+---+---+
2  |   |   |   |   |   |   |   
   ～　～　～　～　～　～　～
   ～　～　～　～　～　～　～
8  |   |   |   |   |   |   |   
   +---+---+---+---+---+---+   
9  |   |   |   |   |   |5,9|   
   +---+---+---+---+---+---+   
Y
```
---
- ピースの座標

ピースの形状と向きにを一意な **座標列**（５つの座標 (*x,y*) の配列）として定義します。
座標の取り方はピースの最も左上を (0,0) とします。なのでＹ座標は必ず 0 以上ですがＸ座標は負値になる場合があります。下図の例では左側ピースの座標列は[(0,0),(1,0),(-1,1),(0,1),(0,2)] 、右側は[(0,0),(0,1),(1,1),(2,1),(1,2)]と定義します。
```text:ピースの座標

     -1   0   1      X                    0   1   2     X
        +---+---+                       +---+    
0       |0,0    |                  0    |0,0|    
    +---+   +---+                       +   +---+---+
1   |       |                      1    |           |
    +---+   +                           +---+   +---+
2       |   |                      2        |   |
        +---+                               +---+
Y                                  Y

[(0,0),(1,0),(-1,1),(0,1),(0,2)]   [(0,0),(0,1),(1,1),(2,1),(1,2)]

````

# ピース：*Piece*

ピースは12種類ありその形状から *F I L N P T U V W X Y Z* という *ID* を持ちます。
各ピースは 0度／90度／180度／270度回転、表裏反転の組み合わせで最大８通りの座標列が定義できます。ピースの対称性により '*T*'、'*U*'、'*V*'、’*W*'、'*Z*' は４通り、'*I*' は２通りの座標列が定義できます。 '*X*' は１通りしかありません。

### 座標列のデータ
例えば、*'F'* の８通りの座標列は、以下のような配列で定義できます。
```ruby
  [ [[0, 0], [1, 0], [-1, 1], [0, 1], [0, 2]],
    [[0, 0], [-1, 1], [0, 1], [1, 1], [1, 2]],
    [[0, 0], [0, 1], [1, 1], [-1, 2], [0, 2]],
    [[0, 0], [0, 1], [1, 1], [2, 1], [1, 2]],
    [[0, 0], [1, 0], [1, 1], [2, 1], [1, 2]],
    [[0, 0], [-1, 1], [0, 1], [1, 1], [-1, 2]],
    [[0, 0], [-1, 1], [0, 1], [0, 2], [1, 2]],
    [[0, 0], [-2, 1], [-1, 1], [0, 1], [-1, 2]]
  ]
```
残りのピースについても丁寧に定義していけば良いのですが面倒です。実際のプログラムではもう少しスマートに**ピースの絵の文字列**から座標列を計算しています。
基になるデータは以下の ***PIECE_DEF*** です。
```ruby
PIECE_DEF = %Q(
+-------+-------+-------+-------+-------+-------+
|       |   I   |  L    |  N    |       |       |
|   F F |   I   |  L    |  N    |  P P  | T T T |
| F F   |   I   |  L    |  N N  |  P P  |   T   |
|   F   |   I   |  L L  |    N  |  P    |   T   |
|       |   I   |       |       |       |       |
+-------+-------+-------+-------+-------+-------+
|       | V     | W     |   X   |    Y  | Z Z   |
| U   U | V     | W W   | X X X |  Y Y  |   Z   |
| U U U | V V V |   W W |   X   |    Y  |   Z Z |
|       |       |       |       |    Y  |       |
+-------+-------+-------+-------+-------+-------+
).split("\n").each_with_index.map do |l, y|
  l.split('').each_with_index.map { |c, x| [ c, x, y ] }
end.flatten(1).each_with_object( Hash.new([]) ) do |cxy, h|
  h[ cxy[0] ] += [ [ cxy[1] / 2, cxy[2] ] ]
end
```
やっていることは、文字ごとに位置（列と行）を集めて *Hash* にしているだけです。文字の間に空白を入れてるので、Ｘ座標は横方向の位置を 1/2 する必要があります。結果として以下のような *Hash* が得られます。
```ruby
  PIECE_DEF = {
    "F" => [[2, 3], [3, 3], [1, 4], [2, 4], [2, 5]],
    "I" => [[6, 2], [6, 3], [6, 4], [6, 5], [6, 6]],
```
*`+`*、*`-`*、*`|`* 等の文字に対しても座標列を作ってしまいますが、使わないので良しとします。

### *initialize*: 回転、反転、正規化

ひとつの座標列を基にして、それを回転、反転、正規化することで８通りの座標列を作ります。対称性のあるピースの場合は重複した座標列ができるのでそれを排除します。
```ruby
class Piece
  def initialize( id, fig_def, next_pc )
    @figs = Array.new(8) do |r_f|          # rotation and flip
      fig = fig_def.map do |x,y|
        ( r_f % 4 ).times{ x, y = -y, x }  # rotate
        ( r_f < 4 )? [x, y] : [-x, y]      # flip
      end.sort_by do |x,y|                 # sort
        [y, x]
      end
      fig.map do |x,y|                     # normalize
        [ x - fig[0][0], y - fig[0][1] ]
      end
    end.uniq                               # uniq
```
*`fig_def`* を基にして *`@figs`* を作ります。 *`@figs`* は座標列の配列です。各ピースは固有の *`@figs`* を持つことになります。
回転・反転の組み合わせは８通りあるので８回ループを回します。
90度の回転は *`x, y = -y ,x`* で計算できるので、180度や270度はこれを２回、３回繰り返します。反転は *`x, y = -x, y`* です。反転するのはループ後半の４回です。
座標列を一意に決めるために、まず座標列をソートします。Ｙ座標を優先してソートしたいので *x, y* を逆にしたものをキーにしてソートしてます。
```ruby
   .sort_by do |x,y|                 # sort
     [y, x]
   end
```
次にピースの座標列の先頭を (0,0) にするために、全ての座標から先頭の座標値を引き算します。

```ruby
   fig.map do |x,y|                     # normalize
     [ x - fig[0][0], y - fig[0][1] ]
   end
```
これで正規化が完了し一意な座標列が得られました。

最後にピースの対称性により重複している座標列を排除するために *uniq* しています。*Ruby* の *uniq* は配列の要素で比較してくれるのですが、言語によっては比較関数を作る必要があります。

# 盤面：*Board*

盤面を表すデータは 6x10 や 12x5 の配列で、サイズは60です。配列の要素は言語によって文字列だったり文字コードだったりします。
```ruby
class Board
  def initialize( w, h )
    @width  = w
    @height = h
    @cells  = Array.new( @height ) { Array.new( @width ) { :SPACE } }
    if w * h == 64               # 8x8 or 4x16
      @cells[h/2 - 1][w/2 - 1] = '@'; @cells[h/2 - 1][w/2 - 0] = '@'
      @cells[h/2 - 0][w/2 - 1] = '@'; @cells[h/2 - 0][w/2 - 0] = '@'
    end
  end
```
初期値として空白（を表す定数）を入れておき、ピースを配置する際には対応する要素にそのピースの*ID*（'*X*' や '*F*'）を入れます。
8x8 や 4x16 も設定可能で、その場合は盤面の中央に 2x2 の穴を空けてピースを配置できないようにしています。

### 表示：*render*

盤面を１行ずつスキャンしながら上下左右のピース同士の**境界**をチェックして、盤面全体の文字列を作成します。
```ruby
  #         2
  # (-1,-1) | (0,-1)
  #   ---4--+--1----
  # (-1, 0) | (0, 0)
  #         8
  ELEMS = [
    # 0      3     5    6    7     9    10   11   12   13   14   15
    "    ,,,+---,,----,+   ,+---,,+---,|   ,+---,+   ,+---,+   ,+---",
    "    ,,,    ,,    ,    ,    ,,|   ,|   ,|   ,|   ,|   ,|   ,|   "
  ].map { |s| s.split(',') }.transpose

  def render()
    Array.new( @height + 1 ) do |y|
      Array.new( @width + 1 ) do |x|
        ELEMS[ ( ( at( x+0, y+0 ) != at( x+0, y-1 ) )? 1: 0 ) |
               ( ( at( x+0, y-1 ) != at( x-1, y-1 ) )? 2: 0 ) |
               ( ( at( x-1, y-1 ) != at( x-1, y+0 ) )? 4: 0 ) |
               ( ( at( x-1, y+0 ) != at( x+0, y+0 ) )? 8: 0 ) ]
      end.transpose.map(&:join)
    end.flatten.join( "\n" )
  end
```
ピース同士の接し方を12パターンに分けて、境界線の線素（*ELEMS*）を選びます。線素は *`+`* *`-`* *`|`* といった文字を組み合わせた文字列です。*`transpose`* を使うことでシンプルなコードになっています。


### 配置可能の確認：*check* ####
盤面上の *(ox, oy)* という位置に *fig* という座標列が配置可能か調べます。
```ruby
  def check?( ox, oy, fig )
    fig.all? { |x,y| at( x + ox, y + oy ) == :SPACE }
  end

  def at( x, y )
    ( x >= 0 && x < @width  && y >= 0 && y < @height )? @cells[y][x] : '?'
  end
```
盤面からはみ出す可能性があるので、配列にアクセスする前にチェックしています。対応する座標の要素が全て空白ならそこに配置可能と判定します。

#### 配置：*place* ####
盤面にピースの *id*（'*F*' とか ’*L*'）を書き込みます。事前に*check* しているので配列からはみ出す心配はありません。

```ruby
  def place( ox, oy, fig, id )
    fig.each { |x,y|  @cells[ y + oy ][ x + ox ] = id  }
  end
```
配置したピースを取り出すには *id* に 空白を設定して *place* します。

### 空白の探索：*find_space* ####
盤面をスキャンして空白を探します。

```ruby
  def find_space( x, y )
    while @cells[ y ][ x ] != :SPACE
      if ( x += 1 ) == @width
        x = 0
        y += 1
      end
    end
    return [ x, y ]
  end
```
*x, y* は直前に配置したピースの位置です（十字ピース *'X'* を配置した直後は(0,0) ）。Ｘ方向、Ｙ方向に配列を愚直にスキャンして空白が見つかったらその座標を返します。未配置のピースがある限り必ず空白が見つかるので、オーバーランのチェックはしていません。


# ソルバー：*Solver*

以下のようにして *Solver* を実行します。
```ruby
solver = Solver.new( width, height )
solver.solve( 0, 0 )
```
*`Solver.new`* で盤面やピースを生成して、*`solve(0,0)`* により盤面の左上(0,0)から12個のピース全ての組合せを試しながら敷き詰めていきます。


中身を順番に説明します。
### 初期処理: *initialize*

先に説明した *Board* と *Piece* を作ります。
```ruby
class Solver
  def initialize( w, h )
    @solutions = 0
    @board     = Board.new( w, h )

    pc = nil
    'FLINPTUVWXYZ'.reverse.each_char do |id|
      pc = Piece.new( id, PIECE_DEF[id], pc )
    end
    @Unused = Piece.new( '!', [], pc )      # dummy piece
    # limit the symmetry of 'F'
    pc.figs = pc.figs[ 0, (w == h)? 1 : 2 ]
  end
```
*Board* の作成は特に説明不要なので *Piece* について説明します。
***PIECE_DEF*** はピースの座標列を定義した *Hash* です。これを基にしてピース毎に最大８個の座標列を作ることは先に説明した通りです。

12個のピースは '*F*' を先頭として'*Z* 'までを単方向リストで繋がります。ピースを作りながら繋げるために'*Z*' から作って最後に'*F*' を作っています。そして *`@Unused`* をピース'*F*' に繋いでいます。
```mermaid
---
title: 未配置ピースの単方向リスト
---
flowchart LR;
    a["`@Unused`"]-->F;
    F-->L;
    L-->I;
    I-->N;
    N-->P;
    P-->T;
    T-->U;
    U-->V;
    V-->W;
    W-->X;
    X-->Y;
    Y-->Z;
    Z-->nil;
```
この *`@Unused`* からたどれるピースはまだ盤面に配置されていないピースで、初期状態では全てのピースが未配置です。
ループの回し方は、*`'ZYXWVUTPNILFX'.each_char`* としても全く問題ないです。ピースを作る順番がリストの並びと逆なので敢えて *`'XFLINPTUVWXYZ'.reverse.each_char`* としています。

### *`F`* の座標列を制限
８通りある *'F'* の座標列を１通りか２通りに制限することで、対称な解を排除します。6x10 や 5x12 のような長方形の場合は「反転と180度回転なし、90度回転あり」、8x8の正方形の場合は「反転も回転もなし」とします。
```ruby
    # limit the symmetry of 'F'
    pc.figs = pc.figs[ 0, (w == h)? 1 : 2 ]
```

### バックトラッキング ：*solve* 

解探索の中心部です。*`solve()`* は再帰的に呼び出されます。

```ruby
  def solve( x, y )
    if (prev = @Unused).next != nil
      x, y = @board.find_space( x, y )
      while ( pc = prev.next ) != nil
        prev.next = pc.next
        pc.figs.each do |fig|
          if @board.check?( x, y, fig )
            @board.place( x, y, fig, pc.id )
            solve( x, y )
            @board.place( x, y, fig, :SPACE )
          end
        end
        prev = (prev.next = pc)
      end
    else
```
まだピースが全て収まっていない場合、つまり未配置ピースがある場合、 *`if (prev = @Unused).next != nil`* は *`true`* なので *`if`* 文の中で単方向リストをたどって未配置のピースを順番に配置していきます。ピースは回転と反転の組み合わせで複数の座標列を持つので、*`pc.figs.each`* で順番に座標列を試しています。
単方向リストのたどり方を図で示しながら説明します。
下図の盤面では７つのピースが配置されていて、＊ の位置に次のピースを配置しようとしています。

```
+-----------+-----------+   
| V         | P         |   
|   +-------+       +---+   
|   | W     |       | N |   
|   +---+   +---+---+   |   
|   | X |       |       |   
+---+   +---+   |   +---+   
|           |   |   | L |   
+---+   +---+---+   |   |   
| Y |   | *     |   |   |   
|   +---+       +---+   |   
|       |           |   |   
|   +---+       +---+   |   
|   |           |       |   
|   |           +-------+   
|   |                   |   
+---+                   |   
|                       |   
|                       |   
|                       |   
+-----------------------+   
```
*'Y'* が配置された後のリストは以下の通りで、**この盤面において** このリストの順番にピースを選び配置を試みます。（「この盤面において」というのがポイントです）
```mermaid
---
title: 未配置ピース
---
graph LR;
    Unused["@Unused"]==>F;
    F==>I;
    I==>T;
    T==>U;
    U==>Z;
    Z==>nil 
```

'*F*' は試し終わったとして、その次の '*I*' を試すときのリストを以下に示します。

```mermaid
---
title: "(1) 'I' を配置しようとしている状態"
---
graph LR;
    Unused["@Unused"]==>F;
    F== "prev.next" ==>I;
    I== "pc.next" ==>T;
    T==>U;
    U==>Z;
    Z==>nil 
    prev -- ＝ --- F
    pc -- ＝ --- I
```
リストを操作するために、*`solve()`* の中で *`pc`* と *`prev`* というふたつのローカル変数を使います。 それぞれ配置対称のピースとひとつ手前のピースです。図では *`pc`* は '*I*' 、*`prev`* は '*F*' です。ピース自体は単方向リストで繋がっていますが、*`prev`* により双方向リストと同じようにノードを操作できます。*`prev`* はローカル変数なので**盤面毎に**存在します。（「盤面毎」というのがポイントです）
この状態で *`prev.next = pc.next`* とすると '*I*' がリストから外れて下図のようになります。
```mermaid
---
title: "(2) 'I' をリストから外す操作"
---
flowchart LR;
    Unused["@Unused"]==>F;
    F -. "✕" .- I;
    F== "prev.next = pc.next" ==>T;
    I== pc.next ==>T;
    T==>U;
    U==>Z;
    Z==>nil 
    prev -- ＝ --- F
    pc -- ＝ --- I
```
'*I*' を配置すると（盤面が更新され）リストはこの状態のまま再帰的に *`solve()`* が呼ばれ、その *`solve()`* の中で未配置ピースをたどる際には '*I*' はスキップされます。

リストを元の状態に戻すには *`prev.next = pc`* とします。

```mermaid
---
title: "(3) 'I' をリストに戻す操作"
---
flowchart LR;
    Unused["@Unused"]==>F;
    F -. "✕" .- T;
    F== "prev.next = pc" ==>I;
    I== pc.next ==>T;
    T==>U;
    U==>Z;
    Z==>nil 
    prev -- ＝ --- F
    pc -- ＝ --- I
```

さらに配置対称のピースを '*I*' から '*T*' に進めるため *`prev = pc`* とします。実際のコードではリストを元に戻す操作と合わせて while ループの最後で *`prev = (prev.next = pc)`* としています。
while ループの先頭に戻ると *`pc = prev.next`* が実行され、リストは下図のようになります。

```mermaid
---
title: "(4) 'T' を配置しようとしている状態"
---

graph LR;
    Unused["@Unused"]==>F;
    F==>I;
    I==>T;
    T==>U;
    U==>Z;
    Z==>nil 
    prev -- ＝ --- I
    pc -- ＝ --- T
```
(1) のチャートと比べると *`prev`* と *`pc`* がひとつ進んでいることが見て取れます。

### 解の表示
全てのピースが盤上に収まると未配置のピースはなくなり、 *`@Unused.next`* は *`nil`* です。以下の *`if`* 文は *`else`* が実行されます。
```ruby
  def solve( x, y )
    if (prev = @Unused).next != nil
    #  ・・・リスト操作と再帰呼び出し ・・・
    else
      @solutions += 1
      curs_up = (@solutions > 1)? ("\033[%dA" % [@board.height * 2 + 2]) : ""
      printf( "%s%s%d\n", curs_up, @board.render(), @solutions )
    end
```
ここで、解の数（*`@solutions`*）をカウントアップしてから、盤面の状態（*`@board.render()`*）と解の数を表示します。大量の解を表示すると画面が流れて見難いので、２回目以降はカーソルを盤面のトップに移動してから表示します。そのためのエスケープシーケンス文字列が *"\033[%dA"* で、%d には盤面の縦サイズに応じた行数が入ります。

# 参考

https://qiita.com/sense_n_react/items/0875e969626c1892b60a

https://qiita.com/gushwell/items/9742c5091b2d95725651

https://qiita.com/maskot1977/items/685c336b104a3ec12c2c

https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%B3%E3%83%88%E3%83%9F%E3%83%8E

https://en.wikipedia.org/wiki/Pentomino

https://www.codeproject.com/Articles/271634/Puzzle-Solver

https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X


* [pentomino-solver](https://github.com/mlepage/pentomino-solver)
* [明治ミルクチョコーレートパズルの解をすべて探す - ザリガニが見ていた...。](https://zariganitosh.hatenablog.jp/entry/20150112/pentomino_programming)
* [PENTOMINO](https://www.kobe-kosen.ac.jp/~maeda/)
* [ペントミノを解く](https://www.asahi-net.or.jp/~rn8t-nkmr/pentomino/)
* [脳ブロック](https://bb.tenyo.co.jp/products/index.html)