用JavaScript解决八皇后问题

2019-05-20 本文已影响0人小小的开发人员

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案，1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

我们用JS实现该过程。

为了演示方便，我们先在页面搭建网格：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<style>
    * {
        margin: 0;
        padding: 0;
    }
    li {
        list-style: none;
    }
    #ul1 {
        height: auto;
        margin: 20px auto;
        overflow: hidden;
        border: 1px #000 solid;
        border-right: none;
        border-bottom: none;
    }
    #ul1 li {
        float: left;
        border: 1px #000 solid;
        border-left: none;
        border-top: none;
    }
</style>
<body>
<ul id="ul1"></ul>
</body>
<script >
    let oUl = document.getElementById('ul1')
    let aLi = document.getElementsByTagName('li')
    let sizeGrid = 50
    let num = 8
    let iCount = 0

    init()
    function init() {
        createGird()
    }
    function createGird() {
        let len = num * num
        oUl.style.width = num * (sizeGrid + 1) + 'px'
        for (let i = 0; i < len; i++) {
            let oLi = document.createElement('li')
            oLi.style.width = sizeGrid + 'px'
            oLi.style.height = sizeGrid + 'px'
            oUl.appendChild(oLi)
        }
    }
</script>
</html>

建立坐标系，为每一个网格挂载坐标信息：

for (let i = 0; i < num; i++) {
    for (let j = 0; j < num; j++) {
        aLi[ i * num + j].x = j
        aLi[ i * num + j].y = i
        aLi[ i * num + j].innerHTML = j + ',' + i
    }
}

我们可以看出同一行的方格纵坐标相同，同一列的方格横坐标相同，同一斜线上的方格坐标相加或相减值是一样的。

实现思路：

我们先给每个方格挂载索引index = -1，表示还未开始摆放。
从第一行的第一个方格开始摆放，此时index = 0，表示这是第一步，满足上图规则的（也就是在横纵斜方向）的方格也令其index = 0，index ! == -1的方格表示以后不能再摆放了。
从第二行搜索index === -1 的方格，令其index = 1，表示这是第二步，同样，满足横纵斜方向的也令其index = 1。
重复上述过程，当第8行时，仍然能找到一个index === -1的方格，表示是一种正确的摆放方式，我们记录下来。如果在下一行找不到index === -1的方格，则表示摆放方案不可行，我们需要回溯到上一行，改变上一行摆放方格的位置，再次重复步骤4。

我们来实现上述过程：

function setQueen(iQueen) {

    // 终止条件
    if (iQueen === num) {
        return
    }

    for (let i = 0; i < num; i++) {
        if (aLi[iQueen * num + i].index === -1) {
            aLi[iQueen * num + i].innerHTML = iQueen
            let x = aLi[ iQueen * num + i].x
            let y = aLi[ iQueen * num + i].y
            for (let j = 0; j < aLi.length; j++) {
                if (aLi[j].index == -1 && (aLi[j].x == x || aLi[j].y == y || aLi[j].x - aLi[j].y == x - y || aLi[j].x + aLi[j].y == x + y))  {
                    aLi[j].index = iQueen // 不可以摆放的方格
                }
            }
            setQueen(iQueen + 1) // 跳转到下一行

            // 回溯
            for (let j = 0; j < aLi.length; j++) {
                if (aLi[j].index === iQueen) {
                    aLi[j].index = -1 // 把上一行的状态恢复
                }
            }
        }
    }
}

我们来做一些统计：

let iCount = 0 // 共有多少种摆放方案
let postArr= [] // 其中一种方案具体的摆放
let postAll = [] // 所有方案的摆放

完整代码：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<style>
    * {
        margin: 0;
        padding: 0;
    }
    li {
        list-style: none;
    }
    #ul1 {
        height: auto;
        margin: 20px auto;
        overflow: hidden;
        border: 1px #000 solid;
        border-right: none;
        border-bottom: none;
    }
    #ul1 li {
        float: left;
        border: 1px #000 solid;
        border-left: none;
        border-top: none;
        text-align: center;
        line-height: 50px;
    }
</style>
<body>
<ul id="ul1"></ul>
</body>
<script >
    let oUl = document.getElementById('ul1')
    let aLi = document.getElementsByTagName('li')
    let sizeGrid = 50
    let num = 8
    let iCount = 0
    let postArr= []
    let postAll = []

    init()
    function init() {
        createGird()
        setQueen(0)
        console.log(iCount)
        console.log(postAll)
    }
    function createGird() {
        let len = num * num
        oUl.style.width = num * (sizeGrid + 1) + 'px'
        for (let i = 0; i < len; i++) {
            let oLi = document.createElement('li')
            oLi.style.width = sizeGrid + 'px'
            oLi.style.height = sizeGrid + 'px'
            oLi.index = -1
            oUl.appendChild(oLi)
        }
        for (let i = 0; i < num; i++) {
            for (let j = 0; j < num; j++) {
                aLi[ i * num + j].x = j
                aLi[ i * num + j].y = i
                // aLi[ i * num + j].innerHTML = j + ',' + i
                aLi[ i * num + j].innerHTML = aLi[ i * num + j].index
            }
        }
    }
    function setQueen(iQueen) {

        // 终止条件
        if (iQueen === num) {
            iCount++
            postAll.push(postArr.concat())
            return
        }

        for (let i = 0; i < num; i++) {
            if (aLi[iQueen * num + i].index === -1) {
                aLi[iQueen * num + i].innerHTML = iQueen
                postArr.push(aLi[iQueen * num + i])
                let x = aLi[ iQueen * num + i].x
                let y = aLi[ iQueen * num + i].y
                for (let j = 0; j < aLi.length; j++) {
                    if (aLi[j].index == -1 && (aLi[j].x == x || aLi[j].y == y || aLi[j].x - aLi[j].y == x - y || aLi[j].x + aLi[j].y == x + y))  {
                        aLi[j].index = iQueen // 不可以摆放的方格
                    }
                }
                setQueen(iQueen + 1) // 跳转到下一行

                // 回溯
                postArr.pop()
                for (let j = 0; j < aLi.length; j++) {
                    if (aLi[j].index === iQueen) {
                        aLi[j].index = -1 // 把上一行的状态恢复
                    }
                }
            }
        }
    }
</script>
</html>

用JavaScript解决八皇后问题

猜你喜欢

热点阅读