【Leetcode】:51.N-Queens問題in JAVA

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where  'Q'  and  '.'  both indicate a queen and an empty space respectively.
[  [".Q..",  //Solution 1   "...Q",   "Q...",   "..Q."],  ["..Q.",  //Solution 2   "Q...",   "...Q",   ".Q.."] ]
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
この問題の難易度はHardで,確かに工夫して作らなければならないが,依然として再帰的な考え方を採用して便利に解くことができる.
まずQの配置を表す簡便な方法が必要であり、1つのN長の配列がint[n]を解決することができ、例えばint[0]=1はQが1行目の2列目を表し、int[2]=3はQが3行目の4列目を表す.
表現を簡単にするには、カスタム関数が必要です.

private boolean isValid(int[] queenList, int row, int col)

関数は、指定された行列にQを配置できるかどうかを返します.ここでは、指定された行の上のQの配置が合法であることを前提としています.

import java.util.List;  
import java.util.ArrayList;  

public class Solution {
    public List> solveNQueens(int n) {
        List> res = new ArrayList>();
        int[] queenList = new int[n]; // i         row  ，Q  
        placeQueen(queenList, 0, n, res);//  0  Q
        return res;
    }
    private void placeQueen(int[] queenList, int row, int n, List> res) {
        //      ，     
        if (row == n) {
            ArrayList list = new ArrayList();
            for (int i = 0; i < n; i++) {
                String str = "";
                for (int col = 0; col < n; col++){
                    if(queenList[i] == col) {
                        str += "Q";
                    } else {
                        str += ".";
                    }
                }
                list.add(str);
            }
            res.add(list);
        }
        for (int col = 0; col < n; col++) {//     
            if (isValid(queenList, row, col)) { //       Q     
                queenList[row] = col;
                placeQueen(queenList, row + 1, n, res);
            }
        }
    }
    
    private boolean isValid(int[] queenList, int row, int col) {
        for (int i = 0; i < row; i++) {
            int pos = queenList[i];
            if (pos == col) { //     Q     
                return false;
            }
            if (pos + row - i == col) { //     Q      
                return false;
            }
            if (pos - row + i == col) { //     Q      
                return false;
            }
        }
        return true;
    }
}