八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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>
网友评论