首页 > 代码库 > LeetCode 50 N-Queens

LeetCode 50 N-Queens

2024-08-01 09:19:03   214人阅读

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<Integer>  al来存储某个皇后的列，而它在ArrayList的索引就是其行数。
public class Solution {
	public List<String[]> solveNQueens(int n) {
		List<String[]> result = new LinkedList<String[]>();
		search(result,n,new  ArrayList<Integer>(),1);
		return result;
	}

	private boolean isValid(ArrayList<Integer> 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<String[]>result,int n, ArrayList<Integer> al, int col) {
		if (col > n){
			char []temp=new char[n];
			Arrays.fill(temp, '.');
			String []str=new String[n];
			for(int i=0;i<al.size();i++){
				StringBuilder sb=new StringBuilder(String.valueOf(temp));
				sb.setCharAt(al.get(i), 'Q');
				str[i]=sb.toString();
			}
			result.add(str);
		}else {
			for (int j = 0; j < n; j++) {
				al.add(j);
				if (isValid(al)) {
					search(result,n, al, col + 1);
				}
				al.remove(al.size()-1);
			}
		}
	}
	public static void main(String []args){
		Solution s=new Solution();
		int n=8;
		List<String []> result=s.solveNQueens(n);
		for(String []str:result){
			System.out.println(Arrays.toString(str));
		}
		
		System.out.println("\n"+result.size());
	}
}


LeetCode 50 N-Queens


联系
我们