地図を4色で塗るゲーム：隣と同じ色にしない

「4色で足りる」と「気ままに塗って足りる」は別の話

平面の地図は隣り合う領域が別の色になるよう4色で塗り分けられる、という内容は四色定理として知られています。コンピュータを使った証明が行われたことでも有名です。

ただしこれは「塗り方がどこかに存在する」という主張です。順番を決めずに塗り進めても必ずうまくいく、とは言っていません。序盤の選び方によっては、後半で4色目の逃げ道がなくなることがあります。ゲームで問題になるのはこちらです。

プレイヤーの塗り方が2通りあると考えてみます。

• 先読みして塗る人は、詰みを避けられます。
• 目についた領域から思いつきで塗る人は、詰みに当たる可能性があります。

後者の頻度が高いと、プレイヤーは「自分の失敗」ではなく「地図の意地悪」と感じやすくなります。逆に頻度が低すぎると、4色という制約がほとんど意味を持たず、考える余地のないぬり絵になります。実験で測りたいのは、この中間のどこに自分の地図があるかです。

領域を「タイルの遊び」に変える

地図を描くより、マス目のタイルで領域を作るほうが、判定もルール変更も簡単になります。この実験では次の約束を置きます。

1. 盤面は縦横が決まった格子（たとえば12×12マス）にします。
2. 格子の上にランダムに「種」の点を置き、各マスを最も近い種の領域に属させます。種が14個なら、最大14個の領域ができます。
3. 隣接は「マスの辺が接している」場合だけとし、角だけが触れ合う場合は隣とみなしません。
4. プレイヤーの塗りは、「その領域に隣接する領域に使われていない色の中から1色を選ぶ」操作とします。

3番目は、ゲームのルールとして決めておくべき点です。角で接する領域まで隣とみなすと、1点で4領域が集まる箇所が増え、色数が足りなくなりやすくなります。この記事の実験では辺の接触だけを使いますが、角を含めるかどうかは別の条件として比べる価値があります。

4番目の「合法な色から選ぶ」は、プレイヤーがルール違反の色を選べない画面を想定しています。その上で、実際の人間の判断を、ここでは合法な色からのランダム選択で置き換えます。人間より雑な塗り方なので、詰みの頻度としては多めに出る、という見込みで読みます。

手順：詰みの回数を数える最小のプログラム

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

<!doctype html><meta charset="utf-8">
<pre id="out"></pre>
<script>
const W=12,H=12,N=14,K=4,TRIALS=1000;
function make(){
  const s=Array.from({length:N},()=>[Math.random()*W,Math.random()*H]);
  return Array.from({length:H},(_,y)=>Array.from({length:W},(_,x)=>{
    let b=0,bd=1e9;
    s.forEach((p,i)=>{const d=(p[0]-x)**2+(p[1]-y)**2;if(d<bd){bd=d;b=i;}});
    return b;}));
}
function graph(g){
  const adj=Array.from({length:N},()=>new Set());
  for(let y=0;y<H;y++)for(let x=0;x<W;x++)
    for(const [dx,dy] of [[1,0],[0,1]]){
      const a=g[y][x],b=g[y+dy]?.[x+dx];
      if(b!==undefined&&a!==b){adj[a].add(b);adj[b].add(a);}
    }
  return adj;
}
function play(adj){
  const order=[...adj.keys()];
  for(let i=order.length-1;i>0;i--){const j=Math.floor(Math.random()*(i+1));[order[i],order[j]]=[order[j],order[i]];}
  const col=new Array(N).fill(-1);
  for(const v of order){
    const ok=[];
    for(let c=0;c<K;c++)if(![...adj[v]].some(u=>col[u]===c))ok.push(c);
    if(!ok.length)return false;
    col[v]=ok[Math.floor(Math.random()*ok.length)];
  }
  return true;
}
let stuck=0;
for(let t=0;t<TRIALS;t++)if(!play(graph(make())))stuck++;
document.getElementById("out").textContent=`K=${K} N=${N} 詰み ${stuck} / ${TRIALS}`;
</script>

make が地図を作り、graph が領域どうしの隣接関係を数え、play が気ままな塗りを1回再現します。play は、塗れる色が一つもない領域に当たった時点で「詰み」として false を返します。最後の2行が、1,000枚の地図で詰みが何枚あったかを表示します。

記録の取り方

数字は1回の実行だけで判断せず、同じ条件を複数回走らせて、ばらつきを確認します。記録は次のような表を手元に作ります。

• 基準、K：4、N：14、格子：12×12、実行1：、実行2：、実行3：
• 領域を増やす、K：4、N：24、格子：12×12、実行1：、実行2：、実行3：
• 色を増やす、K：5、N：14、格子：12×12、実行1：、実行2：、実行3：

変えるのは1回に1か所だけです。N を変えたら K は戻します。数字を入れる単位は「1,000枚中の詰み枚数」とし、3回の実行で差が大きければ、TRIALS を増やして揺れを小さくします。

より踏み込むなら、次の条件も増やせます。

• 格子を小さく（8×8）、または大きく（20×20）する。
• 隣接の判定に角の接触を加える。[[1,0],[0,1]] を [[1,0],[0,1],[1,1],[-1,1]] に変えると、斜めの接触も隣とみなします。ただし、斜め判定を足すときは g[y+dy]?.[x+dx] の x+dx が負になる場合の扱いも確認してください。
• 塗る順を完全なランダムではなく、隣接数の多い領域から先に塗る順に変える。

結果の読み方

出た数字は「詰みの割合」として読み、先に決めておいた基準と照らします。基準の例を挙げます。実際の閾値は、ゲームの難しさをどうしたいかで決めてください。

• 詰みがほぼ出ない場合： 4色では余裕があり、塗り分けにほとんど緊張感がありません。領域数を増やす、角の接触を隣とみなす、といった条件で難しくできます。
• 詰みが時々出る場合： 「うっかり塗ると行き詰まる」緊張感が生まれる範囲かもしれません。この場合は一手戻す機能や、詰んだ領域を示す演出を付けると、失敗が学びに変わります。
• 詰みが頻繁に出る場合： 気ままな塗り方では最後まで進めない地図です。色数を5にする、塗れない領域が出たら警告する、といった調整を考えます。

K=4 と K=5 の差も有用な手がかりです。色を1色足したとき詰みが大きく減るなら、4色目と5色目の間にゲームの難易度を調整する余地があります。差が小さいなら、詰みの原因は色数ではなく、地図の形（領域が密集している箇所）にある可能性があります。

もう一つ、プレイヤーの実際の振る舞いがランダムより賢いか雑かは、このコードでは測れません。数字はあくまで「雑に塗った場合の目安」です。実際の判断は、友人に遊んでもらい、どの領域で手が止まったかを観察して補ってください。

誤りやすい点

実験の数字を読み違えやすい箇所を挙げます。

1. 領域の数が N と一致するとは限りません。 種の近くにマスが一つも割り当てられない場合があり、その領域は空になります。空の領域は隣接がなく、詰みにも関わりません。実際の領域数は、盤面を描画して数えてください。
2. 領域が分断されることがあります。 格子上の最近傍の割り当てでは、まれに同じ領域のマスが離れた場所に分かれます。飛び地のある領域を一つの頂点として扱うと、四色定理が想定する地図から外れ、4色で塗り分けられない地図が混ざる可能性があります。気になる場合は、連結成分ごとに別の領域として扱う改造を試してください。
3. 「詰み」と「塗り分け不可能」は違います。 この実験の詰みは「その塗り順では行き詰まった」という意味にすぎません。別の順なら最後まで塗れた地図も含まれます。
4. 乱数の偏りに注意してください。 順番のシャッフルに sort(() => Math.random() - 0.5) を使うと、並びが均等になりません。コードのように、一つずつ入れ替える方法を使ってください。
5. ブラウザの再読み込みで数字が変わるのは正常です。 固定したい場合は、乱数の種を指定できる自作の乱数関数に差し替えます。

次の行動

まず基準の条件を3回走らせ、詰みの枚数を表に記入してください。次に K を5に変えて差を見て、ゲームに入れたい緊張感の水準を決めます。その水準に合わせて、領域数か色数を調整してください。

調整した地図を画面に描き、タップで色を塗れるようにすれば、一つのHTMLファイルとしてアソバースに投稿できます。その際は、直下の index.html を入口にし、素材は相対パスで指定してください。