問題のあらすじはある座標にクイーンがいる場合、座標を中心とした「米」線では新たなクイーンを置くことができない、つまり攻撃されるという制限がある。この制限ルールにしたがってNxNのチェスボードにN名のクイーンが置ける解き方を見つけ出しなさい。
本文: 51問題リンク
適切な組み合わせを見出すためには後戻り法を使って、行ごとで全ての列と組み合わせた座標を検証し、適切な場合は次の行に移し(再帰呼び出し)、残りの行列の座標の組み合わせを検証すんだら、解き方をリストに入れておき、かけた制限を消し、現在の行の次の列に順番を回す。
実は一番難しいところは斜線(／＼)の座標がどんな行列関係を持っているのかを理解出来れば、コードにするには余り難しくないだろう。
行＋列=定数
行-列=定数
NQueens
public class NQueens {
// このクラスで使われている配列やリストは複数のメソッドの間で
// 共有される必要があるため、彼らをグローバル（広域）変数にしておく。
// 攻撃制限条件(要素が1の場合、攻撃されている)： 一列を一つの要素として、
// n個要素を納める配列 「rows[列目]」。
int rows[];
// 攻撃制限条件(要素が1の場合、攻撃されている)： 北西から南東まで("＼")
// 水平と45度で引いた線を一つの要素としてトータル(2n-1)個を納める配列。
// 線のパターン： 行の添え字-列の添え字(row-col)は同じ、-(n-1)から(n-1)まで
// トータル(2n-1)本線(要素)がある。
int hills[];
// 攻撃制限条件(要素が1の場合、攻撃されている)： 北東から南西まで("／")
// 水平と45度で引いた線を一つの要素としてトータル(2n-1)個を納める配列。
// 線のパターン： 行の添え字 + 列の添え字(row + col)は同じ、0から(2n-2)まで
// トータル(2n-1)本線(要素)がある。
int dales[];
// 置きたいクイーンの数(N)。
int n;
// 条件に満たされた解き方のリスト
List<List<String>> output = new ArrayList<>();
// クイーンの座標、行を添え字とし列を値としn個要素を納める配列
int queens[];
//0
public static void main(String[] args) {
// 二次元リスト、複数の解き方に備える。引数n＝4を渡し、検証開始。
List<List<String>> listList = new NQueens().solveNQueens(4);
// 結果をプリントする。
System.out.println(listList);
}
//1
public List<List<String>> solveNQueens(int n) {
this.n = n; // nが4の場合、配列の要素の数
rows = new int[n]; // 4 {0,0,0,0}
hills = new int[2 * n - 1]; // 7
dales = new int[2 * n - 1]; // 7
queens = new int[n]; // 4 {0,0,0,0}
// 走査開始
backtrack(0);
// 走査結果を戻す
return output;
}
//2
// 行ごとで中に入れられる座標を見つけたら、クイーンをおいておき、
// 「米」字に関する制限配列の要素を1(埋まっている)にしておき、
// 次の行に移す、残りの行列を完走したら、現在の行の次の列に移す前に
// 先入れた適切な座標による「米」字制限配列要素を消し(0にする)
// この行の全部の列を一通り完走する。
// 最初、または一つ上の行に適切な座標が見つかった場合、
// このメソッドを呼び出し、列を順番に検証する。
public void backtrack(int row) { 。
for (int col = 0; col < n; col++) { // 列の検証
// この位置にクイーンを入れられかどうか、まず同じ列や左上--右下や
// 右上--左下に埋まっているかどうかをチェック。
// 座標が空いてる場合(攻撃されていない)、if文に回す。
// つまりこの位置は一応適切。
if (isNotUnderAttack(row, col)) {
// クイーンをこの座標に置き、攻撃制限をかける。
placeQueen(row, col);
// もし全ての行にクイーンさまがお臨みになった場合は、
// 一つの解き方が見つけた。
if (row + 1 == n) {
// アウトプット用の二次元リストにこのリストを入れる。
addSolution();
// そうじゃない場合は次の行に移す。
}else {
backtrack(row + 1);
}
// 残りの行列の検証を完了したら、現在の行に戻り。
// 一応現在の行の適切な座標によるつくって置いた攻撃制限を消し、
// 同じ行の次の列に移す。
removeQueen(row, col);
}
}
}
//3
// 攻撃されていないかどうか判断する。resが0の場合はtrue、
// 1以上の場合はfalse(攻撃されている)。
public boolean isNotUnderAttack(int row, int col) {
// row[]配列は全ての行の同じ列を一つの要素として代入している。
// (2n-1)本線に応じてhillsに(2n-1)個要素があり、
// もし添え字で要素が1(クイーンが埋まっている場合)だとこの線はアウト。
// (n-1)をたすのはhills配列の添え字が0から始めるにあわせて調節している。
int res = rows[col] + hills[row - col + n - 1] + dales[row + col];
return (res == 0) ? true : false;
}
//4
// 座標にクイーンが埋まったら、「米」字に攻撃制限に関する配列の要素を1にしておく。
public void placeQueen(int row, int col) {
// queens[行] = 列
queens[row] = col;
// 列の制限をかける。
rows[col] = 1;
// 北西から南東まで線の制限をかける。
hills[row - col + n - 1] = 1;
// 北東から南西まで線の制限をかける。
dales[row + col] = 1;
}
//5
// 一つの置き方を見つけたら、outputリストに入れておく。
public void addSolution() {
List<String> solution = new ArrayList<>();
// 一行で一つの「Q」(クイーン)と(n-1)「.」を
// 使って一つの要素を生成し、リストに入れる。
// iはクイーン座標を含めるリストの行の番号、 列 = queens[行]。
for (int i = 0; i < n; ++i) {
// colは行にクイーンがいる列の添え字。
// 例えばnが4で場合, 一つの解き方のqueens配列の値(列)は{1,3,0,2}
int col = queens[i];
StringBuilder sb = new StringBuilder();
// Qの前に「.」を埋めていく。
for(int j = 0; j < col; ++j) sb.append(".");
// Qを置く
sb.append("Q");
// 行に残った位置に「.」を埋める。
for(int j = 0; j < n - col - 1; ++j) sb.append(".");
// 一行を作り上げたので、リストに入れる。for文は次の行の処理を始める。
// nが4の場合。一番目の解き方の入れる順番：一回目[.Q..], 二回目[...Q],
// 三回目[Q...], 四回目[..Q.]。
solution.add(sb.toString());
}
// 一つの解き方リストをoutput二次元リストに入れる。
output.add(solution);
}
//6
public void removeQueen(int row, int col) {
// 判定用の四つの配列に要素の1(埋まっている)を0にする。
queens[row] = 0;
rows[col] = 0;
// (n-1)をたすのはhills配列の添え字が0から始めるにあわせて調節している。
hills[row - col + n - 1] = 0;
dales[row + col] = 0;
}
}