エイトクイーン

エイトクイーンの遊び方

• 8×8のチェス盤に8個のクイーンを、どの2個も互いに取られないように置くパズルです。クイーンはたて・よこ・ななめに何マスでも進めるので、同じ段・同じ列・同じななめの線に2個を置けません。
• マスを押すとクイーンを置き、クイーンを押すと外します。取り合っているクイーンは赤くなり、点線で結ばれます。
• 「取られるマス」をオンにすると、置いたクイーンが取れるマスに斜線が付きます。斜線の無いマスが安全です。
• 行き詰まったら「ヒント」。取り合っている2個、このままでは解けないときに外すクイーン、次に置くマスのどれかを教えます。
• 8×8の解は全部で92通り。見つけた解は「見つけた解」に保存され、一覧で見られます。4×4〜10×10の盤でも遊べます（大きさをNにした問題をNクイーン問題といいます）。
• 「今日の問題」は毎日みんな同じ問題です。白いクイーンがはじめから置いてあって動かせません。残りを置いて完成させます。答えはちょうど1つです。
• パソコンでは、矢印キーでマスを選び、Enter か Space で置く・外す、H でヒント、U か Ctrl+Z で元に戻せます。盤は保存されるので、続きから遊べます。

コツ

• どの段にも、どの列にも、クイーンはちょうど1個。「各段に1マスずつ選ぶ」と考えると進めやすくなります。
• 安全なマスがいちばん少ない段から埋めます。安全なマスが1つしか残っていない段は、そこに置くしかありません。
• 角はあまり使いません。92通りのうち、角のマスを使う解は16通りだけです。
• 安全なマスが無い段ができたら、最後に置いたクイーンを同じ段の次の安全なマスへ動かします。動かせる所が無ければ、さらに1つ前のクイーンへ戻ります（バックトラック）。

解は何通り？

* 回転したり裏返したりすると重なる解を1つと数えた数。8×8では、12通りのうち11通りは向きを変えた形が8つずつ、残りの1通りは半回転すると同じ形になるので4つで、11×8＋4＝92通りです。

8クイーン問題をコンピューターで解く（バックトラック）

コンピューターはバックトラックで解きます。1段目にクイーンを置き、次の段の安全なマスに置き、と1段ずつ進めます。安全なマスが無い段に来たら1つ前の段に戻り、そのクイーンを次の安全なマスへ動かします。全部の解を数える短い JavaScript の例です。

function solve(n, row = 0, cols = []) {
  if (row === n) return 1; // n 個置けた
  let count = 0;
  for (let c = 0; c < n; c++) {
    // 上の段のどのクイーンとも、同じ列・ななめでなければ置ける
    const safe = cols.every((pc, pr) => pc !== c && Math.abs(pc - c) !== row - pr);
    if (safe) count += solve(n, row + 1, [...cols, c]);
  }
  return count;
}
solve(8); // 92

エイトクイーンの由来

1848年にチェスの問題作家マックス・ベッツェル（Max Bezzel）が出した問題で、1850年にフランツ・ナウク（Franz Nauck）が初めて解を発表しました。ガウスなど多くの数学者も取り組みました。1972年にはダイクストラ（Edsger Dijkstra）が構造化プログラミングの例に使い、深さ優先のバックトラックの手順を示しました。