阅读 246

每天一道前端算法题--回溯算法--N皇后问题

什么是回溯算法

先来了解一下什么时回溯算法。回溯的处理思想,有点类似枚举搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。

接下来来看下题目,N皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

Image text

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

求解思路

N皇后问题非常适合使用回溯算法来做,我们把每一行选择值分为一个阶段,在放置值的过程中,我们不停检查当前的方法,是否满足要求,满足就继续跳到下一行放置棋子,不满足就换一种方法,继续尝试。

代码

首先是写出递推公式

function getRowPos (rowIndex, arr = []) {
    // n个棋子都放置完成,返回结果
    if (rowIndex === n) {
        result.push(arr)
        return
    }
    for (let col = 0; col < n; col ++) {
        // 如果是第一行,就直接放入,然后跳到下一行
        if (rowIndex === 0) {
            arr = [col]
            getRowPos(rowIndex + 1, arr)
        } else {
            // 判断是否符合要求,符合就插入并继续跳到下一行
            if (isOk(rowIndex, col, arr)) {
                const newArr = [...arr]
                newArr.push(col)
                getRowPos(rowIndex + 1, newArr)
            }
        }
    }
}
复制代码

然后写出判断条件

function isOk (row, col, arr) {
    let leftTop = col - 1
    let rightTop = col + 1
    for (let i = row - 1; i >= 0; i --) {
        const lastPos = arr[i]
        // 判断正上方是否有棋子
        if (lastPos === col) {
            return false
        }
        // 判断左上方是否有棋子
        if (leftTop >= 0 && lastPos === leftTop) {
            return false
        }
        // 判断右上方是否有棋子
        if (rightTop < n && lastPos === rightTop) {
            return false
        }
        leftTop--
        rightTop++
    }
    return true
}
复制代码

最后格式化输出

// 格式化输出
function print () {
    return result.map(item => {
        return item.map(item2 => {
            let str = ''
            for (let i = 0; i < n; i++) {
                if (item2 === i) {
                    str += 'Q'
                } else {
                    str += '.'
                }
            }
            return str
        })
    })
}
复制代码

完整的代码


var solveNQueens = function(n) {
    const result = []   
    function getRowPos (rowIndex, arr = []) {
        // n个棋子都放置完成,返回结果
        if (rowIndex === n) {
            result.push(arr)
            return
        }
        for (let col = 0; col < n; col ++) {
            // 如果是第一行,就直接放入,然后跳到下一行
            if (rowIndex === 0) {
                arr = [col]
                getRowPos(rowIndex + 1, arr)
            } else {
                // 判断是否符合要求,符合就插入并继续跳到下一行
                if (isOk(rowIndex, col, arr)) {
                    const newArr = [...arr]
                    newArr.push(col)
                    getRowPos(rowIndex + 1, newArr)
                }
            }         
        }
    }

    // 判断该位置是否合理
    function isOk (row, col, arr) {
        let leftTop = col - 1
        let rightTop = col + 1
        for (let i = row - 1; i >= 0; i --) {
            const lastPos = arr[i]
            // 判断正上方是否有棋子
            if (lastPos === col) {
                return false
            }
            // 判断左上方是否有棋子
            if (leftTop >= 0 && lastPos === leftTop) {
                return false
            }
            // 判断右上方是否有棋子
            if (rightTop < n && lastPos === rightTop) {
                return false
            }
            leftTop--
            rightTop++
        }
        return true
    }

    // 格式化输出
    function print () {
        return result.map(item => {
            return item.map(item2 => {
                let str = ''
                for (let i = 0; i < n; i++) {
                    if (item2 === i) {
                        str += 'Q'
                    } else {
                        str += '.'
                    }
                }
                return str
            })
        })
    }
    getRowPos(0)
    return print()
};
复制代码
关注下面的标签,发现更多相似文章
评论