八皇后問(wèn)題
在 8×8 格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊儡嘶，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上蹦狂，問(wèn)有多少種擺法。
回溯算法
回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過(guò)程凯楔，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)摆屯，就“回溯”返回，嘗試別的路徑虐骑。
回溯算法和窮舉法很像，都是樹(shù)的深度優(yōu)先遍歷廷没，但回溯法會(huì)進(jìn)行'剪枝'，比如第 5 層某 i 葉子結(jié)點(diǎn)時(shí)發(fā)現(xiàn)該節(jié)點(diǎn)已經(jīng)無(wú)意義垂寥，會(huì)直接跳過(guò)該節(jié)點(diǎn)下面的遍歷另锋，提高了效率
求解
不考慮限制條件盏缤，問(wèn)題變成了排列組合，一共有 C64 取 8(22307873454720)種
分析該問(wèn)題唉铜，問(wèn)題可以拆解為:
- 從 64 個(gè)格子中取 8 個(gè)格子放入 8 個(gè)皇后
- 限制條件：任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上
我們用一個(gè)二維矩陣來(lái)記錄皇后的位置和狀態(tài),其中 1 表示該位置已經(jīng)有皇后了
let num = 8;
for (let i = 0; i < num; i++) {
this.arr[i] = [];
for (let j = 0; j < num; j++) {
this.arr[i][j] = 0;
}
}
// 橫軸表示 i 行潭流，縱軸表示第 j 列
// 1 2 3 4 5 6 7 8
1 [ 0, 0, 0, 0, 0, 0, 0, 0 ], # （0,0) 表示第一行第一列 （0,1) 表示第一行第二列
2 [ 0, 0, 0, 0, 0, 0, 0, 0 ],
3 [ 0, 0, 0, 0, 0, 0, 0, 0 ],
4 [ 0, 0, 0, 0, 0, 0, 0, 0 ],
5 [ 0, 0, 0, 0, 0, 0, 0, 0 ],
6 [ 0, 0, 0, 0, 0, 0, 0, 0 ],
7 [ 0, 0, 0, 0, 0, 0, 0, 0 ],
8 [ 0, 0, 0, 0, 0, 0, 0, 0 ]
基本步驟如下:
- 一個(gè)檢查函數(shù)，確定該位置不會(huì)與其他皇后有沖突
- 從第一行開(kāi)始灰嫉，8 列中任意選一個(gè)列執(zhí)行步驟 0，若安全則開(kāi)始放第二行........直到放到第八行若有位置讼撒，則已經(jīng)找到一個(gè)解輸出；若第 i 行的操作中沒(méi)有位置可以放入皇后回退回第 i-1 行的操作根盒，若 i=0 即第一行則說(shuō)明已經(jīng)執(zhí)行完畢程序結(jié)束
用遞歸可以很容易的實(shí)現(xiàn)，什么是遞歸炎滞？看下面這個(gè)斐波那契數(shù)列敢艰，就是一個(gè)很簡(jiǎn)單的遞歸,遞歸有兩個(gè)很重要的特點(diǎn):一個(gè)結(jié)束條件钠导，不斷調(diào)用自身。
recurFib(n) {
if (n < 2) return n;
return this.recurFib(n - 1) + this.recurFib(n - 2);
}
// 棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu),先壓進(jìn)棧的最后出棧
n = 3時(shí)
1.recurFib(3)壓入執(zhí)行棧森瘪，執(zhí)行到 recurFib(2) + recurFib(1),recurFib(2)被壓入執(zhí)行棧中
2.recurFib(2)執(zhí)行，執(zhí)行到 recurFib(1) + recurFib(0)扼睬，recurFib(1)被壓入執(zhí)行棧中
recurFib(1)執(zhí)行，返回1痰驱；recurFib(1)執(zhí)行完出棧
繼續(xù)執(zhí)行recurFib(2), 1 + recurFib(0)瞳浦，recurFib(0)壓入執(zhí)行棧中
recurFib(0)執(zhí)行，返回1叫潦；recurFib(0)執(zhí)行完出棧
繼續(xù)執(zhí)行recurFib(2)，1 + 1，返回2短蜕，recurFib(2)執(zhí)行完出棧
3.繼續(xù)執(zhí)行recurFib(3)，執(zhí)行到 2 + recurFib(1)朋魔，recurFib(1)被壓入執(zhí)行棧中
recurFib(1)執(zhí)行，返回1警检；recurFib(1)執(zhí)行完出棧
繼續(xù)執(zhí)行recurFib(3)，2 + 1 扇雕，返回 3，棧已經(jīng)清空镶奉，程序結(jié)束
回到 8 皇后問(wèn)題,關(guān)鍵代碼如下:
buildList(list, row) {
// 遞歸中止條件,找到一個(gè)解緩存起來(lái)
if (row === list.length) {
this.result.push(JSON.parse(JSON.stringify(list)));
return;
}
for (let col = 0, len = list.length; col < len; col++) {
if (this.isSafe(list, row, col)) {
list[row][col] = 1;
this.buildList(list, row + 1);
// 走到這里，說(shuō)明該次遞歸已經(jīng)結(jié)束哨苛，不管找沒(méi)找到鸽凶，都需要重置,繼續(xù)找下一個(gè)可放置的位置
list[row][col] = 0;
}
}
}
isSafe 方法吱瘩，確保該行該列不會(huì)與其他皇后沖突:
isSafe(list, row, col) {
const len = list.length;
// 同一列
for (let i = 0; i < len; i++) {
if (list[i][col] === 1) return false;
}
// 斜右上方
for (let i = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) {
if (list[i][j] === 1) return false;
}
// 斜左上方
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (list[i][j] === 1) return false;
}
return true;
}
完整代碼
class Queen {
constructor(num) {
this.num = num;
this.arr = [];
this.result = [];
this.initList();
this.buildList(this.arr, 0);
}
initList() {
let num = this.num;
for (let i = 0; i < num; i++) {
this.arr[i] = [];
for (let j = 0; j < num; j++) {
this.arr[i][j] = 0;
}
}
console.log(this.arr);
}
buildList(list, row) {
// 遞歸中止條件,找到一個(gè)解緩存起來(lái)
if (row === list.length) {
this.result.push(JSON.parse(JSON.stringify(list)));
return;
}
for (let col = 0, len = list.length; col < len; col++) {
if (this.isSafe(list, row, col)) {
list[row][col] = 1;
this.buildList(list, row + 1);
// 走到這里迹缀，說(shuō)明該次遞歸已經(jīng)結(jié)束，不管找沒(méi)找到祝懂，都需要重置
list[row][col] = 0;
}
}
}
isSafe(list, row, col) {
const len = list.length;
// 同一列
for (let i = 0; i < len; i++) {
if (list[i][col] === 1) return false;
}
// 斜右上方
for (let i = row - 1, j = col + 1; i >= 0 && j < len; i--, j++) {
if (list[i][j] === 1) return false;
}
// 斜左上方
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (list[i][j] === 1) return false;
}
return true;
}
}
const queen = new Queen(8);
console.log(queen.result);
優(yōu)化
其實(shí)解法跟之前一樣，上面用了二維矩陣來(lái)記錄位置砚蓬，因?yàn)橐呀?jīng)確定同一行不可能存在 2 個(gè)皇后實(shí)際上只用一維數(shù)組就表示：list[row] = col;減少空間消耗
isSafe 判斷和之前不同
isSafe(row) {
for (let i = 0; i < row; i++) {
// 判斷列
if (this.arr[i] === this.arr[row]) return false;
// 判斷對(duì)角線
if (Math.abs(this.arr[row] - this.arr[i]) === row - i) return false;
}
return true;
}
完整代碼
class Queen {
constructor(num) {
this.num = num;
this.arr = [];
this.result = [];
this.initList();
this.buildList(0);
}
initList() {
let num = this.num;
for (let i = 0; i < num; i++) {
this.arr[i] = 0;
}
}
buildList(row) {
// 遞歸中止條件,找到一個(gè)解緩存起來(lái)
if (row === this.num) {
this.result.push(JSON.parse(JSON.stringify(this.arr)));
return;
}
for (let col = 0; col < this.num; col++) {
this.arr[row] = col;
if (this.isSafe(row)) {
this.buildList(row + 1);
}
}
}
isSafe(row) {
for (let i = 0; i < row; i++) {
// 判斷列
if (this.arr[i] === this.arr[row]) return false;
// 判斷對(duì)角線
if (Math.abs(this.arr[row] - this.arr[i]) === row - i) return false;
}
return true;
}
}
const queen = new Queen(8);
console.log(queen.result);
END
跑一下，可知 8 皇后問(wèn)題一共有 92 種擺法
嘗試跑了一下 n=16 的情況祟剔，cpu 直接燃燒，幾分鐘沒(méi)出結(jié)果摩梧，果斷放棄......
可見(jiàn)遞歸有多么耗性能~~
