17 June 2026
(ヘ)ヤジリンにおける黒マスの最大充填数の話
目次
もともとゆきこに出そうと思ったけど構築も証明も思いつくのは不可能だったので放流します
— hiro1729 / ゆきーみー (yukimy32) (@hiro_1729) May 27, 2026
H×Wのグリッドに隣接しないように黒マスを置いて、黒マスが通らないマス全てを通るハミルトン閉路を構築してください 黒マスはなるべく多くしてください (つまりヤジリン) https://t.co/IxB6mj8dyJ
これまでに上記テーマについて一定の研究を行ってきました。今回良い機会なので、まとめて公開することにします。
問題の再定義
上記の問題を、以下のように単純化します。
$H \times W$ のグリッドに、互いに辺で隣接しないように黒マスを置く。 黒マスを通らないマス（白マス）すべてをちょうど一度ずつ通るハミルトン閉路を構築できるとき、置ける黒マスの個数の最大値を求めよ。
- 黒マスは縦横で隣り合ってはならない（斜めはよい）。
- 白マスの集合上に、ただ一つの閉路（ループ）が存在し、その閉路はすべての白マスを通過する。
- 各白マスの「次数」はちょうど 2（ループが通過する辺がちょうど 2 本）。
- ハミルトン閉路が成立する黒マス配置のうち、黒マス数が最大のものを探す。
ペンシルパズルでは解の一意性、すなわち、ひとつの盤面に対して答えが一通りに定まることが求められますが、それは考慮しないものとします。
具体例(H=W=7で最大9個)
この問題を愚直に解く場合、あるマスが黒マスか白マスかという組み合わせをすべて試す必要があり、$H=W=10$程度でも$10^{30}$回以上の計算が必要になります。家庭用のコンピューターが1秒で行える計算は$10^9$回程度、1日かけても$10^{14}$回程度なので、文字通り天文学的な時間がかかってしまいます。
今回は、この計算量をアルゴリズム的な工夫によって減らし、できる限り大きなパターンを含めて調査しました。
解法の紹介
プログラムの中身について説明しています。興味のない方は飛ばして頂いて結構です。
ここをクリックして展開
解法1: 連結DP（フロンティア法）による厳密解
盤面の左上から右下に向かってマスを順に辿りつつ、「探索済みエリア」と「未探索エリア」の境界部分の情報（線や黒マス、線同士の連結に関する情報など）だけを保持しながら探索していく手法です。
「隣接するマスに黒マスは置けない」などの強力な制約による枝刈り（不要な探索の省略）を直接反映できるうえ、「境界部分の形が全く同じものがあれば、そのうちこれまでの黒マスが最も多いものだけを選ぶ」といった操作も可能になり、計算が大幅に短縮されます。実際、このDPを用いることでおおよそ$O(HW \cdot 3^W)$程度の計算量に抑えることができました。$H=W=10$なら$10^7$程度なので、家庭用パソコンでも1秒かからずに計算できます。それでも$H=W=15$を超えたあたりからは分単位の時間がかかりますが......
アイディアとしては以下の記事が近い。
https://ricky-pon.hatenablog.com/entry/2023/04/14/001438
解法2: ビームサーチによる最適解導出
解法1では、盤面が大きいと管理すべき状態数が増えすぎてしまい、メモリの使用量が爆発するという課題がありました。そこで、「これまでに置けている黒マスの数が多いもの」の上位だけを残すことで、「ほとんど正解に近いと思われる解」をある程度高速かつ現実的なメモリ使用量で得ることを考えました。このような手法は、一般的にビームサーチと呼ばれます。
今回は解法1のDPにほぼそのままこの発想を適用しました。もっとうまいやり方があるかも。
解法3: cspuz-solver2に解いてもらう
semiexpさん (website) が開発した、ペンシルパズルをSAT（充足可能性問題）に帰着して解くソルバーです。世界に数多ある超難解パズルをさらっと解く魔法のツール。いつもお世話になっております。
メモリ使用量が少ない点がメリット。問題を直接解くというよりは、$H \times W$で黒マスを$N$個にすることは可能か？ というYesNo問題を一晩かけて解かせるのに使いました。
厳密解(H=Wの場合)
| H=W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 7 | 9 | 18.4% |
| 8 | 16 | 25% |
| 9 | 19 | 23.5% |
| 10 | 22 | 22% |
| 11 | 29 | 24.0% |
| 12 | 36 | 25% |
| 13 | 41 | 24.3% |
| 14 | 48 | 24.5% |
| 15 | 55 | 24.4% |
| 16 | 66 | 25.8% |
| 17 | 73 | 25.3% |
| 18 | 84 | 25.9% |
元ツイートの引用で紹介されていた通り、10x10の盤面であれば、黒マスの個数は22個が最大となります。
注意が必要なのは、この計算では解の一意性を考慮していないということです。すなわち、ハミルトン閉路（黒以外のすべてのマスを通る周回パス）が1通りに定まらないケースも答えとして含んでいるため、実際のヘヤジリンでは問題として成立しないケースも含まれている可能性があります。（特に、H=W=8で黒マス16個のケースにおいて唯一解のパズルは多分存在しません。H=W=11で黒マス29個のケースも怪しいです。誰か作れたら教えてください）
例1-1: 10 x 10で22個の例
例1-2: 12 x 12で36個の例
例1-3: 16 x 16で66個の例
いずれも難易度「★4 アゼン」上位から「★5 ハバネロ」レベルの超上級者向け。自信がある方は問いてみてください。（無理でもcspuz-solver2が解いてくれます）
厳密解(H!=Wの場合)
H >= Wとし、以下にまとめます。作る際はもちろん、解く際にも本当に稀に使えます。
ここをクリックして展開
H = 3
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 1 | 11.1 |
H = 4
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 2 | 16.7 |
| 4 | 4 | 25.0 |
H = 5
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 3 | 20.0 |
| 4 | 4 | 20.0 |
| 5 | 5 | 20.0 |
H = 6
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 2 | 11.1 |
| 4 | 4 | 16.7 |
| 5 | 6 | 20.0 |
| 6 | 6 | 16.7 |
H = 7
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 3 | 14.3 |
| 4 | 6 | 21.4 |
| 5 | 7 | 20.0 |
| 6 | 8 | 19.0 |
| 7 | 9 | 18.4 |
H = 8
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 4 | 16.7 |
| 4 | 8 | 25.0 |
| 5 | 10 | 25.0 |
| 6 | 10 | 20.8 |
| 7 | 12 | 21.4 |
| 8 | 16 | 25.0 |
H = 9
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 5 | 18.5 |
| 4 | 8 | 22.2 |
| 5 | 11 | 24.4 |
| 6 | 12 | 22.2 |
| 7 | 15 | 23.8 |
| 8 | 16 | 22.2 |
| 9 | 19 | 23.5 |
H = 10
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 4 | 13.3 |
| 4 | 8 | 20.0 |
| 5 | 10 | 20.0 |
| 6 | 12 | 20.0 |
| 7 | 14 | 20.0 |
| 8 | 18 | 22.5 |
| 9 | 20 | 22.2 |
| 10 | 22 | 22.0 |
H = 11
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 5 | 15.2 |
| 4 | 10 | 22.7 |
| 5 | 13 | 23.6 |
| 6 | 14 | 21.2 |
| 7 | 17 | 22.1 |
| 8 | 20 | 22.7 |
| 9 | 23 | 23.2 |
| 10 | 24 | 21.8 |
| 11 | 29 | 24.0 |
H = 12
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 6 | 16.7 |
| 4 | 12 | 25.0 |
| 5 | 14 | 23.3 |
| 6 | 16 | 22.2 |
| 7 | 18 | 21.4 |
| 8 | 24 | 25.0 |
| 9 | 26 | 24.1 |
| 10 | 28 | 23.3 |
| 11 | 32 | 24.2 |
| 12 | 36 | 25.0 |
H = 13
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 7 | 17.9 |
| 4 | 12 | 23.1 |
| 5 | 15 | 23.1 |
| 6 | 16 | 20.5 |
| 7 | 21 | 23.1 |
| 8 | 24 | 23.1 |
| 9 | 27 | 23.1 |
| 10 | 30 | 23.1 |
| 11 | 35 | 24.5 |
| 12 | 38 | 24.4 |
| 13 | 41 | 24.3 |
H = 14
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 6 | 14.3 |
| 4 | 12 | 21.4 |
| 5 | 16 | 22.9 |
| 6 | 18 | 21.4 |
| 7 | 22 | 22.4 |
| 8 | 26 | 23.2 |
| 9 | 30 | 23.8 |
| 10 | 32 | 22.9 |
| 11 | 38 | 24.7 |
| 12 | 40 | 23.8 |
| 13 | 44 | 24.2 |
| 14 | 48 | 24.5 |
H = 15
| W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 3 | 7 | 15.6 |
| 4 | 14 | 23.3 |
| 5 | 19 | 25.3 |
| 6 | 20 | 22.2 |
| 7 | 23 | 21.9 |
| 8 | 28 | 23.3 |
| 9 | 33 | 24.4 |
| 10 | 36 | 24.0 |
| 11 | 41 | 24.8 |
| 12 | 44 | 24.4 |
| 13 | 47 | 24.1 |
| 14 | 52 | 24.8 |
| 15 | 55 | 24.4 |
ヒューリスティックな手法を用いた暫定解(H=Wのみ)
解法2を活用し、「厳密ではないけどこれ以上の値なのは間違いない」と言える値を導出しました。 （19x19だけは、黒マス97個の解が存在しないことをcspuz-solver2で確認しました。）
| H=W | 黒マスの最大数 | 充填率 |
|---|---|---|
| 19 | 95 | 26.3% |
| 20 | >= 106 | >= 26.5% |
| 21 | >= 117 | > 26.5% |
| 22 | >= 130 | > 26.8% |
| 23 | >= 143 | > 27.0% |
| 24 | >= 158 | > 27.4% |
| 25 | >= 171 | > 27.3 % |
| 26 | >= 186 | > 27.5% |
| 27 | >= 201 | > 27.5% |
| 28 | >= 218 | > 27.8% |
| 29 | >= 235 | > 27.9% |
暫定解でしかありませんが、H=Wが大きくなるほど、少しずつですが充填率は向上していそうです。
今回使ったコードは評価関数が雑すぎるので、ちゃんとチューニングすれば少ない計算量でもこれと同程度orより良い結論に辿り着けそうな気がします。
さらに大きなケースにおける予想
充填率については、無限大に飛ばせば1/3に収束すると思います。
より具体的な個数については、H=W=N, 黒マスの最大数を$a_N$として、概ね
$$a_N = \frac{1}{3} (N-A)^2 + BN$$ $$ \ \ (A \geq 4, \ B \leq AN)$$
程度になっていくと予想しています。要するに、「壁周辺以外の充填率は1/3で、壁周辺は1/4かそれ未満」というあたりかなと。
ただし、N >= 50以上のような極端なケースの最大数を探求する価値は、少なくともペンシルパズルとしてはないに等しいと思います。解けないし作れないので......
例3-1 24x24で150個の例（充填率26.0%）
例3-2: 36x36で366個の例（充填率28.2%）
(唯一解あり。面倒なのでcspuz-solver2などに解いてもらうことを推奨します)
例3-1と3-2はサイズが違うだけで黒マスのパターンは全く同じ。24x24の最大個数が158以上であることを考えるとかなり弱いパターンと思われますが、これと同じことを120x120でやれば充填率31.7%、1200x1200でやれば32.8%になります。
