[leetcode-51]N-Queens(java)

質問説明:The n-queens puzzle is the problem of placing n queens on an×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.
For example, There exist two distinct solutions to the 4-queens puzzle:
[ [“.Q..”,//Solution 1 “…Q”, “Q…”, “..Q.”],
[“..Q.”,//Solution 2 “Q…”, “…Q”, “.Q..”] ]
分析:この問題は典型的な遡及法(再帰+剪定)で、最初の行から下へ、最後の行まで、すべて見つかったら、処理してresに追加します.ここで、私のtmpListはcol値を保存しています.比較(同じ行、同じ列、または同じ斜行)を容易にするためです.
コードは次のとおりです:288 ms

public class Solution {
     public List> solveNQueens(int n) {
        List> res = new LinkedList<>();
        List tmpList = new LinkedList<>();//store col

        solve(n,0,res,tmpList);
        return res;
    }
    private void solve(int n,int index,List> res,List tmpList){
        if(n==index){
            List tmpStrList = new LinkedList<>();
            for(int i = 0;iint col = tmpList.get(i);
                StringBuffer sb = new StringBuffer();
                for(int j = 0;jif(j==col)
                        sb.append('Q');
                    else
                        sb.append('.');
                }
                tmpStrList.add(sb.toString());
            }
            res.add(tmpStrList);
            return;
        }
        //     O(N2)    ，      ，，
        for(int col = 0;colint row = index;
            int rowList;
            for(rowList = 0;rowListint rowrow = rowList;
                int colcol = tmpList.get(rowrow);
                //   
                if(col == colcol)
                    break;
                //    
                if(Math.abs(rowrow-row)==Math.abs(colcol-col))
                    break;
            }
           if(rowList==tmpList.size()) {
               tmpList.add(col);
               solve(n, index + 1, res, tmpList);
               tmpList.remove(tmpList.size()-1);
           }
        }
    }
}