LintCode 34. N皇后问题 II JavaScript算法

描述

根据n皇后问题，现在返回n皇后不同的解决方案的数量而不是具体的放置布局。

样例

- 例1:

输入: n=1
输出: 1
解释:
1:
1

- 例2:

输入: n=4
输出: 2
解释:
1:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
2:
0 1 0 0 
0 0 0 1
1 0 0 0
0 0 1 0

解析

采用了lintcode上华助教的方法，dfs暴力搜索
N皇后属于算法经典问题了
可以在leetcode上找到很多解法
有兴趣的话可以搜索看看

const totalNQueens = function (n) {
    var cols, sum;
    function canPut(row, col) {
        var i;
        for (i = 0; i < row; i++) {
            if (cols[i] - i === col - row) {
                return false;
            }
            if (cols[i] + i === col + row) {
                return false;
            }
            if (cols[i] === col) {
                return false;
            }
        }
        return true;
    }
    function dfs(n, k) {
        var i;
        if (k === n) {
            sum++;
            return;
        }
        for (i = 0; i < n; i++) {
            if (!canPut(k, i)) {
                continue;
            }
            cols[k] = i;
            dfs(n, k + 1);
        }
    }
    cols = new Array(n);
    sum = 0;
    dfs(n, 0);
    return sum;
}

运行结果