yura1685
共円回避とは？
今回の「共円回避」は，盤面上にいくつかの石が置かれているとき どの $4$ 点も同一円周上にないように 新たな石を配置するゲームです．また，本ゲームでは同一直線上にある $4$ 点も禁止します．そのような点が一意に存在していることが保証されているので，それを頑張って探してくださいというゲームです．
共円回避はこちらから遊べます．
|
|
|
|-|-|
生成アルゴリズム
盤面上の点の集合を $V$，現在置かれている石の集合を $S$ とします．また，\(C:=\{p\in V\setminus S\mid S\cup\{p\}\text{ に共円な4点が存在しない}\}\) を，現在の盤面に石を1つ追加しても条件を満たす点の集合とします．以降 $C$ を「候補集合」と呼びます．
基本方針
最初は $S=\varnothing$ とし，その後次の操作を繰り返します．
- 候補集合 $C$ から1点 $q$ をランダムに選ぶ．
- $q$ を石として追加し，$S\leftarrow S\cup{q},\ C\leftarrow C\setminus{q}$ とする．
- 残っている各候補 $p$ について，$p$ を追加したときに新しく共円な4点が生じるかを調べる．
- 共円が生じる候補 $p$ を $C$ から削除する．
-
$ C =1$ になれば生成を終了する．$ C =0$ になった場合は生成失敗として最初からやり直す．
高速化
現在の石の集合を $S$ とします．石 $p, q\in C\ (p\neq q)$ であって，$S\cup{p, q}$ が条件を満たさない（共円となる $4$ 点が存在する）場合を考えます．
$p,q\in C$ なので，$S\cup{p}$ と $S\cup{q}$ はどちらも条件を満たします．したがって，$S\cup{p,q}$ で新しく生じる共円な $4$ 点は必ず $p,q$ の両方を含みます．よって，その $4$ 点は $a,b\in S$ を用いて ${a,b,p,q}$ と書けます．
| したがって，$q$ を追加したあとに各候補 $p\in C$ に対し，$S$ から選ぶ $O( | S | ^3)$ 通りの点の組を調べて削除するのではなく，追加前の $S$ から $2$ 点 $a,b$ を選び，${p,q,a,b}$ が共円かどうかだけを調べれば十分です．この際の計算量は $O( | S | ^2)$ に削減できます． |
共円判定
4点 $A,B,C,D$ が共円かどうかは，浮動小数点で円の中心や半径を求めず，行列式を使って判定できます．$A=(x_0,y_0)$ を基準にし，他の3点との差を \(u_X=x_X-x_0,\quad v_X=y_X-y_0,\quad s_X=u_X^2+v_X^2\) とします．このとき，\(\begin{vmatrix}u_B&v_B&s_B\\u_C&v_C&s_C\\u_D&v_D&s_D\end{vmatrix}=0\) なら4点は同一円周上にあります．整数格子上ではすべて整数演算で計算できるため，誤差を考えなくて大丈夫です．なお，この行列式は4点がすべて一直線上にある場合にも $0$ になるため，一直線上の4点も同時に判定できます．
計算量
盤面を $N\times N$，最終的に置かれる石の個数を $m$ とします．候補点の数は高々 $N^2$ 個です．
石が $k$ 個置かれている段階で新しい石 $q$ を追加すると，各候補 $p$ について，既存の石から2点を選ぶ必要があります．組の数は $\binom{k}{2}=O(k^2)$ なので，1回の候補更新に必要な計算量は $O(N^2k^2)$ です．これを石が $m$ 個になるまで繰り返すため，1回の生成に必要な計算量は \(O\left(N^2\sum_{k=0}^{m-1}k^2\right)=O(N^2m^3)\) となります．
さらに，本ゲームでは各行には石を高々3個しか置けません．したがって常に $m\le 3N$ が成り立ちます．よって，1回の生成に必要な計算量は最悪でも \(O(N^2m^3)=O(N^5)\) です．
考察
生成される石の個数 $m$ や，生成が成功するまでの試行回数を理論的に求めるのは難しいので，実験して傾向を調べます．各 $N$ について成功例を $10000$ 個得るまで生成を繰り返し，石の個数 $m$，成功までの試行回数 $T$，成功するまでに行った共円判定の回数を記録しました．
| $N$ | $E[m]$ | $E[T]$ | 成功確率 $p_N$ | 平均共円判定回数 |
|---|---|---|---|---|
| 3 | 4.000 | 8.905 | 0.112 | 195 |
| 4 | 5.422 | 2.465 | 0.406 | 190 |
| 5 | 6.855 | 2.164 | 0.462 | 515 |
| 6 | 8.368 | 1.903 | 0.526 | 1,177 |
| 7 | 9.791 | 1.798 | 0.556 | 2,373 |
| 8 | 11.172 | 1.741 | 0.575 | 4,351 |
| 9 | 12.551 | 1.671 | 0.599 | 7,368 |
| 10 | 13.895 | 1.641 | 0.609 | 11,925 |
| 11 | 15.228 | 1.594 | 0.627 | 18,082 |
| 12 | 16.658 | 1.575 | 0.635 | 27,313 |
| 13 | 17.986 | 1.543 | 0.648 | 38,791 |
| 14 | 19.448 | 1.517 | 0.659 | 54,879 |
| 15 | 20.823 | 1.489 | 0.672 | 74,813 |
| 16 | 22.193 | 1.460 | 0.685 | 99,412 |
| 17 | 23.522 | 1.450 | 0.690 | 131,478 |
| 18 | 24.997 | 1.434 | 0.697 | 172,364 |
| 19 | 26.359 | 1.401 | 0.714 | 217,803 |
| 20 | 27.807 | 1.400 | 0.714 | 279,431 |
石の個数
$N=3,4,\ldots,20$ について $E[m]$ を一次式で近似すると，\(E[m]\simeq 1.389N-0.019\) となりました．今回調べた範囲では非常にきれいに直線上に乗っており，$E[m]$ は $N$ にほぼ比例しています．このことから，漸近的にも \(E[m]=\Theta(N)\) となることが予想されます．
また，理論上は $m\le3N$ ですが，実際にはその半分程度の石を置いた段階で候補が1点まで絞られていることが分かります．
成功までの試行回数
1回の生成が成功する確率を $p_N$ とすると，成功までの試行回数 $T$ は幾何分布に従うので，\(E[T]=\frac{1}{p_N}\) です．
$N=4$ では $E[T]\simeq2.47$ で，$N=20$ では $E[T]\simeq1.40$ まで小さくなっています．成功確率も $0.41$ 程度から $0.71$ 程度まで上がっており，少なくとも今回調べた範囲では，$N$ が大きくなっても生成が成功しにくくなるという傾向は見られません．
また，今回調べた範囲では $E[T]$ は定数程度に収まっています．このことから，漸近的にも \(E[T]=\Theta(1)\) となることが予想されます．なお，$N=3$ だけは他と比べてかなり成功率が低くなっています．
生成に必要な計算量
先ほど示したように，1回の生成に必要な計算量は最悪でも $O(N^5)$ です．成功までの試行回数を $T$ とすると，成功する盤面を1つ生成するまでの計算量は $O(TN^5)$ なので，その期待値は \(O(N^5E[T])\) となります．
今回の実験では $E[T]$ は定数程度に収まっているため，この傾向が大きな $N$ でも続くと仮定すれば，盤面を1つ生成するまでの期待計算量も $O(N^5)$ となります．
一方，実際にはすべての候補について常に $\binom{k}{2}$ 回の共円判定を行うわけではありません．共円な4点が見つかった時点でその候補についての判定を打ち切るうえ，石が増えるにつれて候補集合自体も小さくなっていきます．そのため，実際の共円判定回数は理論上界より少なくなります．
$N=4,\ldots,20$ における，成功するまでの平均共円判定回数を $cN^\alpha$ の形で近似すると，\(\alpha\simeq4.53\) となりました．したがって，今回調べた範囲では，共円判定回数はおよそ $N^{4.5}$ 程度の増え方をしています．ただし，これは有限の範囲における実験結果であり，漸近的な計算量が $\Theta(N^{4.53})$ であることを意味するものではありません．
以上の結果から，1回の生成に必要な計算量は理論上 $O(N^5)$ であり，実験では成功するまでの共円判定回数がおよそ $N^{4.5}$ に比例して増加することが分かりました．また，生成される石の個数は $N$ にほぼ比例し，成功までの試行回数は今回調べた範囲では定数程度に収まっています．