ヘヤワケ

へやわけ（日本語：へやわけ）は、ニコリ社が発行する二分決定論理パズルです。2013年現在、ニコリ社からへやわけパズルのみで構成された5冊の本が出版されています。このパズルは、パズル通信ニコリ第39号（1992年9月） に初めて掲載されました。

Heyawakeは、標準サイズのない長方形のセルのグリッド上でプレイされます。グリッドは、セルの端に沿った太線によって、さまざまなサイズの長方形の「部屋」に分割されます。一部の部屋には、通常、左上のセルに印刷されている 1 つの数字が含まれます。当初の設計では、すべての部屋に番号が付けられていましたが、これは解決にほとんど必要ないため、現在は従われていません。

パズルのセルの一部は黒く塗る必要があります。パズルの目的は、各セルを塗るか、空白のままにするか (白のままにするか) を決定することです。実際には、既知の「空白」セルを何らかの方法でマークする方が簡単な場合がよくあります。たとえば、セルの中央に点を配置するなどです。

どのセルがどのセルであるかは、次のルールによって決まります。

• ルール 1: ペイントされたセルは、直交して接続することはできません (対角線で接することはできますが、辺を共有することはできません)。
• ルール 2: すべての白いセルは相互に接続されている必要があります (単一のポリオミノを形成します)。
• ルール 3: 数字は、その特定の部屋に塗装されたセルがいくつある必要があるかを正確に示します。
• ルール 4: 番号のない部屋には、任意の数の塗装されたセルが含まれる場合もあれば、まったく含まれない場合もあります。
• ルール 5: 白いセルが直線 (直交) に繋がっている場合、その直線には 2 つ以上の部屋のセルを含めることはできません。つまり、3 つ以上の部屋を繋ぐ白いセルの直線は禁止されています。

最初の 2 つのルールは (たとえば)ひとりパズルにも適用され、これらのパズルの解決方法の一部が共通していることに注意してください。

• あるセルが黒く塗られていることがわかった場合、隣接する 4 つのセル (直交するセル) はすべて白でなければならないことがすぐにわかります (ルール 1 より)。
• (直交する) 連続した白いセルのセクションは、グリッドの残りの部分から切り離すことはできません (ルール 2 より)。黒いセルは、グリッドを横切る斜めの分割や閉じたループを形成することはできません。このような「短絡」を完了するセルは、代わりに白でなければなりません。

より複雑なパズルでは、推測せずに進めるためにルール 1 とルール 2 を組み合わせる必要があります。鍵となるのは、セルが 2 つの市松模様のパターンの 1 つをとる必要がある場所と、1 つが短絡につながる場所を認識することです。

残りのルールは、Heyawake を他の「王朝」パズルと区別します。

• ルール 5 はパズルの定義ルールです。黒いセルは、2 つの部屋の境界を横切る (「スパナ」) 白いセルの (直交する) 線を防ぐために配置する必要があります。
• 番号の付いた部屋は通常、他の推論とともに、解答者に開始場所を提供します。以下は、最初に定義された部屋の最も単純な例です。
  • グリッドの角にある 2×2 の部屋には、グリッドの角に 1 つの塗りつぶされたセルがあり、角から斜め外側に 2 つ目の塗りつぶされた正方形がなければなりません。塗りつぶされた正方形は辺を共有できないため (ルール 1)、唯一の代替案は、角にある強制された白いセルを切り離すことですが、これはルール 2 に違反します。
  • 2×3 の部屋で、3 セルの辺が「3」を含むグリッドの境界線に沿っている場合、上記と同様の理由により、境界線に沿った 3 セルの辺の中央に 1 つのセルをペイントし、部屋の反対側の角に他の 2 つのセルをペイントする必要があります。
  • 1×3 の部屋に「2」が入っている場合、中央のセルを塗るとルール 1 に違反するため、両端のセルを塗る必要があります。より一般的には、1×(2 n −1) の部屋にnが入っている場合、その部屋内の他のすべてのセルを塗る必要があります。
  • 「5」を含む 3×3 の部屋には、すべての角と中央のセルが塗られた市松模様が必要です。

• Heyawacky はHeyawake と同じようにプレイしますが、部屋は必ずしも長方形ではありません。白いセルの直交線は部屋から出て再び部屋に入ることはできません。つまり、そのような線は複数の領域境界にまたがることはできません。
• 対称性ヘヤワケ（別名エカワエ、アヤヘヤ）はヘヤワケと同じようにプレイしますが、ヒントによって部屋の黒いマスのパターンがその中心に対して回転対称であるかどうかが示されます。

Heyawakeの計算の複雑さは分析されています: ^[1] Heyawakeの特定のインスタンスに対してパズルの解が存在するかどうかを判断することはNP完全です。この理論的結果を素人の言葉で解釈すると、このパズルはブール充足問題と同じくらい解くのが難しいということです。ブール充足問題とは、コンピュータサイエンスでよく研究されている難しい問題です。

ニコリパズルの種類一覧

• Holzer, Markus; Ruepp, Oliver (2007)。「インテリアデザインの悩み - ゲーム Heyawake の複雑性分析」(PDF)。議事録、第 4 回アルゴリズムを楽しむ国際会議、LNCS 4475。Springer、ベルリン/ハイデルベルク。pp. 198–212。doi :10.1007 / 978-3-540-72914-3_18。ISBN 978-3-540-72913-6。

• Heyawake の Nikoli のページは、Wayback Machineで 2013-11-09 にアーカイブされています。