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.."] ]思路：回溯法，使用ArrayList
public class Solution {
public List
solveNQueens(int n) {
List
result = new LinkedList
(); search(result,n,new ArrayList
(),1); return result; } private boolean isValid(ArrayList
al) { int column = al.get(al.size() - 1); for (int i = 0; i < al.size() - 1; i++) { if (column == al.get(i) || Math.abs(column - al.get(i)) == Math.abs(al.size()-1 - i)) { return false; } } return true; } private void search(List
result,int n, ArrayList
al, int col) { if (col > n){ char []temp=new char[n]; Arrays.fill(temp, '.'); String []str=new String[n]; for(int i=0;i
result=s.solveNQueens(n); for(String []str:result){ System.out.println(Arrays.toString(str)); } System.out.println("\n"+result.size()); } }