Ｎクイーン問題の後戻り法解説

　問題のあらすじはある座標にクイーンがいる場合、座標を中心とした「米」線では新たなクイーンを置くことができない、つまり攻撃されるという制限がある。この制限ルールにしたがってNxNのチェスボードにN名のクイーンが置ける解き方を見つけ出しなさい。

本文: <a href="https://leetcode.com/problems/n-queens/description/">51問題リンク</a>

　適切な組み合わせを見出すためには後戻り法を使って、行ごとで全ての列と組み合わせた座標を検証し、適切な場合は次の行に移し(再帰呼び出し)、残りの行列の座標の組み合わせを検証すんだら、解き方をリストに入れておき、かけた制限を消し、現在の行の次の列に順番を回す。

　実は一番難しいところは斜線(／＼)の座標がどんな行列関係を持っているのかを理解出来れば、コードにするには余り難しくないだろう。

---
　　　　　　　　　　　　　行＋列=定数
 ![NQueen01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/521111d5-5b95-4155-884a-c4486017cc69.png)

　　　　　　　　　　　　 行-列=定数
            ![NQueen02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3589185/44a9c5bf-cfe7-4ee5-8b98-79456a51a5e2.png)

```Java: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;
    }
}
```