"ワンのタイル"については[このページ]が参考になりました。 もともとはこのパズルというか落ちゲーみたいなルールで無限の空間を敷き詰めることができるか、という問題。それが「わからない」ことが証明できるんだけど、どうやって証明するかというと、タイリングでチューリングマシンをエミュレートできて、チューリングマシンでは計算が止まるか止まらないか予測できない問題があるのでワンのタイルも敷き詰めることができるかできないかは分からない、て感じです。有限の空間を敷き詰めることができるか、という問題なら全ての方法を試して見ればいいけど、目茶苦茶時間がかかります。
ちなみに、マインスイーパーでもチューリングマシンを作れるらしいです(くわしくはこちら)。さらに、ライフゲームでも作れます。『ライフゲイムの宇宙』 ISBN:4535783837 に詳しいです。
http://www.zillions-of-games.com/cgi-bin/zilligames/submissions.cgi/37667?do=show;id=1089 ワン・タイリングのゲームです。ダウンロードは無料だけど実行には専用のソフトを購入する必要があるようです。自分でも作ってみようと思います。
