首页 > 代码库 > [LeetCode]N-Queens II

[LeetCode]N-Queens II

题目:给定一个整数n,表示棋盘的规模是n*n,在棋盘上放置n个皇后,要求同一行,同一列,同一条对角线不能有相同的皇后,求出可行的方案数

算法:深度优先搜索 + 剪枝优化

剪枝优化方案如下(拿4皇后为例):

不难发现存在下列规律:

同一条左对角线:row - col + n = 恒定值
同一条右对角线:row + col = 恒定值

public class Solution {
    final int CHECK_NUMBER = 3;  // check tree points: col, left diagonal and right diagonal
	    final int MAX_NUMBER = 1024;
	    
	    int nSolutions = 0;
		boolean[][] isVisited = new boolean[CHECK_NUMBER][MAX_NUMBER];
		
		public int totalNQueens(int n) {
	        for (int i=0; i<CHECK_NUMBER; ++i) {
	        	isVisited[i] = new boolean[MAX_NUMBER];
	        }
	        
	        dfs(0, n);
	        return nSolutions;
	    }
		
		/**
		 * boolean[0][MAXN]:
		 *
		 * 0: check the col
		 * 1: check the left diagonal
		 * 2. check the right diagonal
		 * 
		 */
		public void dfs(int row, int nGirds) {
			if (row == nGirds) {
				++nSolutions;
				return ;
			}
			
			for (int col=0; col<nGirds; ++col) {
				if (!isVisited[0][col] 
				 && !isVisited[1][row-col+nGirds]
				 && !isVisited[2][row+col]) {
					isVisited[0][col] = true;
					isVisited[1][row-col+nGirds] = true;
					isVisited[2][row+col] = true;
					dfs(row+1, nGirds);
					isVisited[0][col] = false;
					isVisited[1][row-col+nGirds] = false;
					isVisited[2][row+col] = false;
				}
			}
		}
}