こんばんは。きなこ屋です。
早速ですが、次の[問題1]をご覧下さい。
次に、[問題2]をご覧下さい。
この2つは同じ問題です。
シャカシャカをやり過ぎて壊れた訳ではありません。[問題2]は[問題1]をシャカシャカとして実現したものです。
この記事ではシャカシャカでシャカシャカを再現する方法について考えていきます。
1. 完成図と動機
改めて問題2を注視しましょう。図の緑色に照らした部分に注目します。ここには、問題1の盤面16マスが1マスずつバラバラに切り離され、50マスおきに配置されています。
そして問題2を解いて緑の部分を抜き出すと、ちょうど問題1の正解盤面に一致するという仕掛けになっています。
言うなれば、シャカシャカ(問題1)のルールをシャカシャカ(問題2)で表現したわけです。
今回の構成法では、問題1だけではなく、任意のシャカシャカを問題2のようにメタ構成することが可能になっております。ただし盤面サイズは50倍になります。
('24 8/26追記：斜め2×3以上の白長方形を含む場合には上手くいかないとの指摘を頂きました。問題によっては再現可能である、と訂正します。)
動機はライフゲームのOTCA Metapixelというパターンです。ライフゲームでライフゲームが作れるならば、シャカシャカでシャカシャカも作れるはずですよね。
ここでは①シャカシャカで論理演算を作り、②論理演算でシャカシャカを作るという2段階の変換を行うことになります。
このうち①は過去に取り組んだ結果を利用できそうです。そこで②、シャカシャカというパズルを論理演算だけで再現する方法が問題になります。この記事ではその構成方法を解説していきます。
※シャカシャカで論理演算をする話はこちら
2. ルール
まず、シャカシャカのルールをおさらいしましょう。
- 盤面のいくつかのマスに三角形を配置する。
- 塗られずに残った領域は全て長方形(正方形も含む)になる。
- 数字は、周囲4マスに入る三角形の数を表す。
普段なら呼吸するように従っているルールですが、これを回路で再現するとなると話は複雑です。
ルール1：三角形を配置する
各マスに三角形を配置する方法は、4方向に加えて白マス(置かない)の計5通りあります。これを再現するには、何らかの形で「マス」を用意し、それが5つの解を持つようにしなければなりません。
そこで今回使うのが下図の形です。この5×5盤面を「マス」とし、5通りの解をそれぞれの置き方に対応させます。
後は「マス」同士を上手く繋ぐことで置き方に条件をつけてやればOKです。
ルール2：残った領域は長方形
このルールは大域的過ぎて曲者です。後でマス同士をケーブルで繋いで判定することを考えると、あまり遠くのマス同士や多くのマスを繋ぐわけにはいきません。
そこで簡略化に簡略化を図った結果、ルール2は次の2つに言い換えられました。
- 2-1：全ての三角形について、その左隣は図の2パターンの何れかになる。
曲がる(緑)か伸びる(橙)か - 2-2：全ての頂点について、隣接する4マスのうち、3マスが白マス(三角形が入らない)ならば、残り1マスは白マス或いは頂点を向く三角形。
これ以外の向きの三角形は入らない
以上2つを満たすことが、「残った領域は長方形になる」の同値な言い換えになります。多分。
これらは局所的な条件であり、周囲3~4マスの情報だけで判定することができます。
ルール3：数字は三角形の個数
これ自体はルール2と同様に局所的な制約です。しかし設計上の影響があります。
ルール1ではマスを5×5小盤面で再現しましたが、それは白マスの話。黒マスは三角形を入れられませんので、別な形を用意する必要があります。ルール3の存在により、黒マスは入力ではなく判定機の役割を担わなければなりません。
そこで用意したのが下図の形です。周囲4マスが白マスか否かを取得してこの機構に接続することで、ルール3を判定することができます。
ルール2と3の判定のためには、それぞれのマスから特定の向きに三角形が入っているかどうか等の情報を取り出し、それを「判定機」までケーブルで運び、判定にかける、という手順を踏む必要があります。しかし、ルール3の判定に必要な白マスか否かという情報をマスから引き出すのは簡単ではありません。それもマスに隣接する4頂点の全てでルール3を判定しますから、ただ引き出すだけでなく、その情報を4方向に分配する必要があるのです。
3. 構造
というわけで完成形を見てみましょう。
一見複雑に見える問題2ですが、実際には4つのパーツの組み合わせで構成されています。
- 白マス
マスを中央に有し、5通りの解から都合16の出力を行う基幹部分です。
- 黒マス
対応する数字を中央の黒マスに入れて、4方向の入力からルール3を判定します。なお巨大長方形たちは装飾です。
- 辺
隣接する2つのマスから6つの入力を受け、L字部分でルール2-1を判定します。
- 頂点
12~16の入力によって、中央でルール2-2を判定するとともに、辺から辺へ情報を受け渡します。
以上4ピース(と外周部の調整)の組み合わせによって、任意のシャカシャカの盤面をシャカシャカとして再現することができます。
詳細は割愛しますが、それぞれの制約判定の様子を眺めてみましょう。
- ルール2-1
- ルール2-2
- ルール3
4. 展望
本作にはまだまだ課題が残されています。
大き過ぎる
問題1,2ではたった4×4のシャカシャカを再現するために186×186の盤面を要しました。今回の構成ではピース同士は50マスおきですので、元の問題に対し約50倍の盤面サイズ・2500倍の面積を必要とします。
サイズが大き過ぎることの難点は、冗長すぎて人間の手に負えないことに加え、もう一つの致命的な弱点を抱えることにあります。
それは、URLが長過ぎること。
URLが長くなると、読み込みに時間がかかるばかりか、そもそも414エラーによって開いてくれないという事態に陥ります。
例えばぱずぷれv3の場合、通常の問題であれば150×150程度はぎりぎりエラーに引っ掛からずに開くことが出来るのですが、論理回路は黒マスが多いために100×150(2×3)程度が限度になってしまいます。
対処法として余分な空間を用意して黒マスを減らすことは可能ですが、本質的な対策はやはり伝達効率を上げてブロックあたりの面積を縮小することでしょう。
とりわけ信号を交差させる素子の使い勝手があまり良くなく、多重交差素子の開発に成功すればかなり省スペースが可能になると思われます。
また現状ではn×n盤面に対して約4(n-1)²回の判定が必要になりますが、ルール2-1,2-2,3を見直すことによって判定の回数を減らすことが出来ればこれまた縮小に貢献するでしょう。
シャカシャカに見えない
元はと言えばライフゲームのように「シャカシャカを解いて遠くから見ると大きなシャカシャカに見える」というものを目指したのですが、結果として回路の完成がやっとでした。
ということで目下の課題はシャカシャカの盤面を上手く再現する方法です。最近練習中のシャカシャカお絵描きを応用して頑張れるでしょうか。
上で述べたように回路を縮小することも、結果としてシャカシャカのように見えやすくなることに貢献するでしょう。
5. 終わりに
シャカシャカ→論理回路→シャカシャカという変換に挑戦しました。
次の目標は、シャカシャカに代えて他のパズル種を試すことです。一部のパズル種では論理回路を構築する研究があるようですので、パズル種によってはずっと面白いことが出来るのではないでしょうか。或いはシャカシャカで他のパズルを再現していくプロジェクトも面白そうです。
類似の研究が待たれます。
