【LeetCode】N-Queens II N皇后问题 回溯法

Have you been asked this question in an interview?

class Solution {
public:

    int sum;
    int *board;
    
    bool isok(int k) //check whether the kth Queen can be put down.
    {
        for(int i = 1; i < k; i++)
	    {
		if(board[i] == board[k] || abs(i-k) == abs(board[i] - board[k]))
			return false;
	    }
	    return true;
    }
    
    void totalN(int n, int k)
    {
        if(k > n)
            sum++;
        else{
            for(int i = 1; i <= n; i++)
            {
                board[k] = i;
                if(isok(k))
                    totalN(n, k+1);
            }
        }
    }

    int totalNQueens(int n) {
        board = new int[n+1];
        sum = 0;
        totalN(n, 1);
        int res = sum;
        delete []board;
        return res;
    }
};

【LeetCode】N-Queens II N皇后问题 回溯法,布布扣,bubuko.com

【LeetCode】N-Queens II N皇后问题 回溯法

原文：http://blog.csdn.net/xiaozhuaixifu/article/details/21296395