[Leet Code] N Queens II

こんにちは!今日、5月5週目に最初のアルゴリズムN Queens IIプールを作成します.)

質問する

サマリn x nのシナリオでは、nの皇后を攻撃不可能な位置に置くことができるすべてのシナリオの数を見つけて返します.

初志

実は、最初は皇后がどうしたのか分からなかったので、探してみました.
上下左右の対角線はずっと空いています
そこで、最初にn x n配列を作成し、最初の行にQueenを配置し、dfsでQueenの位置を見つけました.
解けましたが、コードが複雑すぎて、実は私もよく理解していないので、答えを探し始めました.

その他の分コードを参照

アルゴリズムを位置決めするとき、初めて他人のコードを参考にしますが、よくあるタイプなので、効率的なコードを参考にしたいです.n x nアレイではなく、nアレイが最初に使用される.
配列内のindexは行を表し、indexに格納された値は列を表す.
例えば、array[1] = 3であれば、皇后は第1行の第3列に位置する.
別のインデックスにローのインデックス値が格納されている場合、クイーンの位置チェックはローのインデックス値が同じローにあることを確認します.
対角線チェックは、現在の行と前の行の差が現在の行の列値と前の列の差に等しい場合、対角線上にあることを示します.

コードの説明

int result = 0;

クラスのグローバル変数としてresultを宣言します.

private void placeQueens(int[] array, int row, int n) {
    if (row == n) {
        result++;
        return;
    }
    for (int i = 0; i < n; i++) {
        array[row] = i;
        if (checkValidation(array, row)) {
            placeQueens(array, row + 1, n);
        }
    }
}

解放後のプロセス関数placeQueens.rowがnであれば、すべての皇后が釈放されます.したがって、resultに値を追加し、返します.
すべての皇后が釈放されなければ、forドアを巡視して再び呼びます.rowの値をiに設定し、アレイを検証します.皇后の位置検査ですね?trueの結果があれば、リペアコールを行います.

private boolean checkValidation(int[] array, int row) {
    for (int i = 0; i < row; i++) {
        if (array[i] == array[row] || row - i == Math.abs(array[i] - array[row])) {
            return false;
        }
    }
    return true;
}

皇后位置検査を行うcheckValidation関数.array[i] == array[row]は、Queenが同じ列にあるかどうかを確認するための関数です.
同じ行をチェックしません.これは、インデックス自体がローであるため、重複チェックは意味がありません.row - i == Math.abs(array[i] - array[row])は、対角線にあるかどうかを確認します.
前の行に格納された値が現在の行に格納されている値と異なる場合、対角線に配置されます.

完全なコード

class SolutionNQueens {
    int result = 0;

    // 0: 비어있음 1: 퀸 있음 -1: 퀸 못놓음
    public int totalNQueens(int n) {
        placeQueens(new int[n], 0, n);
        return result;
    }

    private void placeQueens(int[] array, int row, int n) {
        if (row == n) {
            result++;
            return;
        }
        for (int i = 0; i < n; i++) {
            array[row] = i;
            if (checkValidation(array, row)) {
                placeQueens(array, row + 1, n);
            }
        }
    }

    private boolean checkValidation(int[] array, int row) {
        for (int i = 0; i < row; i++) {
            if (array[i] == array[row] || row - i == Math.abs(array[i] - array[row])) {
                return false;
            }
        }
        return true;
    }
}

の最後の部分

初めて思いついた2次元配列で行った方が多かったのを覚えています
しかし,Let Codeでは,時間的重なりが生じる可能性があり,一次元配列と呼ばれる方法が見つかった.
効率的なコードを見つけてよかったと思います.ほほほ.ほほほ
今回のポスターを読んでくださってありがとうございます.