LeetCode-N-Queens

末蓝、 2022-08-04 10:43 140阅读 0赞

The n\-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

![8-queens.png][]

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

八皇后问题的变形题，一个不能再经典的题了。回溯法，要保证任意两各queens都不能再同一行、同一列、同一对角线。代码如下：

public List<List<String>> solveNQueens(int n) {
            List<List<String>> lists = new ArrayList<List<String>>();
            dfs(lists, new int[n], 0);
            return lists;
        }
        
        private void dfs(List<List<String>> lists, int[] ret, int col) {
        	if (col == ret.length) {
        		List<String> list = new ArrayList<String>(ret.length);
        		for (int p = 0; p < ret.length; p++) {
        			StringBuilder sb = new StringBuilder();
        			for (int q = 0; q < ret.length; q++) {
        				if (ret[p] == q) sb.append("Q");
        				else sb.append(".");
        			}
        			list.add(sb.toString());
        		}
        		lists.add(list);
        		return;
        	}
        	for (int k = 0; k < ret.length; k++) {
        		ret[col] = k;
        		if (check(ret, col))
        			dfs(lists, ret, col+1);
        	}
        }
        
        private boolean check(int[] ret, int col) {    	
        	for (int p = 0; p < col; p++) {
        		if (Math.abs(ret[col]-ret[p]) == Math.abs(col-p))
        			return false;
        		if (ret[col] == ret[p])
        			return false;
        	}
        	return true;
        }

其实这里面还是有很多值得研究的，首先搞了一个n长度的一维数组，而不是二维数组，因为数组的下标就代表了第几列，即ret\[col\] = row， 这是一个很好的优化。我上面是一列一列的扫描的，你也可以一行一行的扫描，都一样，因为这是个n\*n的正方形。

[8-queens.png]: http://www.leetcode.com/wp-content/uploads/2012/03/8-queens.png