【LeetCode】51. N-Queens

问题描述

https://leetcode.com/problems/n-queens/#/description

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.."]
]

算法分析

N-皇后问题

因为国际象棋中，皇后可以在横、竖、斜线上不限步数地吃掉其他棋子，所以N个皇后不能在同一行、同一列以及同一斜线上。

考虑n个皇后的放法时，我们先按照简单暴力算法的思路来捋一捋题目。

我们首先一个一个位置试探，比如先在(1,1)，即第一行、第一列上放置第一个皇后，，然后在(1,2)放置第二个皇后，这时候，就看皇后们是不是在同行、同列或同斜线，皇后不能在同一行，所以第二个皇后放(1,2)就不行，同时第二个皇后放第一行都不可行，所以我们就可以直接考虑第二行了，根据不能同行这个特点，我们在遍历解法时， 就可以直接排除掉“行”这个因素了。这时候，一个解法就可以实现使用一个数组c[n]表示，c[i]=j，表示第i行的皇后放在第j列。

接下来，考虑根据c[n]如何判断皇后是同列或同斜线的。

同列容易，如果c[i]=c[j]，就表明两个皇后在同一列，解法不可取；同斜即当i-j = c[i]-c[j]时，第i行的皇后和第j行的皇后同斜线，即行之间的差等于列之间的差时，两个皇后同斜线。

考虑好了一个解法怎么出来后，就只需要使用递归回溯就可以得出所有解法了。

代码

       public List<List<String>> solveNQueens(int n) {
	        List<List<String>> res = new ArrayList<>();
	        solve(res, new int[n], n, 0, new String[n]);
	        return res;
	    }
	    
	    public void solve(List<List<String>> list, int[] c, int n, int index, String[] cur) {
	    	if(index == n) {
	    		list.add(Arrays.asList(cur.clone()));
	    		return;
	    	}
	    	// 从第一列开始遍历
	    	for(int j=0;j<n;j++) {
	    		c[index] = j; // 将第index行的皇后放在第j列
	    		boolean has = false; // 是否有冲突标志位
	    		// 遍历当前已放置好的皇后，看是否有冲突
	    		for(int i=0;i<index;i++) {
	    			if(c[i] == c[index] || Math.abs(i-index)==Math.abs(c[i]-c[index])) {
	    				has = true;
	    			}
	    		}
	    		if(!has) {
	    			char[] row = new char[n];
		    		Arrays.fill(row, '.');
		    		row[j] = 'Q';
		    		cur[index] = new String(row);
	    			// 如果没有冲突，当前解法可行，增加一位皇后
	    			solve(list, c, n, index+1, cur);
	    		}
	    	}
	    }