三目並べの譜面全パターン分析

3×3のマス目に○(先手)と×(後手)のマークを交互に埋めていき、縦・横・斜めのいずれかで同じマークが3つ並ぶと勝ちという2人対決ゲームがあります。 3×3=9つのマス目に「○」「×」「未配置」の3つのどれかが入ると考えると、位置まで区別すると全部で$3^9=19683$パターンの状態が存在しますが、対称性を考慮すると自明ではありません。対称性まで考慮してそもそも何パターンの状態が存在するのかを調べました。

準備:対称性の確認

3×3のマス目は正方形なので、4回(90°回転)の回転対称性と4本の軸対称性(横軸、縦軸、右上斜軸、右下斜軸)があります。 三目並べの場合、譜面を回転・反転しても本質的には同じとなるため、同一の譜面とみなします。さらに、回転した後に反転した譜面も同様に同一の譜面とみなせます。 次の結果は3×3のマス目に左上から順番に1から9の数字を記入した譜面を、「回転→反転」、「反転→回転」させた際の全譜面です。

元の並び


回転 → 反転

0°回転90°回転180°回転270°回転
反転なし
横軸対称反転
縦軸対称反転
右上斜軸対象反転
右下斜軸対象反転

反転 → 回転

「回転 → 反転」のどれかと必ず一致するため考慮する必要はありません。

0°回転90°回転180°回転270°回転
反転なし
横軸対称反転
縦軸対称反転
右上斜軸対象反転
右下斜軸対象反転

点対称反転

正方形には点対称も存在しますが、2次元の場合は180°回転と同じとなるため、考慮する必要はありません。


全譜面の列挙(対称性を考慮)

「○」→「×」→「○」→「×」→「○」→「×」→「○」→「×」→「○」 と順番に埋めていった場合の、0手目から9手目までの全パターンを列挙します。 なお、途中で勝敗が決定した場合も9手目まですべて埋めるとします。

0手目:


1手目:


2手目:


3手目:


4手目:


5手目:


6手目:


7手目:


8手目:


9手目:


合計:

思ったよりも多いですね。次回は勝敗が決した時点で終了する場合の全譜面を調べます。