LeetCode 解答 #51. N-Queens プログラミング練習

問題：

難易度:　hard
入力:　int n
目的: n Queensの条件を満たすすべての回答をListとして返せ
出力: List>

Lineの面接試験問題でも出題されたと噂されてる有名な問題ですね。
nQueensの条件は以下の通りです:
n*nの盤面があります。（入力のｎです）
n個のQueenの駒を盤面に置き、縦、横、斜めすべての方向に違う駒がない盤面を求める問題です。
Chess上でqueenは縦横斜めに移動が出来るので、
すべてのqueenが安全な盤面を求めるのですね。←チェスやった事ないｗ
例題を見ればわかるのですが、盤面をn*nの行列で表し、何もない所を"."　、Queenを”Q"で表します。
条件を満たす盤面を表した行列すべてを一つのリストに纏めてreturnすれば正解です。

注意すべき事:　

• 重複した答えを含んではならない

• pは小文字の'a-z'と'*'と'?'を含む

以下回答です。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[][] array = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                array[i][j] = 0;
            }
        }
        queens(array, res, 0, 0);
        return res;
    }
    
    public boolean queens(int[][] array, List<List<String>> res, int m, int n) {
        if (m >= array.length) return false;
        for (int j=n; j<array.length; j++) {
            array[m][j] = 1;
            if (!check(array, res, m, j)) {
                array[m][j] = 0;
                continue;
            }
            else queens(array, res, m+1, 0);
            array[m][j] = 0;
        }
        return true;
    }
    
    public boolean check(int[][] array, List<List<String>> res, int m, int n) {
        //printArray(array);
        for (int i=0; i<array.length; i++) {
            if (i != m && array[i][n] == 1) return false;
        }
        for (int i=0; i<array.length; i++) {
            if (i != n && array[m][i] == 1) return false;
        }
        int i=1;
        int j=-1;
        while (i + m < array.length && j + n >= 0) {
            if (array[i+m][j+n] == 1) return false;
            i++;
            j--;
        }
        i=-1;
        j=1;
        while (i + m >= 0 && j + n < array.length) {
            if (array[i+m][j+n] == 1) return false;
            i--;
            j++;
        }
        i = -1;
        j = -1;
        while (i + m >= 0 && j + n >= 0) {
            if (array[i+m][j+n] == 1) return false;
            i--;
            j--;
        }
        if (m == array.length - 1) {
            List<String> temp = new ArrayList<>();
            for (i=0; i<array.length; i++) {
                StringBuilder sb = new StringBuilder();
                for (j=0; j<array.length; j++) {
                    if (array[i][j] == 0) sb.insert(j, ".");
                    else sb.insert(j, "Q");
                }
                temp.add(sb.toString());
            }
            res.add(temp);
        }
        return true;
    }

DFSを使った探索方法の回答です。
まず入力nを用いて盤面を初期化します。私は0に初期化しましたが得に意味はありません。
初期化出来たらqueensと言うrecursive関数の中に飛ばします。
一行一行進んでいき、駒を置く度に盤面をcheckと言う関数で有効かどうかを判断します。
判断方法は上で紹介した通り、縦横斜めの方向に他の駒がないかを判断するものです。
有効なら次の行へ、無効なら次の列へと進みます。
条件を満た盤面を見つけたらListへ記録しこれを繰り返します。

今日は以上。
よいプログラミング生活を！