円を四角で埋めるパズル：ぴったり収まる組み合わせ

「ぴったり」を決める：円盤をセルの集合にする

円を次のように定義します。方眼の中心を原点にして、各セルの中心が円の内側か円周上にあれば、そのセルは円盤の一部とします。半径をrとすると、セル中心の座標を(a, b)として、a²+b²がr²以下であれば円盤のセルです。

この定義で、小さな半径を机上で数えてみます。

• 半径1：中心座標は(±0.5, ±0.5)の4か所で、距離の2乗は0.5です。1以下なので4セルすべてが入ります。
• 半径2：中心座標は±0.5と±1.5の組み合わせです。距離の2乗は、(0.5, 0.5)が0.5、(0.5, 1.5)が2.5、(1.5, 1.5)が4.5になります。4以下のものだけが残るので、4×4の角の4セルが外れ、12セルになります。
• 半径3：座標は±0.5、±1.5、±2.5です。(2.5, 2.5)だけが12.5で9を超えるため、6×6の角の4セルが外れ、32セルになります。

半径3の32セルが円の面積π×9（約28.3）より大きいことに気づいたでしょうか。セル中心で判定する方式は、面積とぴったりは一致しません。「円盤」の大きさはセル数で決まるものと割り切り、以降はこのセル数を基準にします。

数は合うのに置けない例を、紙の上で確かめる

半径2の12セルを、2×2の正方形3枚で埋められるかを考えてみます。面積は4×3=12で、セル数と一致します。

行を上から1〜4、列を左から1〜4とします。円盤は、行1と行4が列2・3の2セルずつ、行2と行3が列1〜4の4セルずつです。

まず、行2・列1のセルに注目します。このセルを覆う2×2は、行1〜2か行2〜3のどちらかで、列は1〜2になります。行1・列1は円盤の外なので、行1〜2は使えません。したがって行2〜3・列1〜2に置くしかありません。右側も同じ理由で、行2〜3・列3〜4に置くしかありません。

この2枚を置くと、残りは行1の列2・3と、行4の列2・3です。この2セルずつは横に細長く、離れているため、2×2を置く余地がありません。したがって、2×2を3枚という組み合わせは、面積が合っていても敷き詰められません。

一方、2×2を2枚と1×1を4枚の組み合わせは置けます。上に1枚、下に1枚の2×2を並べ、左右の縦2セルを1×1で埋めれば、12セルちょうどになります。

面積が合うことは、敷き詰められるための必要条件にすぎません。この実験は、その差がどの程度あるかを調べるものです。

準備と手順：組み合わせを列挙して、置けるかを機械で判定する

次の問いを立てます。「半径rの円盤について、面積が合う正方形の組み合わせのうち、実際に敷き詰められるものは何割か」。ここでの組み合わせは、使う正方形の辺の長さの集まり（多重集合）のことです。たとえば2、2、1、1、1、1が一つの組み合わせです。

準備するものは、ブラウザとテキストエディタだけです。次のコードをindex.htmlとして保存し、ブラウザで開きます。外部ライブラリは使いません。

<!doctype html>
<meta charset="utf-8">
<pre id="out"></pre>
<script>
const R = 3;   // 半径。まず1〜4で
const K = 99;  // ピース数の上限（重いときは小さく）
function disk(r){
  const s = new Set();
  for (let y=-r; y<r; y++) for (let x=-r; x<r; x++){
    const a=x+0.5, b=y+0.5;
    if (a*a+b*b <= r*r) s.add(x+","+y);
  }
  return s;
}
function combos(n, from, cur=[], out=[]){
  if (n===0){ out.push([...cur]); return out; }
  for (let s=Math.min(from, Math.floor(Math.sqrt(n))); s>=1; s--){
    cur.push(s); combos(n-s*s, s, cur, out); cur.pop();
  }
  return out;
}
function solve(cells, sizes){
  const order=[...cells].map(k=>k.split(",").map(Number))
    .sort((p,q)=>p[1]-q[1]||p[0]-q[0]);
  const used=new Set(), left=[...sizes];
  const each=(x,y,n,f)=>{for(let j=0;j<n;j++)for(let i=0;i<n;i++)f((x+i)+","+(y+j));};
  const can=(x,y,n)=>{let ok=true;
    each(x,y,n,k=>{if(!cells.has(k)||used.has(k))ok=false;});return ok;};
  function go(){
    const p=order.find(([x,y])=>!used.has(x+","+y));
    if(!p) return left.length===0;
    for(let t=0;t<left.length;t++){
      if(t>0&&left[t]===left[t-1]) continue;
      const n=left[t];
      if(!can(p[0],p[1],n)) continue;
      left.splice(t,1); each(p[0],p[1],n,k=>used.add(k));
      if(go()) return true;
      each(p[0],p[1],n,k=>used.delete(k)); left.splice(t,0,n);
    }
    return false;
  }
  return go();
}
const cells=disk(R);
const list=combos(cells.size,2*R).filter(c=>c.length<=K);
const rows=list.map(c=>c.join("+")+" : "+(solve(cells,[...c].sort((a,b)=>a-b))?"OK":"NG"));
out.textContent="r="+R+" セル数="+cells.size+" 組み合わせ="+list.length+
  " OK="+rows.filter(s=>s.endsWith("OK")).length+"\n"+rows.join("\n");
</script>

判定の考え方は単純です。未使用のセルのうち、最も上で最も左にあるものを探します。そのセルは、どれかの正方形の左上の角になるはずです。そこで、手持ちのピースを一種類ずつ試して置き、置けたら次の空きセルへ進みます。行き止まりになったら一つ戻ります。小さな盤なら、これで十分に答えが出ます。

実行の手順は次のとおりです。

1. Rを1にして実行し、表示されるセル数が4であることを確かめます。次に2で12、3で32になることを確かめます。ここが合わなければ、座標の取り方か不等号を見直します。
2. R=2で、2+2+2がNGと表示され、2+2+1+1+1+1がOKと表示されることを確かめます。前節の机上の論証と、機械の判定が一致するかの確認です。
3. Rを3、4と上げながら、各半径の組み合わせ数とOK数を記録します。

半径を大きくすると、1×1を多く含む組み合わせが急に増えて重くなります。半径5以上に進むときは、Kでピース数に上限をつけます。

記録の取り方と、結果の読み方

記録は半径ごとに1行で、次の表の形にまとめます。数値は各自が実行して入れます。

• 1、セル数：4、面積が合う組み合わせ数：、敷き詰め可能な数：、可能な割合：
• 2、セル数：12、面積が合う組み合わせ数：、敷き詰め可能な数：、可能な割合：
• 3、セル数：32、面積が合う組み合わせ数：、敷き詰め可能な数：、可能な割合：
• 4、セル数：、面積が合う組み合わせ数：、敷き詰め可能な数：、可能な割合：

セル数の列は、半径1〜3は先ほどの数え方で確認済みです。半径4以降は実行結果を書き入れます。実行は半径ごとに1回で十分です。この判定には乱数が入っておらず、同じ入力なら同じ結果になるからです。

表に加えて、NGになった組み合わせを書き出して眺めます。見る観点は次の三つです。

• 最大の辺で分ける：NGの組み合わせは、最大の辺が大きいものに偏っているか、偏っていないかを集計します。偏りがあれば、大きなピースが円盤の細い縁に引っかかることが原因と読めます。
• 1×1の枚数で分ける：1×1が何枚以上あればOKが増えるかを調べます。1×1は小さなすき間を埋める調整役なので、必要な枚数の目安が見えてきます。
• 半径で比べる：可能な割合が、半径を上げると増えるのか、減るのか、増減が混じるのかを見ます。ただし半径は数点しか取れないので、傾向と言い切るのは避け、「この範囲では」と限定して読みます。

判断の基準は三つです。NGがほぼ出なければ、このパズルは数を合わせるだけで解けるので、パズルとしては弱くなります。NGが多すぎると、プレイヤーは理由が分からないまま行き詰まります。割合が中間で、NGの理由を盤面から説明できる組み合わせが複数あれば、ゲームの素材として使えます。

誤りやすい点

この実験でつまずきやすい点を挙げます。

• 判定方式の混同：「セル中心が円の内側」と「セル全体が円の内側」は別物です。後者にすると、半径2のセル数は12より減ります。途中で方式を変えないでください。
• 境界の扱い：<=を<に変えると、円周上にセル中心が乗る場合の扱いが変わります。この記事の数え方は「円周上は内側」です。
• 座標の半セルずれ：セルの角を座標とするか、中心を座標とするかを混ぜると、盤が非対称になります。まず盤が左右上下対称になっているかを確かめます。
• 重複の数え方：同じ辺の正方形を区別せず、辺の長さの多重集合で数えています。ピースに名前をつけて区別すると、組み合わせ数の意味が変わります。
• 配置の数との混同：この実験が数えるのは、置けるか否かの組み合わせです。置き方が何通りあるかは数えていません。置き方の数を知りたければ、goがtrueを返した後も探索を続ける改造が必要です。
• 回転や鏡映：円盤は回転しても同じ形ですが、この実験は配置を数えないので、影響しません。配置を数える改造をするときは、同一視するかを先に決めます。

遊びにする：この結果をパズルの設計に使う

実験で得られる表は、そのままパズルの出題表になります。たとえば次のような作りが考えられます。

1. 箱から選ぶ型：ピースの箱を見せて、「円盤をぴったり埋められる選び方」を探させます。箱の中の面積合計は、あえて円盤のセル数より多くします。数合わせだけで選ぶと詰まる設計にできます。
2. 罠を仕込む型：NGと判定された組み合わせを、一つだけ箱に混ぜます。「面積は合うのに置けない」ことに気づいたとき、プレイヤーは数と形のずれを体験します。
3. ヒントの出し方：面積の合計と残りセル数を常に表示します。さらに「いま置いた結果、残りの部分に入れない大きさのピースがある」ことを知らせるだけで、行き詰まりの理由が伝わります。
4. 難易度の段階：半径1〜2を入門、半径3以上を本編として、実験で得られた「可能な割合」が低い半径を後半に回します。

投稿時には、直下にindex.htmlを置いたHTMLまたはZIPをアップロードします。素材は相対パスで参照します。判定のコードは外部通信が不要なので、そのまま収まります。

次の行動

まず上のコードを保存し、R=1からR=3まで実行して、セル数が4、12、32になるか確かめます。次にR=2で2+2+2がNGになるか確かめ、記録表を埋めます。そのうえで、NGの組み合わせのうち一つを選び、「なぜ置けないか」を一文で説明できるか試してみます。説明できる組み合わせが、パズルの最初の一問になります。