次の問題を考えてみてください．
「正方形の中に，半径$r$の円を互いに重ならないようにできるだけ効率よく詰め込む．
$r$の値を自由に設定できる場合，$r$が最大となる円を1個だけ入れた場合が最も高い充填率
（=円の面積の総和/正方形の面積）となる．」
これは○でしょうか，それとも×でしょうか．
×だと思う場合は，その反例となる最小の円の個数も考えてみてください．
この記事では，正方形に対する円の詰込み問題を解説します．
冒頭の問題の答えも，後ほど明らかにします．
前提
正方形に対する円の詰込み問題 (Circle packing in a square) は，最適化問題の1種です．
円が多い場合，最適な円の大きさとその詰め込み方は，証明されていません．
Wikipediaの説明では，円の大きさを固定した場合の最小の正方形を考えていますが，
この記事では，面積1の正方形に対して円を詰め込むことを考えます．
円の個数n=1,2,3個の場合
まずは，円の個数$n=1$個の場合を考えます．
この場合，半径$r=0.5$の円が正方形にぴったり納まります．
円の中心座標は$(0.5, 0.5)$で，その面積$A＝\pi r^2=\pi/4\approx0.78539816$です．
これが基準になります．
次に，$n=2$の場合，少し考えると正方形の対角線上に円の中心を置くと良いことに気が付きます．
計算・証明は省略しますが，半径$r=1-\sqrt{2}/2$の円が最適解で，円の合計面積$A\approx0.53901208$です．
実はこの$n=2$の場合が，最も効率の悪い円の詰込み（$=A$の最小ケース）となります．
同様に$n=3$の場合，半径$r\approx0.25433310$，円の合計面積$A\approx0.60964481$です．
図にすると，以下のようになります．
 |
 |
 |
|---|---|---|
| $n=1,~A\approx0.78539816$ | $n=2,~A\approx0.53901208$ | $n=3,~A\approx0.60964481$ |
円の個数n=4~9個の場合
次は，円の個数$n=4\sim9$個の場合です．
考えるより図・表を見る方が早いでしょう．結果は，以下になります．
 |
 |
 |
|---|---|---|
| $n=4,~A\approx0.78539816$ | $n=5,~A\approx0.67376511$ | $n=6,~A\approx0.66395691$ |
 |
 |
 |
| $n=7,~A\approx66931083$ | $n=8,~A\approx0.73096383$ | $n=9,~A\approx0.78539816$ |
$n=1,4,9$ すなわち $n=1^2,2^2,3^3$ の場合に面積$A=\pi/4$となり，
それ以外の場合は，面積$A$が$\pi/4$より小さい値となっています．
では，冒頭の問題の答えは◌でしょうか？ MATLABプログラムで検証してみましょう．
MATLABプログラムによる解法
この問題は，近似解（$\neq$厳密解）であれば20行程度のプログラムで求められます．
具体的なMATLABプログラムを以下に示します．
function CPS(n) % Circle packing in a square
lb = [zeros(1, 2*n) 0]; ub = [ones(1, 2*n) 0.5];
options = optimoptions('fmincon', 'Display', 'none', ...
'Algorithm', 'sqp', 'MaxFunctionEvaluations', 1e6);
r = -inf;
for i = 1:200
x0 = [rand(1, 2*n) 0.1];
x = fmincon(@(x) -x(end), x0, [], [], [], [], ...
lb, ub, @(x) constraints(x), options);
r = max(r, x(end));
end
fprintf('n=%d, A=%.8f\n', n*pi*r^2);
end
function [c, ceq] = constraints(x)
X = reshape(x(1:end-1), 2, [])';
r = x(end);
c = [(2*r-pdist(X))'; r-X(:); X(:)+r-1];
ceq = [];
end
このプログラムはMATLABの Optimization Toolbox， fmincon関数 を利用しています．
$n$個の円の中心座標$(x,y)$と円の共通半径$r$を変数として，$r$の最大化問題を解いています．
各円が重なり合っていないこと，円が正方形の外に出ていないこと という制約条件は，
制約違反量$c$として実装しています．
特に$n$が大きい場合に良い結果を得られないことがあったため，200試行の最良値を出力しています．
$n$の値を変えてプログラムを実際に動かしてみてください．興味深い結果を確認できます．
円の個数n=30,49個の場合
この記事では最後に，円の個数$n=30,49$個の場合を取り上げます．
以下の3つの結果をご確認ください．
 |
 |
 |
|---|---|---|
| $n=30,~A\approx0.79201903$ | $n=49,~A\approx0.78539816$ | $n=49,~A\approx0.79068398$ |
$n=30$の時，その合計面積$A$は$n=1$の時より大きくなります．
つまり，この記事の冒頭の問題の答えは × で，その反例となる最小の円の個数は 30 です．
これは，4つの円の中心を頂点とする四角形を考えると，理解がしやすいです．
正方形ができるように円を並べたとき，その配置（正方格子）の充填率は$\pi/4\approx0.78539816$です．
一方，菱形ができるように円を並べたとき，その配置（六方格子）は最密充填となり，
充填率は$\sqrt{3}\pi/6\approx0.90689968$です．
図示すると，以下になります．
図の配置で円を敷き詰めたとき，その内部は図の正方形・菱形を敷き詰めた場合と同じ
と見做せます．
ここから，正方形に対する円の詰込み問題 (Circle packing in a square) では $n\rightarrow\infty$の時，$A^*=\sqrt{3}\pi/6\approx0.90689968$に収束することがわかります．（説明・証明は省略）
$n=49$については，2通りの結果を掲載しています．
円をきれいに縦横$7\times7$で敷き詰めた場合，その合計面積$A=\pi/4\approx0.78539816$です．
一方，掲載したMATLABプログラムを利用した場合，円はきれいに整列しません．
しかし，その合計面積$A\approx0.79068398$であり，円を縦横きれいに敷き詰めた場合より
大きい$A$が得られています．
この結果からも，円を縦横に整列させる方法が最善でないことが確認できます．
なお，wolframalphaで確認すると，$n=30$の場合は同じ結果ですが，$n=49$の場合は$r\approx0.0716927,~A\approx0.7912$というより良い結果が掲載されています．
$n$がこれくらい大きくなると，より良い結果を得るためにはアルゴリズムやパラメータに工夫が必要になります．
終わりに
この記事では，正方形に対する円の詰込み問題 (Circle packing in a square) を紹介しました．
$n=30$で初めて$n=1$の場合より大きい充填率になるなんて，驚きですよね．
また，僅か20行のプログラムで近似解が得られることに驚いた方もいるかもしれません．
これは，数値計算に強いMATLABだからできることだと思います．
この記事に関連するプログラムは，GitHubで公開しています．
可視化コードや$n=1\sim30$の結果も公開内容に含まれます．
また，円に円を詰め込むプログラムも公開しています．
良ければ以下もご確認ください．