橋をかけろ

橋をかけろ（はしをかけろ）は、ニコリ社が出版している論理パズルの一種である。 ^{[1]英語では}BridgesまたはChopsticks という名前で出版されている（誤訳に基づく：タイトルの「橋」は橋を意味し、「箸」は箸を意味する）。また、タイムズ紙にHashiという名前で。フランス、デンマーク、オランダ、ベルギーではAi -Ki-Ai という名前で出版されている。

ハシをかけてろは、標準サイズのない長方形のグリッド上でプレイされますが、グリッド自体は通常描画されません。一部のセルには、1 から 8 までの数字 (通常は丸で囲まれています) が描かれており、これが「島」です。残りのセルは空です。

目標は、島々の間に一連の橋を描いてすべての島々を結ぶことです。橋は特定の基準に従う必要があります。^[2]

• 出発地と目的地は別々の島で、その間は直線で移動する必要があります。
• 他の橋や島を渡ってはいけません。
• それらは直交方向にのみ実行できます（つまり、斜め方向に実行することはできません）。
• 2 つの島を結ぶ橋は最大 2 つあります。
• 各島に接続されている橋の数は、その島の橋の数と一致する必要があります。
• 橋は島々を 1 つの連結されたグループに接続する必要があります。

ハシヲカケロパズルを解くことは手続き的な力の問題である。橋をどこに架けなければならないかを決めて、そこに橋を架けることで他の橋を架けられる可能性のある場所を排除し、別の橋を架けることを強制する、などである。^[3]

角に「3」、外縁に「5」、またはどこでも「7」と表示されている島には、各有効な方向に少なくとも 1 つの橋が放射状に伸びている必要があります。1 つの方向に橋がない場合、他のすべての方向に 2 つの橋があっても、十分な数の橋が配置されていないことになります。角に「4」、境界に「6」、またはどこでも「8」と表示されている島には、各方向に 2 つの橋が必要です。これは、追加された橋がルートを妨げるため、一般化できます。たとえば、垂直方向からしか移動できない「3」には、上下にそれぞれ少なくとも 1 つの橋が必要です。

ブリッジの割り当て数に達した島には、線を引いたり埋めたりするのが一般的です。^[2] これは、間違いを減らすだけでなく、潜在的な「短絡」を見つけるのにも役立ちます。すべての島は 1 つのブリッジ ネットワークで接続する必要があることを念頭に置いて、それ以上ブリッジを追加できない閉じたネットワークを作成するブリッジは、それがすぐにパズル全体の解決につながる場合にのみ許可されます。この最も単純な例は、互いに 1 が並んでいる 2 つの島です。パズル内の唯一の 2 つの島でない限り、ブリッジで接続することはできません。そうすると、追加できないネットワークが完成し、その結果、その 2 つの島に他の島が到達できなくなるためです。

島のグループを別のグループから完全に分離する橋は許可されません。そうすると、接続できない島のグループが 2 つ存在することになります。ただし、この推論は、はしをかけろパズルではあまり見られません。

ハシウォカケロパズルに解があるかどうかの判定は、整数座標単位距離グラフのハミルトン閉路を見つけることからの還元により、 NP完全である。^[4] GLPKに含まれるMathProgの例には、整数線形計画法を使用した解法がある。^[5] 400までの島を数えるパズルのライブラリと整数線形計画法の結果も報告されている。^[6]

ハシヲカケロは、パズル通信ニコリ第31号（1990年9月）に初めて登場しましたが、このパズルの以前の形は第28号（1989年12月）に掲載されました。

• ニコリパズルの種類一覧

ウィキメディア・コモンズには、ハシゴをかけてに関連するメディアがあります。

• ニコリのハシゴケロ英語ページ