N皇后

回溯法

// 参见leetcode 51题
var totalNQueens = function(n) {
    const result = [];
    const preBlock = [];
    // let max = 10000;
    // let index = 0;
    const walk = function(n, preBlock, r) {
        // console.log(preBlock)
        // if (index++ > max) return;
        if (n === r) {
            preBlock.length === n && result.push(JSON.parse(JSON.stringify(preBlock)));
            return;
        }
        
        for(let i = 0; i < n; ++i) {
            // 是否可放置标志
            let canPut = true;
            preBlock.forEach(({row, col}) => {
                // 同行同列 不行
                if (row === r || col === i) {
                    canPut = false;
                    return;
                }
                // 对角线不行
                if (row - r === col - i
                    || row - r === i - col
                    || r - row === i - col
                    || r - row === col - i
                    ) {
                    canPut = false;
                    return;
                }
            });
            if (canPut) {
                preBlock.push({
                    row: r,
                    col: i,
                });
                walk(n, preBlock, r + 1);
                preBlock.pop();
            }                                                                                                                                                                                             
        }
    }
    
    walk(n, preBlock, 0);

    return result.map(it => {
        const arr = [];
        it.forEach(({ col }) => {
            let str = '';
            for(let i = 0; i < n; i++) {
                if (i === col) {
                    str += 'Q';
                } else {
                    str += '.';
                }
            }
            arr.push(str);
        });
        return arr;
    });
};