Net

quiz

http://d.hatena.ne.jp/succeed/20081004#c1223126963

これはこれで迷惑なんだが、 このゲームの存在も迷惑。
http://www.jurjans.lv/stuff/net/FreeNet.htm
大学から帰れなくなった。

http://www.jurjans.lv/stuff/net/FreeNet.htm

これ実は大学の二年生ごろにこれの幻覚を見るほどやった。
難易度のばらつきが大きいのでタイムアタックにはむかない。ただ、この状況でここが決まるという定理を量産するのにはまったのだ。
一辺の長さが n の初期状態を受け取り正解を出力とする問題クラスの NP 完全性を証明してみよう。これはたぶん SAT に帰着する。


まずは、問題の定式化。
n*n の升目に次の五種類の駒のどれかが置かれている。

  • T字路
  • 直線路
  • L字路
  • 行き止まり
  • 空白(実際のゲームではこれはめったに出ない)

これらを適当に回転させてグラフ理論でいうところの木を作る。また、升同士の境界には壁を作っていいことにする。

wire と NAND と bridge と branch と terminator を作ればいいに違いない。