Post

Conversation

パジョカ (Pajoca)
@Pajoca_
マインスイーパーは地雷の場所が 1 箇所確定すると近接するここが確定して次に隣のここが確定して… という配置確定の伝播を用いて配線と論理ゲートが構成できて、盤面を無限に広めればマインスイーパーがチューリング完全になる話面白くて好き NOT や OR ゲートは比較的単純に実装できる
マインスイーパーで論理回路を実装するうえで必要になる各パーツ(配線・NOTゲート・ORゲートの画像と説明) <画像に埋め込んだテキスト> 基本となる配線 便宜上、隣接する2マスのうち左側に地雷がある状態を「0」 右側に地雷がある状態を「1」とする。(地雷の数じゃなくて回路の0/1の話) 例えば「0」：左端のマスに地雷があることが確定すれば、その右隣に地雷は無し、 次の2マスの左側に地雷あり、その次の2マスも左側に地雷あり、… と次々に 地雷が左側という情報を伝播できる。 (右側に地雷という場合も同様) NOT ゲート 左側に地雷がある状態でこのゲートを通過すると右端の矢印の根本(赤3の隣)に 地雷が無いことが確定するのでそこに配線を接続すれば左側に地雷がない状態に 反転できる (その逆も同様に反転) OR ゲート ※片方縦になっているけど、90°回転するターン回路が別途作れるので大丈夫 少なくとも一方が「1」なら出力も「1」になる NOT, OR ゲートがあれば他の全ての論理演算を実装できる ※他に配線の分岐や交差を可能にする部品もある <画像の出典> sed.free.fr, "Minesweeper is NP-complete" http://sed.free.fr/complex/mines.html （2026年5月5日アクセス）
read image description
6,431
Views