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.
For example, There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
最开始想到用dfs，其实dfs就是回溯，与这个题目点击打开链接类似，先看AC的代码
import java.util.ArrayList; import java.util.List; public class Solution { List<List<String>> rst = new ArrayList<List<String>>(); char[][] cs; boolean[][] marked; int len; public List<List<String>> solveNQueens(int n) { cs = new char[n][n]; marked = new boolean[n][n]; len = n; for(int i=0; i<n; i++){ for(int j=0; j<n; j++) { cs[i][j] = '.'; } } dfs(0); return rst; } // pass parameters to faster private void dfs(int curRow) { if(curRow == len) { List<String> t = new ArrayList<String>(); for(int i=0; i<len; i++) { t.add(new String(cs[i])); } rst.add(t); return; } for(int j=0; j<len; j++) { // replace NotInOneLine with array if(isValide(curRow, j)) { marked[curRow][j] = true; cs[curRow][j] = 'Q'; dfs(curRow+1); marked[curRow][j] = false; cs[curRow][j] = '.'; } } } private boolean isValide(int row, int col) { for(int i=0; i<len; i++) if(marked[row][i] || marked[i][col]) return false; int increment = 1; while(isValidate(row, col, increment)) { if(row+increment<len && col+increment<len) { if(marked[row+increment][col+increment]) return false; } if(row-increment>=0 && col-increment>=0) { if(marked[row-increment][col-increment]) return false; } if(row-increment>=0 && col+increment<len) { if(marked[row-increment][col+increment]) return false; } if(row+increment<len && col-increment>=0) { if(marked[row+increment][col-increment]) return false; } increment ++; } return true; } private boolean isValidate(int row, int col, int increment) { if(row+increment<len && col+increment<len) return true; if(row+increment<len && col-increment>=0) return true; if(row-increment>=0 && col+increment<len) return true; if(row-increment>=0 && col-increment>=0) return true; return false; } } 最开始用两层循环，在循环里面递归调用dfs，结果出现很多重复，
for(int i=0; i<len; i++) { for(int j=0; j<len; j++) { // replace NotInOneLine with array if(isValide(i, j)) { marked[i][j] = true; cs[i][j] = 'Q'; dfs(curQ+1); marked[i][j] = false; cs[i][j] = '.'; } } }
换成一维的才没有，具体也没弄懂，其实完全没有必要用2D的DFS
这个题用回溯应该也没有问题
