PentominoをBitboardを使って解く

子どもが百均で買ってきたパズルをやってみたら、全然うまく出来なくて悔しかったのでプログラムで解を探すことにした。

Pentominoとは
探索アルゴリズムと実装
反転・回転での重複の除外
高速化
その他の実装・手法
WebAssembly化してWebAppで使う
参考
まとめ

Pentominoとは

調べるまで知らなかったが、このような 5つの正方形を繋げて作られる12種類のピースを使って敷き詰める、というパズルを Pentomino(ペントミノ) というらしい。

en.wikipedia.org

最も一般的なものはこれらを1種類ずつ使って長方形に敷き詰めるもので、5マス x 12種類なので面積60のものが考えられる。回転や反転によって重複するものを同一視すると、それらの解の数は以下の通り、とのこと。

6x10 には 2,339通り
5x12 には 1,010通り
4x15 には 368通り
3x20 には 2通り

そして冒頭の写真のものは2x2の正方形ピースが使われていて、合計面積64なので 8x8 の正方形が作れる。一般的にはこの2x2の正方形は中央に固定され、周囲のドーナツ状の部分に12種類を敷き詰める問題、となる。このときの解は 65 通りになる、とのこと。

探索アルゴリズムと実装

ということで、この問題を解くプログラムをRustで書いてみた。

計算量概算

まず、どれくらいの計算量がかかるのかを概算してみる。

ピースは12種類だが、反転と 90°, 180°, 270°の回転を考えると、それぞれに対し8通りの置き方がある。

12種類のピースの中から未使用のものを順番に選び
  選んだものに対して8通りの反転/回転のどれかを選び
    可能であれば(既に置かれている他のピースとぶつからなければ)置く

12種類の選ぶ順番だけで $12! (= 479,001,600)$ 通りあり、置き方を考慮するとその8倍、そして置ける場所を探すのにも計算が必要で愚直にやると盤面の全探索になったりして、とにかくかなりの時間がかかる、というのは容易に想像できる。

効率的な探索の方針

無駄な計算を省くために、まずは「端っこから順番に埋めていく」という方針を考える。例えば最上段の左端から右端へ、次はその下の段の左端から右端へ、と。次に埋めるべきマスが決まっているので、現在選択しているピースではどうやってもそのマスを埋めることができない、となればその先の探索は必要なくなり枝刈りされる。

backtracking

こういう探索でよく使われるのがおそらくbacktrackingだろう。ざっくり以下のような感じ。

fn backtrack(board: &mut <盤面の状態>) {
    if すべてのマスが埋まっている(すなわち12種類のピースをすべて使いきっている) {
        答えを出力
        return;
    }
    for ピース in 全12種類のピース.filter(|ピース| 未使用) {
        for 反転/回転 in 全8通り {
            if 現在の盤面で最も上段・左端の空きマスを埋めるように置ける {
                boardに選択したピースを置いた状態にする
                backtrack(board);
                boardを1つ前の状態に戻す
            }
        }
    }
}

可能なものを順番に置いていき、置けなくなったら戻って次のものを置いていく、という処理を、盤面の状態を更新/復元しながら再帰的に探索していく。

あとはこれをどのようなデータ構造で実現するか、というところ。長方形の盤面なので Vec<Vec<Option<u8>>> のように2次元配列で表していっても良いが、埋めるべき左上の空きマスを探すときやピースを置けるか否かの判定などに毎回多くのループ処理が必要になってしまう。

Bitboardによる検索と判定

ここで登場するのがBitboard。将棋ライブラリを自作したときに学んだものが役に立つ。

u64 を使って64マスの盤面を表現する。0が空きマス、1が置けないマス、を表す。 8x8の中央に2x2の正方形が固定されていると考えると、初期盤面は以下のようになる。

この盤面のそれぞれのマスがu64の何bit目に対応するか、を割り当てていく。上段の左端から順に割り振っていくと、以下のようなレイアウトになる。

00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

なので前述の初期盤面は 103_481_868_288 (0x0000_0018_1800_0000) という値で表現される。

こうして表される盤面Bitboardに対し、例えばT型のピースを一番左上に置くとき、

のようなBitboardを作る。盤面とピースのそれぞれのBitboardとして表現されるu64同士をAND演算(&)すると、重なっている部分が1になるので、(board & piece) == 0 で盤面とピースが重なるマスが無いかどうか(すなわち空きマスだけにピースを置くことができるか否か)、を判定できる。また、その後に board | piece とOR演算(|)を適用することで、盤面にピースを置いた状態を得ることができる。

また、盤面の左上から順番に埋めていくという方針を考えると、前述のレイアウトにしておくことで、「最も上段・左端の空きマス」の位置を u64::trailing_ones() を使って一発で取得できる。これは x86_64ならbsf命令、aarch64ならclz命令を使って計算されるので非常に高速に動作する。

あとはすべてのピース、その反転/回転、それらを盤面内の可能な範囲で移動したものをすべてBitboardで表現できれば、探索が進められそうだ。

候補の事前計算

まずピースについて、もう少し深く考えてみる。前述したように12種類のピースにそれぞれ反転と4種類の回転があるので、全部で 12 * 2 * 4 = 96 通りありそうだが、実際には線対称・点対称な形もあるのでそこまで多くはならない。例えばT型のピースは線対称な図形なので反転を考慮する必要がなく4通りだけ。I型の細長いピースは縦か横の2通りだけだし、X型のピースにいたっては回転しても同じ形になるので1通りしかない。これらを考慮すると、実際には合計で63種類の形しか存在しないことが分かる。

で、これらをそれぞれ各方向に移動したものを考えていくが、この移動によって配置可能な位置の数はピースの横幅・縦幅に依存する。ちなみに前述のレイアウトにしておくことで、最も左上に配置したときのBitboardを基準として、1つ右に移動したものは piece << 1 で、1つ下に移動したものは piece << 8 で表現できる。ただしこれは8x8の左上から並べるレイアウトのときに限る話であり、例えば6x10の横長盤面で同様に左上から並べるレイアウトでは、1つ下に移動する操作は piece << 10 になる。

全63種類の形を盤面上の全位置に置く、のを列挙するのは大変ではあるが、探索時にはこれらを毎回すべて確認する必要はない。

上述の探索方針で次に置けるピースを探すとき、埋めるべきマスの位置は分かっていて、盤面でそのマスよりも左上(下位ビット)のものは既にすべて埋まっている、という前提になっている。ということは、次に置く試行をすべきピースは必ず「埋めるべきマスを含む」ことが分かっているし、さらに「そのマスより下位のビットを含まない」、つまりそのピースを表すBitboardでの最下位ビットが埋めるべきマスに一致する配置のものしか有り得ない、ということになる。

.O##.   ..O#.   ..O..
..#..   .##..   .###.
..#..   ..#..   ..#..

例えば上図のように.以外で表現される形のピースの場合、Oの位置が埋めるべきマスになっている必要があり、そうでないとピース内の他の箇所が既に埋まっているはずの盤面にぶつかってしまう。

この条件を考慮して「埋めるべきマスの位置」(00-63)のそれぞれに対して「そのマスを埋めることができるピースの候補」を引けるようにしておく。対象1箇所あたり高々63種類で、すべて事前に計算しておくことができる。

実装と実行結果

というわけで、ここまでを踏まえて以下のような実装。

use std::array;

const NUM_PIECES: usize = 12;

pub type Bitboard = u64;

pub struct SimpleSolver {
    table: [[Vec<Bitboard>; NUM_PIECES]; 64],
}

impl SimpleSolver {
    pub fn new(rows: usize, cols: usize) -> Self {
        assert!(rows * cols <= 64);
        let shapes = calculate_shapes();
        let mut table = array::from_fn(|_| array::from_fn(|_| Vec::new()));
        for (n, shape) in shapes.iter().enumerate() {
            for s in shape {
                if s.iter().any(|&(x, y)| x >= cols || y >= rows) {
                    continue;
                }
                let v = s.iter().map(|p| (1 << (p.0 + p.1 * cols))).sum::<u64>();
                let (w, h) = s
                    .iter()
                    .fold((0, 0), |(xmax, ymax), &(x, y)| (xmax.max(x), ymax.max(y)));
                for y in 0..rows - h {
                    for x in 0..cols - w {
                        let offset = x + y * cols;
                        table[s[0].0 + offset][n].push((v << offset).into());
                    }
                }
            }
        }
        Self { table }
    }
    fn backtrack(
        &self,
        current: Bitboard,
        solutions: &mut Vec<[Bitboard; NUM_PIECES]>,
        s: &mut [Bitboard; NUM_PIECES],
    ) {
        if !s.iter().any(|u| *u == 0) {
            return solutions.push(*s);
        }
        let target = current.trailing_ones() as usize;
        for i in 0..NUM_PIECES {
            if s[i] == 0 {
                for &b in self.table[target][i].iter() {
                    if (current & b).is_empty() {
                        s[i] = b;
                        self.backtrack(current | b, solutions, s);
                        s[i] = Bitboard::default();
                    }
                }
            }
        }
    }
    pub fn solve(&self, initial: Bitboard) -> Vec<[Bitboard; NUM_PIECES]> {
        let mut solutions = Vec::new();
        self.backtrack(
            initial,
            &mut solutions,
            &mut [Bitboard::default(); NUM_PIECES],
        );
        solutions
    }
}

通常backtrackingというとVecをstackとして使ってpush()とpop()による更新/復元を使って探索していくことが多いと思うが、この問題の場合は必ず全部使い切るまで探索を続けるものなので固定長の配列を使っている。

手元の環境(MacBook Pro 14-inch, 2021 Apple M1 Pro 32 GB)でrelease buildを使うことで以下のような結果を得た。

8x8-2x2: Found 520 solutions in 325.862ms
6x10: Found 9356 solutions in 11.493s
5x12: Found 4040 solutions in 24.804s
4x15: Found 1472 solutions in 50.362s
3x20: Found 8 solutions in 37.092s

解の数は、反転や回転による同一視をしていないので長方形では4倍、正方形では8倍の値になっている。それぞれ割れば前述した通りの数になる。

Bitboardによる判定と候補の事前計算によってある程度は効率的に探索ができているはずで、8x8-2x2の盤面なら1秒以内に全解答を列挙できているが、他の長方形はかなりの時間がかかっている…

反転・回転での重複の除外

全解答を探索することはできたが、反転や回転で同一になる解を除外することはできていない。これらを除外するためには、探索できた解とそれを反転・回転してできるものをすべてチェックし、既に発見済みの解と同一かどうかを判定する必要がある。

そのためには盤面に合わせてBitboardの反転・回転を実装する必要があるが、一旦これは後回しにして、とりあえず盤面のグリッド表現を愚直に作ってしまうことにする。

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, FromPrimitive)]
pub enum Piece {
    O = 0,
    P,
    Q,
    R,
    S,
    T,
    U,
    V,
    W,
    X,
    Y,
    Z,
}

impl Solver {
    ...

    fn represent_solution(&self, solution: &[Bitboard; NUM_PIECES]) -> Vec<Vec<Option<Piece>>> {
        let mut ret = vec![vec![None; self.cols]; self.rows];
        for (i, b) in solution.iter().enumerate() {
            let p = Piece::from_usize(i);
            for (y, row) in ret.iter_mut().enumerate() {
                for (x, col) in row.iter_mut().enumerate() {
                    if b & (1 << (x + y * self.cols)) != 0 {
                        *col = p;
                    }
                }
            }
        }
        ret
    }
}

これによって2次元配列として表現される盤面を得られるので、単純に反転・回転を実装することができる。 8x8-2x2の場合はXY軸を反転させたものも考慮する必要があるので、それも用意しておく。

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Board(Vec<Vec<Option<Piece>>>);

impl Board {
    fn is_square(&self) -> bool {
        let (rows, cols) = (self.0.len(), self.0[0].len());
        rows == cols
    }
    fn flip_x(&self) -> Self {
        let mut ret = self.clone();
        for row in ret.0.iter_mut() {
            row.reverse();
        }
        ret
    }
    fn flip_y(&self) -> Self {
        let mut ret = self.clone();
        ret.0.reverse();
        ret
    }
    fn flip_xy(&self) -> Self {
        let mut ret = self.clone();
        for row in ret.0.iter_mut() {
            row.reverse();
        }
        ret.0.reverse();
        ret
    }
    fn transpose(&self) -> Self {
        let mut ret = self.clone();
        for (y, row) in ret.0.iter_mut().enumerate() {
            for (x, col) in row.iter_mut().enumerate() {
                *col = self.0[x][y];
            }
        }
        ret
    }
}

あとはこれを使ってHashSetなどに同一解を登録しておき、本当に未発見の解だけを記録するようにすれば良い。

use std::collections::HashSet;

struct UniqueSolutionStore {
    solutions: Vec<[Bitboard; NUM_PIECES]>,
    set: HashSet<Board>,
}

impl UniqueSolutionStore {
    fn add_solution(&mut self, board: Board) {
        if !self.set.contains(&board) {
            self.solutions.push(*pieces);
        }
        self.set.insert(board.flip_x());
        self.set.insert(board.flip_y());
        self.set.insert(board.flip_xy());
        if board.is_square() {
            self.set.insert(board.transpose());
        }
    }
}

impl Solver {
    fn backtrack<S: SolutionStore>(
        &self,
        current: Bitboard,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut S,
    ) {
        if !pieces.iter().any(|u| *u == 0) {
            return store.add_solution(pieces);
        }
        ...
    }
    pub fn solve(&self, initial: Bitboard) -> Vec<[Bitboard; NUM_PIECES]> {
        let store = UniqueSolutionStore::new(...);
        self.backtrack(
            initial,
            (1 << NUM_PIECES) - 1,
            &mut [Bitboard::default(); NUM_PIECES],
            &mut store,
        );
        store.get_solutions()
    }
}

これによって、

8x8-2x2: Found 65 solutions in 362.164ms
6x10: Found 2339 solutions in 11.707s
5x12: Found 1010 solutions in 25.003s
4x15: Found 368 solutions in 51.320s
3x20: Found 2 solutions in 39.203s

と、全列挙していたときと探索時間はほぼ変わらず、正しく重複を除外した解を得ることができたようだ。

高速化

さて、とりあえずは正しく解を列挙できるようになったので、次は探索の高速化を考えてみる。これには様々な手法やテクニックが古くから研究されていたようだ。

短辺から埋める

まず重要なのが、「最上段から順番に左端から右端へと埋めていく」と考えたときに、盤面が長方形の場合は横長の盤面より縦長の盤面の方が探索が早く終わる、ということ。

これは例えばU型のピースを最初に変な向きで置いてしまったときのことを考えると分かりやすい。

##.............
.#.............
##.............
...............

4x15の盤面で左上から埋めていくと、最上段の残りの13マスをまず埋める探索を繰り返していくが、頑張って埋めたとしても埋める対象が2段目に来た時点で左端の1マスの空間はどうしても埋められないことが分かりそこで探索が止まる。

これが15x4の縦長盤面だと

##..
.#..
##..
....

...

となり、もっと早く2段目の不可能なマスに到達できるので、そこまでの無駄な探索が少なくなる。

なので、この探索方針の場合は横幅は短ければ短いほど効率が良くなる、ということになる。ので、6x10(6行10列)の横長盤面の場合は10x6(10行6列)の縦長盤面として、5x12は12x5に、と縦と横を入れ替えて探索することで効率が良くなる。解の表示が横長の方が良かったら表示時にだけまた入れ替えて戻してやれば良い。

当然8x8-2x2の正方形の盤面に対しては効果が無いが、それ以外の長方形たちは

6x10: 約12s → 約1.02s
5x12: 約25s → 約344ms
4x15: 約51s → 約82ms
3x20: 約39s → 約3.7ms

と何百倍、何千倍も高速化される。ものすごい効果だ。

`X` を最初に配置する

次に大きな効果を得られるのが、X型のピースを最初に配置して探索範囲を絞る、というもの。

4. Ｘピースによる解の重複排除の記事が詳しいが、X型のピースは反転しても回転しても同じ形になるので、盤面左上の1/4の領域にだけ最初に配置することで探索範囲を絞ることができる。それ以外の領域にX型ピースを置くことで得られる解は必ずその左上領域に置いて得られた解を反転/回転することで得られるものになるからだ。

さらにX型ピースは最も左上に配置すると左上隅に隙間ができてしまうので有り得ない、ということも分かるので、実際に初期配置として有り得る箇所は $\lfloor\frac{(W-1)}{2}\rfloor\times\lfloor\frac{(H-1)}{2}\rfloor-1$ 通りになる。最も多くても5x12のときの 9通り程度だ。それらを配置した状態を初期状態として、X型以外の11種類のピースで今まで同様のbacktrackingで探索していけば良い。

こうして得られる解は必ずX型ピースが左上の領域に存在することになり、前述した重複除外の手順と逆に、これらが重複を含まない解となる。そしてそれらを反転/回転したものを含めるようにすることで全探索した場合の解を得ることができるようになる。実際にはX型ピースが奇数マス長の辺の中央にいた場合は反転での重複が有り得るし、8x8-2x2の正方形の場合はXY軸を反転させたものへの重複チェックなどが必要になる。

最初の1ピースの配置箇所候補が1/4になるので、単純に探索規模が約1/4に減ることになる、つまり約4倍の高速化が見込まれる。

結果として

8x8-2x2: 約22ms
6x10: 約103ms
5x12: 約43ms
4x15: 約9ms
3x20: 約380μs

と、実際に約4〜10倍程度の高速化が確認された。

github.com

Bitboardの反転/回転

重複除外などの計算で盤面を反転/回転したものを得る必要があるが、簡単にするためにまずは盤面の2次元配列表現を愚直に作って処理してしまっていた。これを高速化するためにBitboardの反転/回転を実装する。これによってHashSetなどで重複チェックする際にも、キーとして [Bitboard; NUM_PIECES] がそのまま使用でき、2次元配列を作る必要がなくなる。

とはいえ盤面によってビット表現のレイアウトは違うし、それぞれに対する反転や回転を計算するのは簡単ではない。勿論64回のループを回して1ビットずつ反転後/回転後のビット位置を計算しながらコピーしていくこともできるが、それでは2次元配列作るのとあまり変わらず、旨味がない。

Delta Swap による手法

参考にしたのは以下の記事。 qiita.com

Delta Swap というXOR演算を利用した数回の操作で、maskで指定した範囲のビットを他の箇所のビットと入れ替えることができる。これを利用することで、例えば隣り合う列同士、のように複数のビットの交換を同時に行うことができる。次は隣り合う2列同士、その次は隣り合う4列同士、とすれば8列の反転が3回のDelta Swapで実現できる。行・列のそれぞれの長さに対し $O(\ln{n})$ 程度で盤面上での反転が機能する。また、8x8-2x2におけるXY軸の反転も、上述の記事に書かれている通り斜めに並ぶmaskを指定することで同様に3回のDelta Swapで実現できる。

盤面の縦横サイズによってビットのレイアウトが変わるので、必要なmaskの値もシフトすべきdeltaの値も異なるものを用意する必要があるが、盤面が決定した時点で事前に計算できるので、それらをVecで用意しておくことで、実際にはDelta Swapの計算は高速に行うことができる。

Const Genericsなんかを使って盤面サイズごとに定数値を埋め込んでおくともっと効率的かな、とも思ったが、試してみた感じではそれほど差異は無さそうだった。実際にBitboardの反転/回転の計算が必要になるのは解が見つかったときだけなので、探索の計算量と比較すると無視できる程度の差にしかならないのかもしれない。

巨大テーブルによるループ効率化

とにかく探索のループが何度も実行されるので、この処理を高速化することが重要になる。

まず使用済みのピースをBitboard同様にビットで管理する。i番目のピースが使用済みか否かのチェックは used & (1 << i) == 0 で判定でき、探索の終了はこの used で使うビットがすべて1になっているか否かで判定できる。そうするとbacktrackingから戻ってきたときにpieces[i]をわざわざdefault値に戻したりする必要はなくなる。

impl Solver {
    fn backtrack<S: SolutionStore>(
        &self,
        current: Bitboard,
        used: usize,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut S,
    ) {
        if used == (1 << NUM_PIECES) - 1 {
            return store.add_solution(pieces);
        }
        let target = current.trailing_ones() as usize;
        for i in 0..NUM_PIECES {
            if used & (1 << i) == 0 {
                for &b in self.table[target][i].iter() {
                    if (current & b).is_empty() {
                        pieces[i] = b;
                        self.backtrack(current | b, used | (1 << i), pieces, store);
                    }
                }
            }
        }
    }
}

ここまでは特に効率化できていないが、ここでself.tableから候補を探索する処理を考えてみる。

このtableには target(埋めるべきマスの位置)それぞれに対してi番目の種類のピースで配置可能なBitboardのリストが格納されている。ピースがすべて未使用なら12個のVecをすべて調べるし、残り1種類なら1個だけのVecに対して判定をしていくことになる。いずれにしても2重ループでの処理となる。

ただ、table自体は変更されるものではないので実際にtargetとusedの値の組み合わせに対して探索されるBitboardのリストは不変だ。少し富豪的な発想だが「使用済みピースの状態数は高々4096(= 1<<12)程度なのだから、これも事前計算でそれぞれ1つのVecとしてすべて用意してしまえば良いのでは？」と考える。

    let mut table: [[Vec<Bitboard>; NUM_PIECES]; 64] = array::from_fn(|_| array::from_fn(|_| Vec::new()));
    for (i, shape) in shapes.iter().enumerate() {
        ...
        for target in 0..64 {
            let b: Bitboard = ...;
            table[target][i].push(b);
        }
    }

のようにVec<Bitboard>を格納する[64, 12]の2次元配列として準備していたものを、

    let mut table: [Vec<Vec<(usize, Bitboard)>>; 64] = array::from_fn(|_| vec![Vec::new(); 1 << NUM_PIECES]);
    for (i, shape) in shapes.iter().enumerate() {
        ...
        for target in 0..64 {
            let b: Bitboard = ...;
            for j in 0..(1 << NUM_PIECES) {
                if (j & (1 << i)) == 0 {
                    table[target][j].push((i, b));
                }
            }
        }
    }

とVec<(usize, Bitboard)>を格納する[64, 4096]の2次元配列に拡張する。こうすることで、usedに対応する全候補リストを一発で引けるようになる。

    fn backtrack(
        &self,
        current: Bitboard,
        used: usize,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut dyn SolutionStore,
    ) {
        ...
        let target = current.trailing_ones() as usize;
        for &(i, b) in &self.table[target][used] {
            if current & b == 0 {
                ...
            }
        }
    }

結局判定する内容は変わらないが、このようにループ処理を変えるだけでも意外に明確に速度が改善された。

ただし、初期化のコストは大幅に増大する…。tableの準備段階で1<<12回のループを回すことになるし、格納する値も冗長になりメモリ消費量が増える。手元の環境では6x10の盤面に対し巨大テーブルを使うようにすることで探索時間が約70msから約50msへと短縮されたが、そのぶん初期化にかかる時間が約0.1msから約70msへと激増していて、トータルの実行時間でいうとむしろ遅くなっている。このあたりは探索を速くしたいのかトータルでの実行時間を短くしたいのか、によって使い分けることになるだろう。

github.com github.com

もう一方のループ効率化

巨大テーブルを使わないとどうしても速くならないのか、というとそうでもなく、usedの判定をしながらループを回すのも多少は効率化できる。

毎回12回のループを回して使用済みの場合はskip、としていると無駄な計算が多くなる。

    for i in 0..NUM_PIECES {
        if used & (1 << i) != 0 {
            continue;
        }
        ...
    }

ので、ここでもビット演算によって未使用ビットに該当するものだけを列挙するように変更する。

    let mut u = !used & ((1 << NUM_PIECES) - 1);
    while u != 0 {
        let i = u.trailing_zeros() as usize;
        ...
        u &= u - 1;
    }

これも将棋Bitboardで学んだテクニック。u &= u - 1で最下位の1を消していくことができるので、これをすべて0になるまで繰り返すだけ。少数のビットしか未使用のものがない場合に無駄なループ処理を省くことができる。

これによっても速度は改善し、巨大なテーブルを用意しなくても90msかかっていたものが70ms程度になるくらいの効果があった。

孤立点検出による枝刈り

探索処理自体の高速化はこれくらいにして、最後に枝刈りについて考える。

探索途中のある状態において、この先はどう置いても解が得られないと分かっている場合は、その時点で探索を打ち切ることでその先での無駄な探索を省くことができる。この枝刈りをどれだけできるかでも大きな速度の差が出る。前述した縦長と横長の交換も枝刈りを多く発生させるための工夫だ。

まず一番分かりやすいのはU型ピースを壁際に配置するときで、

#.#.
###.
....
....

や

##..
.#..
##..
....

のように1箇所の穴が壁際に生じてしまう向きで配置すると、その穴のマスはどうやっても埋めることができないのでその先の探索はすべて無駄になる。

同様に四隅に空白ができるような配置も考えられる。左上から埋める限りはその左上に空間はできないように埋めていくが、それ以外の3箇所の角では起こりうる。

########
########

...

###.....
..##....

こうした配置は最初から考慮できるので、候補の事前計算時に除外しておくことはできる。

あとは探索途中の状態における孤立空間を検出して枝刈りできるかどうか。

######
###o..
.#....

...

のように#が埋まっているとき、次に埋めるべきマスがoになるが、ここで次に配置するピースによっては、その右側や左下に空間が生じ得る。

######
####..
.#.##.
....##

や

######
####..
.#.#..
..###.

のような感じ。少なくとも5の倍数の面積でない空間が生じていると、もうそれらを埋める手段は存在しないので、可能であれば即座に探索を打ち切ってしまいたい。

しかし、こういった空間の検出やその面積の計算まで毎回行うのは探索の高速化には逆に計算負荷が増大して逆効果になったりする。検出のコストと枝刈りの効果のバランスを考える必要がある。

Bitboardを使用して簡単に検出することができるのは、孤立点の空間だ。あるマスが空いていて、その上下左右がすべて壁もしくは他のピースによって埋まっている、という状態。これは

..#..
.###.
..#..

のようなX型のmaskを用意し、そのmaskと現在の盤面BitboardのAND演算の結果が

..#..
.#.#.
..#..

の値になるか否か、という判定で簡単に実現できる。盤面上のマスすべてに対してこのmaskと値を事前に計算しておけば、いつでもこういった「穴」のマスを検出することができる。

とはいえ実際にこのような「穴」が生じ得るのは、targetとなる埋めるべきマスにピースを置いた後の、その周辺だけ。なので毎回の探索ごとに穴の出現を判定するのは最小限にしたい。

targetを埋めるようにピースを置いたときに穴が生じやすいのはtargetのすぐ右隣のマス、もしくはすぐ下の段の左隣のマス、だ。先述の図でいうとoに対してXの位置。この2点だけに絞ってピースを置いた後に穴が生じるかどうかを判定して枝刈りを行うことにした。本当はtargetの場所によって穴の発生が起こりやすい位置が違うかもしれないので一律に同じ相対位置にしないで調整した方が良いかもしれないが、そこまではやっていない。

######
###oX.
.#X...

...

    fn backtrack(
        &self,
        current: Bitboard,
        used: usize,
        pieces: &mut [Bitboard; NUM_PIECES],
        store: &mut dyn SolutionStore,
    ) {
        ...

        let target = current.trailing_ones() as usize;
        for &(i, b) in &self.table[target][used] {
            if current & b == 0 {
                let next = current | b;
                // `target`に対してチェックすべき`holes`は初期化時に計算しておく
                if self.holes[target].iter().any(|&(u, v)| next & u == v) {
                    continue;
                }
                pieces[i] = b;
                self.backtrack(next, used | (1 << i), pieces, store);
            }
        }
    }

最終的にこれらの工夫を施すことで、巨大テーブルを使用し初期化コストを無視することで探索自体は

8x8-2x2: 約22ms → 約9ms
6x10: 約103ms → 約44ms
5x12: 約43ms → 約18ms
4x15: 約9ms → 約3ms
3x20: 約380μs → 約147μs

くらいまで短縮することができた。 6x10ではどうしてもまだ40ms以上かかってしまうが、まぁ10秒以上かかっていた頃からすれば200倍以上は速くなっているし、じゅうぶん速くはなったと思う。

github.com

あとはマルチスレッド化したりすればもっと速くなるのかなぁ…。

その他の実装・手法

ここまでまったく触れなかったが、Pentomino Solverの実装として"Knuth's Algorithm X"というものを使う手法があるらしい。

en.wikipedia.org

Pentominoを含むPolyominoによる敷き詰め問題をExtract cover problemとして考え、その解法としてDancing Linksというデータ構造を利用して効率的に計算していく、というものらしい。以下の記事が詳しい。

matsu7874.hatenablog.com

実際に試していない(RustでLinked List的なものを扱うのが面倒そう、というのもあり…)が、これを使ってもそこまで劇的に速くなるわけでもないっぽい。参考記事でも触れているが全パターンの探索には効率的かもしれないが枝刈りのような処理がないはず？なので、今回のようにX型を最初に置いたり孤立点チェックをしたりといった高速化の工夫の方が探索時間の短縮には効果的なように思える。

WebAssembly化してWebAppで使う

RustでSolverを書けたので、WASM化してWebAppから使えるようにしてみた。最近はViteを使ってReact+TypeScriptの環境をさくっと作れると聞いたので、それで。探索は100msかからないくらいだしメインスレッドで実行しても良いかな、とも思ったが念のためWebWorkerで実行するようにしている。

sugyan.com

手元の環境ではCLIで実行するときと遜色ないパフォーマンスがブラウザでも実現できているが、どうもスマホ(iPhone SE)で試してみたところ巨大テーブルを使う方は最初の初期化に10秒以上の時間がかかる。メモリ確保がすごい重いんだろうか… 一度読み込んでしまえばその後はそこそこの速度になるようだけども。ともかくこれだとWebWorker経由じゃないと使いものにならない。

100msかからずに全解答を列挙できるようなブラウザ上で動く実装は他では見かけなかったので現時点では最速のWebAppになっているかもしれない。もっと速いものを知っている方は教えてください。

参考

とても参考にしたページ。

まとめ

最大限にチューニングするとどこまで速くできるものなのかは気になるところだけど、とりあえず自分が満足できるくらいのパフォーマンスでの探索は実現できた。