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:
这次用了一维数组，横坐标为下表，纵坐标为值
public class Solution { public List<String[]> solveNQueens(int n) { ArrayList<String[]> res= new ArrayList<String[]>(); int nrow= n; int[] nQueen= new int[n]; DFS_nQueen(res,0,nrow,nQueen); return res; } public void DFS_nQueen(ArrayList<String[]> res, int row, int nrow, int[] nQueen) { // TODO Auto-generated method stub if(row==nrow){ String[] unit=new String[nrow]; for(int i=0;i<nrow;i++){ StringBuilder s=new StringBuilder(); for(int j=0;j<nrow;j++){ if(j==nQueen[i]){ s.append("Q"); }else{ s.append("."); } } unit[i]=s.toString(); } res.add(unit); }else{ for(int i=0;i<nrow;i++){ nQueen[row]=i; if(isValid(nQueen,row)){ DFS_nQueen(res,row+1,nrow,nQueen); } } } } public boolean isValid(int[] array,int row){ for(int i=0;i<row;i++){ if(array[i]==array[row] || (Math.abs(i-row)==Math.abs(array[i]-array[row]))){ return false; } } return true; } }
原文：http://www.cnblogs.com/joannacode/p/4548190.html