スターバトル手筋集

たのしい星間戦争

 0. ルール

・盤面のマスに星を1つまで配置し、盤面の各行・各列・各部屋に指定された個数の星があるようにする。

・星はタテヨコナナメに接触しない。

指定される星の個数は 2 個のことが多いので、以下その場合を念頭に解説する (一般の場合でもだいたい同じ議論ができる)

 

1. 基本原理

接触禁により、「2×2 のマスには星が高々 1 つしか入らない」とわかる。基本の手筋でも応用的な手筋でもこれを使うことになる。

また、星の位置が二択になった場合、そのどちらにも接するマスはすべて白になる。たとえば 1×2 のマスのどちらかに星が 1 個入るとき、長さ 2 の方に接する横 4 マスは白になる。これは上の 2×2 の原理の応用としても捉えられるが、頻出なのでもはや基本原理ともいえる。

斜め接触した 2 マスや L 字の 3 マスでも、同じようにいくつかのマスが白くなる。ただ情報としては使い勝手の悪い印象がある。 (他の手筋にあまり繋がらない?)

 

2. 初級手筋・小さい部屋における星の位置/白マスの確定

小さい部屋だと、その中で星の位置が確定することがある。位置として二択が残ることもあるが、基本原理によりその周囲のマスが白マスとわかることが多い。ペントミノの P 型とかなどが例。だいたいが 2x4 の長方形に完全に含まれているパターンで、2x3 にだともっと決まる、みたいな感じ。

また、星の位置が確定せずとも、周囲で白マスが確定することがある。これは「領域に接触しすぎたせいで、星を置くと領域に星を 2 個置けなくなって矛盾」というタイプの推論となる。ペントミノの V 型、I 型などが例。

なおこの議論は複数の部屋をまとめても行える。たとえば 4x4 に 2 の部屋が入ってしまうような場合。もはや応用手筋だが。

白マスがたくさん確定した行や列でも、同じように星の位置が確定することがある。上級手筋を探していると、行や列単独だと見落としがちなので注意 (どうしても部屋に注目しがちなので)。

 

3. 応用原理

数独の Fish に似た原理として次のものがある。カバーの原理とよぶことにする。:

 

領域 C, D があり、C が D を覆っているとする。また、C には s 個以下の星しか入らず、一方 D には s 個以上の星が入るとする。

このとき、C と D の共通部分にちょうど s 個の星が入り、C のマスであって D のマスにならないところには星が入らない。

 

抽象的な言い方をしたが、少し考えれば当たり前である。しかしこの原理の汎用性は高い。というかこれ以降の手筋は大体これで説明がつく。

このカバーの原理の C や D は、いくつかの領域、 二択・三択が確定したマスの集まり、など をまとめて使うことが多い。

たとえば、同じ列で二択の 1×2 が 2 個作れた場合、その二択以外の列のマスはすべて白マスになる。これは、

C:二択の 4 マス

D:列

s = 2

として原理を適用している。実際に解くときは、いちいち原理なんて思い出さずにバツを打つはずだけど...

 

4. 中級手筋・部屋の偏りと列

k 個の部屋が k 列に収まる場合、その k 列のうち k 個の部屋の外のマスは白になる。逆に、k 個の部屋が k 列を収める場合、その k 個の部屋で k 列以外のマスは白になる。どちらもカバーの原理による (s = 2k)。

またちょうど k 列に収まっていなくても、はみ出たマスが小さかったり、部屋の外に星がいくつか星が入るとわかるケースでは、似たような議論ができる場合がある。

 

5. 中級手筋・2 列まとめる

これまでの原理を適用するときは、「基本原理を使って個数を評価し、それらをまとめてカバーの原理を使って星の位置を確定させる」という議論の流れになりやすい。そこでよく出てくるのが、2 列まとめて考えるケース。なぜかというと、2 列まとめると 2×2 に分割しやすく、さらに余分な場所が少ないため上限・下限が一致しやすいからである。部屋に関係なく進んでしまうのもミソ。やはりこれも、解くときは部屋に意識が集中しがちなので、列で見るタイプの理詰めは見落としやすい。

星 2 個の場合、2 列に星 4 個入るので、長さ 8 (つまり2x8) だとカバーの原理の適用ができるようになる。端っこにバツが並んだときは意識すべし。ただ 2*2 に 1 個という評価だけではうまくいかないこともあるので、深追いはよくない。ちなみに長さ 7 になったらフィーバータイム。

 

6. 上級手筋・一般の応用原理

中級手筋ではカバーの原理のわかりやすい適用を見たが、実際の問題ではいろんな形で出てくる。各行・各列・領域で個数が確定している上、基本原理により「2*2 の長方形で 1 個」といった評価がしやすいためである。

パターンはいろいろあるので頑張って見つけよう。たとえば、部屋 2 つを列と 2*2 長方形 2 つでカバーしたり、部屋 2 つを 2*2 長方形 4 つでカバーしたり、部屋 4 つを行と列 4 本でカバーしたり、など様々。いろんなパターンが出題されている。

 

7. その他の話

接触禁や、各行各列各領域 2 個といった条件が強すぎるため、残念ながら手に負えない確定の仕方もたくさんある。それでも頑張って理詰めしたり仮定したりで確定させに行けることもある。

 

8. その他・フィン

2 の後半で述べた白マス確定に似ている。カバーの原理において領域 C が D をカバーしきれなかったとしても、 D のうちはみ出たマスに星がある場合と無い場合、いずれにしても白になる場所は白マスと確定する。はみ出たマスをフィンなどとよぶことにする。数独の Finned Fish や、美術館のフィンと原理は同じ。

 

9. その他・チェイン

「マス (or マスの集合) に星が入るか」という命題が真か偽か、という情報を連鎖させることで解くことができるケースもある。一見仮定が必要そうでも、チェインを使って仮定を回避し理詰めで解き切れる場合もある。要するに二択を連鎖させて確定まで追い込むということである。

連鎖で使うのは弱リンク (両方真にはならない) と強リンク (両方偽にはならない)。弱リンクは、注目する 2 マスが接触していれば自動的に成立してしまうし、高々 1 個しか入らない領域の 2 マスについても成立する。また強リンクも 2 マスのうちどちらかに星とわかれば成立する。よってチェインは非常に汎用性が高い。マス単独でなく、グループ化したマスを考えるのもアリ。

チェインの基本は強弱リンクが交互にくるループで、一か所だけ弱リンクが続く場所があれば、それらがつながるマスが白と確定する。強リンクが連続してもいいし (そのマスが星と確定)、交互だけで一周してもよい (その場合は二択になり、すべてのリンクが強チェインかつ弱リンクに昇格する)。グループ化を使うこともある。詳しくはチェインの記事を参考のこと。

 

10. その他・仮定

それでもどうにもならないこともある。実際には入り組んだチェインになっている場合もあるが、実戦ではそれを短時間で見抜くのは難しい。そんな場合はおとなしく仮定しよう。というか、簡単なチェインですら仮定した方が速く解ける場合がほとんどかもしれない。

仮定というと敬遠しがちだが、すぐに詰むパターンもある。「ここに置くとこれこれこうなって詰み」というのが仮定だけど、この「これこれ」が短いパターン。単純仮定とでもいうべきか。

単純仮定でよく見るのは、終盤二択が多い時に、あるマスを置くと、それに接触する二択が決まってしまい、列の個数がオーバーしてしまう(逆に置けなくなる)、というやつ。自分は「押し出し」と呼んでいる。カバーの原理の絡むチェインとも見れなくもないが、シンプルに仮定した方が速いケースがしばしば。このへんは、よくある議論をたくさん解いて学ぶしかないかも。

よくあるパターンすらなく、どうしようもなくなって仮定が必要になったとする。このときポイントは、仮定する場所が真でも偽でも議論が大きく進みそうな場所を選ぶこと (これはスターバトルに限らず一般のパズルで大事なこと)。

たとえばマスに星が入るかで仮定するときは、入らないときに位置確定が大きく進むような場所で行うのが望ましい。入るときはだいたい大きく進みやすい。たとえば「このマス白ならカバーの原理などで大きく進むのになー」みたいな場所で仮定するといい感じ。

 

11. その他・ミス論

スターバトルはミスやハタンが起きやすいパズルと思われる (個人的な感想です)。ミスの原因としては

・行、列、領域の星の個数の把握ミス。部屋が白マスで分断されたせいで個数の把握を誤る、など。

・議論のミス。誤った議論により本来星のマスを白マスとしてしまった、など。

・誤った配置。星を接触させたまま気付かず解き進めてしまった、など。

といったものが考えられる。いずれも意識から漏れやすいと思うので、十分注意して行うこと。また修復不可能なら潔く全消しするのも手。大きなタイムロスになるためあまり行いたくないが、一度ミスると星の位置が大幅にずれることが多い気がする。 解空間を泳げる自信のある人でない限り、そのまま修正するのはおススメしません。

 

12. おまけ・n stars in 4n*4n

部屋にかかわらず、星の配置は 2 通りに限定される。

なお、この事実から星 2 個のときの盤面の適正サイズは9, 10, 11くらいと推測される (9だと少し狭め、12以上は部屋の形がそれなりに特殊になる?)。

 

13. おまけ・1 star

白マスの確定が独特なので注意。もはや別ゲー。

 

 

以上。他に特筆すべき手筋があれば、コメント等でご連絡ください。