[leetcode]N-Queens

新博文地址：

[leetcode]N-Queens

N-Queens

 

写道

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-Queens II没啥区别。有啥不明白的看这里。

代码如下：

ArrayList<String[]> result = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        if(n <= 0){
        	return result;
        }
        int[] hash = new int[n]; 
        place(0,n,hash);
        return result;
    }
    private void place(int number,int n,int [] hash){
    	if(number == n){//load successfully! fill String[] by hash
    		String[] strs = new String[n];
    		for(int i = 0; i < n; i++){
    			strs[i] = "";
    			for(int j = 0 ; j < n;j++){
    				if(j != hash[i]){
    					strs[i] += ".";
    				}else{
    					strs[i] += 'Q';
    				}
    			}
    		}
    		result.add(strs);
    	}

    	for(int i = 0 ; i < n; i++){
    		if(isConflict(hash,number,i)){
    			continue;
    		}
    		hash[number] = i;
    		place(number + 1, n,hash);
    	}
    }
    private boolean isConflict(int[] hash,int row,int column){
    	if(row == 0){
    		return false;
    	}
    	for(int i = 0; i < row;i++){
    		if(hash[i] == column || hash[i] - i == column - row || hash[i] + i == column + row){
    			return true;
    		}
    	}
    	return false;
    }